数据结构之二叉搜索树

马谦马谦马谦 数据结构和算法评论1,096字数 2455阅读 8 分 11 秒阅读模式

一、二叉搜索树

1.1 什么是二叉搜索树

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

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

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

数据结构之二叉搜索树-图片1

其中 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

数据结构之二叉搜索树-图片2

找最小的元素只要一直在左子节点中查找,直到节点的左节点是 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

数据结构之二叉搜索树-图片3

求前驱节点的过程:

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

求后继节点的过程:

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

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

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

2.4 插入节点 (INSERT)

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

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

数据结构之二叉搜索树-图片4

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 删除节点只有一个儿子

只有左子节点的情况

数据结构之二叉搜索树-图片5

只有右子节点的情况

数据结构之二叉搜索树-图片6

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

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

对应情况:

数据结构之二叉搜索树-图片7

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

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

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

情况对应下图:

数据结构之二叉搜索树-图片8

此时要做的两步操作:

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

2.5.4 删除节点的代码

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

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

  最后更新:2019-12-5
马谦马谦马谦
  • 本文由 马谦马谦马谦 发表于 2018 年 11 月 29 日 10:43:49
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/binary-search-tree.html
二叉树的后序遍历 数据结构和算法

二叉树的后序遍历

一、后序遍历 后序遍历逻辑:优先访问左、右子节点,然后访问当前节点。 一个后序遍历的示例,它的后序遍历结果为 [4, 2, 5, 6, 3, 1]: 二、非递归实现 后序遍历的非递归实现比前序和中序的非...
二叉树的中序遍历 数据结构和算法

二叉树的中序遍历

一、中序遍历 中序遍历过程:先访问左子节点,然后访问当前节点,最后访问右子节点。 以下试一次中序遍历过程: 二、非递归实现 非递归方式遍历依赖栈来实现,因为要先访问子节点,然后访问父节点,因此必须要有...
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证