数据结构之二叉搜索树

马谦马谦马谦 2018年11月29日10:43:49 发表评论
文章最后编辑于:2019-4-29 10:46:32

一、二叉搜索树

1.1 什么是二叉搜索树

算法导论中对二叉搜索树(Binary Search Tree, 简称BST)的定义:

设x是二叉搜索树中的一个节点,如果y是x左子树中的一个节点,那么y.key<=x.key。如果y是x右子树中的一个节点,那么y.key>=x.key。

以下两棵树就是二叉搜索树:

数据结构之二叉搜索树

其中a是一个包含6个节点,高度为2的二叉搜索树。b是一个包含相同关键字、高度为4的低效二叉树。

注意:树中包含了两个相同的节点5,在实际用途中,很少把相同的关键字放到二叉搜索树中。

二叉搜索树主要的操作:

  • SEARCH:查找某个节点在树中的位置
  • MINIMUM:求以指定节点为根的树中的最小元素
  • MAXIMUM:求以指定节点为根的树中的最大元素
  • PREDECESSOR:求指定节点的前驱节点
  • SUCCESSOR:求指定节点的后继节点
  • INSERT:在树中插入节点
  • DELETE:删除节点

定理:二叉搜索树中的以上各个操作都是在O(h)时间内完成。

1.2 树节点定义

二叉搜索树的节点需要包含以下元素:

  • 节点的键值,也就是key
  • 父节点和左右子节点的指针

假设key值类型为int,那么树节点的结构应该为:

二、二叉树操作

2.1 查找操作( SEARCH)

通过二叉搜索树的性质很容易得到查找算法:从树根开始查找,沿着树的路径一直向下。对每个遇到的节点x,比较关键字k和x.key,如果两个关键字相等,查找终止。如果k小于x.key,在x的左子树中继续查找。否则就在x的右子树中继续查找。

伪代码如下(来自《算法导论》):

上面采用了递归的方法来进行查找,递归最明显的特点就是简单,代码量小。但是在树高度很高时候,递归就会产生巨大的内存消耗和更多的CPU消耗,因为要频繁对函数及参数压栈,并且函数中栈是有大小限制的,不能无限递归。

大部分时候建议使用非递归查找,非递归查找的伪代码实现为:

非递归对应的C语言描述:

2.2 求最大元素(MAXIMUM)和最小元素(MINIMUM)

根据二叉树的性质可知:最小的节点一定是最左边的节点,最大的节点一定是最右边的节点。

例如对下面这个二叉树而言,最小的元素是2,最大的元素是20

数据结构之二叉搜索树

找最小的元素只要一直在左子节点中查找,直到节点的左节点是NULL为止。相反,找最大的元素,只要在节点的右节点中查找,直到右节点是NULL为止。

2.3 求前驱(PREDECESSOR)和后继(SUCCESSOR)

节点x的前驱节点是指中序遍历中顺序在x之前的元素,节点x的后继节点指中序遍历中顺序在x之后的元素。

以2.3节中的二叉树为例,其中序遍历的结果为:2 3 4 6 7 9 13 15 17 18 20。对于元素6而言,它的前驱节点是4,后继节点是7

数据结构之二叉搜索树

求前驱节点的过程:

  • 如果节点有左子节点,那么前驱节点一定是左子树中的最大元素。例如6的前驱是415的前驱是13
  • 如果节点没有左子节点,那么它的前驱就是以它或者以它任一祖先为右儿子的节点,例如上图中节点9的前驱是7,节点7的前驱是6

求后继节点的过程:

  • 如果节点有右子节点,那么后继节点一定是右子树中最小的元素。例如15的后继节点是1718的后继节点是20
  • 如果节点没有右子节点,那么它的后继就是以它或者以它任一祖先为左儿子的节点,例如上图中的13的后继节点是1517的后继节点是18

可以得到的一个结论:树中最小的元素没有前驱节点,树中最大的元素没有后继节点。

求前驱节点和后继节点的C语言描述:

2.4 插入节点(INSERT)

插入节点和搜索节点的工作方式一样,先根据元素大小找到合适的位置,然后作为子节点插入,每次插入的节点必定是叶子节点

例如在下面的树中插入元素13,首先要找到它的父节点15,然后作为它的左子节点插入:

数据结构之二叉搜索树

C语言实现:

2.5 删除节点(DELETE)

2.5.1 删除节点的基本操作

相对来说,删除节点要比插入节点复杂许多,它有三种不同的情况:

  1. 如果待删除节点z没有孩子节点,那么直接把它删除,修改父节点指针即可完成。
  2. 如果待删除节点z只有一个孩子,那么将这个孩子替换到z的位置,修改z的父节点指针,指向z的子节点。
  3. 如果待删除节点z有两个孩子,找到z的后继节点y,让y占据z的位置,同时还要让y的右子节点(如果有的话)占据y的位置。

前面两种情况相对简单,甚至可以被合并成一种情况。而第三种情况最为复杂,它还能继续向下分解:

  • z的后继节点y就是z的右子节点
  • z的后继节点y不是z的右子节点,这种情况下可以推断出y一定不含左子节点,但此时y的右子节点x又有两种情况:
    • x为空
    • x不为空

下面分别对以上几种情况进行讨论:

2.5.2 删除节点只有一个儿子

只有左子节点的情况

数据结构之二叉搜索树

只有右子节点的情况

数据结构之二叉搜索树

不管是左儿子,还是右儿子,直接替换原删除节点即可。

2.5.3 删除节点有两个儿子且后继节点是右儿子

对应情况:

数据结构之二叉搜索树

只需要把z的位置替换成y就可以了。

2.5.4 删除节点有两个儿子且后继节点不是右儿子

后继节点y不是z的右儿子,那么y必定没有左儿子(如果y有左儿子的话,那么z的后继节点肯定就是y的左儿子而不会是y)。

情况对应下图:

数据结构之二叉搜索树

此时要做的两步操作:

  1. y的右儿子(不管是否为NULL)替换成y
  2. y替换成z

2.5.4 删除节点的代码

添加一个辅助操作TRANSPLANT,英文意思是移植,表示把一个节点用另一个节点代替:

然后在TREE_DELETE操作中调用TRANSPLANT完成删除操作:

本文共执行43次查询,耗时0.292秒!
马谦马谦马谦

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: