二叉查找树(Binary Search Tree)

定义

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点

深度为3的二叉查找树

优势

  1. 查找、插入的时间复杂度较低
  2. 时间复杂度为O(logN),最坏时间复杂度为O(N)
  3. 从基础的二叉查找树可以衍生平衡二叉树,从而使得查询/插入操作的时间复杂度平衡在O(logN) PS: 查询节点的时间与树高度相关,高度越高,时间越长

劣势

  1. 由于普通的二叉查找树没有做平衡(通过旋转来达到树左右子树高度相差不大)处理,导致可能会出现树的严重倾斜

平衡二叉树与倾斜的二叉树.png

二叉树查找

在二叉搜索树b中查找x的过程为: 若b是空树,则搜索失败,否则: 若x等于b的根节点的数据域之值,则查找成功;否则: 若x小于b的根节点的数据域之值,则搜索左子树;否则: 若x大于b的根节点的数据域之值,则搜索右子树。

查找过程.png

二叉树插入

向一个二叉搜索树b中插入一个节点s的算法,过程为: 若b是空树,则将s所指结点作为根节点插入,否则: 若s->data等于b的根节点的数据域之值,则返回,否则: 若s->data小于b的根节点的数据域之值,则把s所指节点插入到左子树中,否则: 把s所指节点插入到右子树中。(新插入节点总是叶子节点)

插入过程.png

二叉树删除

在二叉查找树删去一个结点,有3种情况:

  1. 若*p结点为叶子结点,即当前节点的左子树和右子树均为空树: 由于删去叶子结点不破坏整棵树的结构,则只需修改其父节点的指针即可。

删除无子树的节点

  1. p结点只有左子树或右子树: 此时只要令左子树或右子树直接成为父结点左子树(当p是左子树)或右子树(当*p是右子树)即可,作此修改也不破坏二叉查找树的特性。

删除只有一个子树

  1. p结点的左子树和右子树均不空: 在删去p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法 a. 令p的左子树为f的左/右(依p是f的左子树还是右子树而定)子树,s为p左子树的最右下的结点,而p的右子树为s的右子树 b. 令p的直接前驱(in-order predecessor)或直接后继(in-order successor)替代p,然后再从二叉查找树中删去它的直接前驱(或直接后继)。

删除有两个子树的节点

前驱(Preducessor)

定义:节点val值小于该节点val值并且值最大的节点 若一个节点有左子树,那么该节点的前驱节点是其左子树中val值最大的节点(也就是左子树中所谓的rightMostNode) 若一个节点没有左子树,那么判断该节点和其父节点的关系 2.1 若该节点是其父节点的右节点,那么该节点的前驱结点即为其父节点。 2.2 若该节点是其父节点的左节点,那么需要沿着其父亲节点一直向树的顶端寻找,直到找到一个节点P,P节点是其父节点Q的右节点,那么Q就是该节点的前驱节点

TreeMap的Preducessor算法

如最上图所示: 3的前驱是1:当前节点有左子树,找到左子树最右的节点 10的前驱是8:当前节点没有左子树,并且是父节点的右子树 4的前驱是3:当前节点没有左子树,找到沿父节点出于左子树节点

后继(Successor)

定义:节点val值大于该节点val值并且值最小的节点 若一个节点有右子树,那么该节点的后继节点是其右子树中val值最小的节点(也就是右子树中所谓的leftMostNode) 若一个节点没有右子树,那么判断该节点和其父节点的关系 2.1 若该节点是其父节点的左子树,那么该节点的后继结点即为其父节点 2.2 若该节点是其父节点的右子树,那么需要沿着其父亲节点一直向树的顶端寻找,直到找到一个节点P,P节点是其父节点Q的子树 ,那么Q就是该节点的后继节点

TreeMap的Successor算法

如最上图所示: 8的后继是10:当前节点有右子树,并且右子树节点无左子树 10的后继是13:当前节点有右子树,则找到右节点的右子树最小的节点 4的后继是6:当前节点是父节点的左子树,则该节点的后继即为其父节点

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1535
来自专栏Micro_awake web

python二叉树递归算法之后序遍历,前序遍历,中序遍历

1 #!/usr/bin/env python 2 # -*- coding: utf-8 -*- 3 # @Date : 2016-11-18 0...

2465
来自专栏海天一树

二叉树的建立和遍历

二叉树:每个结点的子结点个数不大于2的树,叫做二叉树。 根结点:最顶部的那个结点叫做根结点,根结点是所有子结点的共同祖先。比如上图中的“7”结点就是根结点。 子...

933
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1834
来自专栏Hongten

ArrayList VS Vector(ArrayList和Vector的区别)_面试的时候经常出现

7682
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39判断平衡二叉树

题目:输入一颗二叉树的根结点,判断该树是不是平衡二叉树。 如果某二叉树中任意结点的左右子树的高度相差不超过1,那么它就是一棵平衡二叉树。 分析:所谓平衡二...

2985
来自专栏Android相关

平衡二叉树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

3743
来自专栏用户画像

4.3.2 线索二叉树

二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点(除第一个和最后一个)都有一个直接前驱和直接后继。

992
来自专栏Bingo的深度学习杂货店

Q110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a hei...

2815
来自专栏WindCoder

二叉树的动态链式存储实现—C语言

2581

扫码关注云+社区