二叉查找树
本篇文章中，我们将介绍常见的树形结构及其常用操作的运算复杂度。
我们知道像家谱族谱、公司组织结构等都是以树结构的形式组织数据。例如公司组织结构图。
树（Tree）是由多个节点（Node）的集合组成，每个节点又有多个与其关联的子节点（Child Node）。子节点就是直接处于节点之下的节点，而父节点（Parent Node）则位于节点直接关联的上方。树的根（Root）指的是一个没有父节点的单独的节点。
所有的树都呈现了一些共有的性质：
- 只有一个根节点；
- 除了根节点，所有节点都有且只有一个父节点；
- 无环。将任意一个节点作为起始节点，都不存在任何回到该起始节点的路径。（正是前两个性质保证了无环的成立。）
树中使用的术语
- 根（Root）：树中最顶端的节点，根没有父节点。
- 子节点（Child）：节点所拥有子树的根节点称为该节点的子节点。
- 父节点（Parent）：如果节点拥有子节点，则该节点为子节点的父节点。
- 兄弟节点（Sibling）：与节点拥有相同父节点的节点。
- 子孙节点（Descendant）：节点向下路径上可达的节点。
- 叶节点（Leaf）：没有子节点的节点。
- 内节点（Internal Node）：至少有一个子节点的节点。
- 度（Degree）：节点拥有子树的数量。
- 边（Edge）：两个节点中间的链接。
- 路径（Path）：从节点到子孙节点过程中的边和节点所组成的序列。
- 层级（Level）：根为 Level 0 层，根的子节点为 Level 1 层，以此类推。
- 高度（Height）/深度（Depth）：树中层的数量。比如只有 Level 0,Level 1,Level 2 则高度为 3。
| 类别 | 树名称 |
|---|---|
| 二叉查找树（Binary Search Tree） | 二叉查找树，笛卡尔树，T 树 |
| 自平衡二叉查找树 （Self-balancing Binary Search Tree） |
AA 树，AVL 树，红黑树（Red-Black Tree），伸展树（Splay Tree） |
| B 树（B-Tree） | 2-3 树，2-3-4 树， B 树，B+ 树，B* 树 |
| 字典树（Trie-Tree） | 后缀树，基数树，三叉查找树，快速前缀树 |
| 空间数据分割树（Spatial Data Partitioning Tree） | R 树，R+ 树，R* 树， 线段树，优先 R 树 |
二叉树（Binary Tree）
二叉树（Binary Tree）是一种特殊的树类型，其每个节点最多只能有两个子节点。这两个子节点分别称为当前节点的左孩子（left child）和右孩子（right child）。
1
2
3
4
5
6
7
8
9
10
1 1
/ \ / \
2 3 2 3
/ \ / \ / \
4 5 4 5 6 7
\ \
6 7
\
8
(a) (b)
上图中，二叉树（a）包含 8 个节点，其中节点 1 是它的根节点。节点 1 的左孩子为节点 2，右孩子为节点 3。注意，并没有要求一个节点同时具有左孩子和右孩子。例如，二叉树（a）中，节点 4 就只有一个右孩子 6。此外，节点也可以没有孩子节点。例如，二叉树（b）中，节点 4、5、6、7 都没有孩子节点。
没有孩子的节点称为叶节点（Leaf Node），有孩子的节点则称为内节点（Internal Node）。如上图中，二叉树 （a） 中节点 6、8 为叶节点，节点 1、2、3、4、5、7 为内节点。
完全二叉树和满二叉树
满二叉树（Full Binary Tree）：一棵深度为 h，且有 \( 2^h - 1 \) 个节点称之为满二叉树。
A full binary tree is a tree in which every node other than the leaves has two children.
完全二叉树（Complete Binary Tree）：深度为 h，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 h 的满二叉树中，序号为 1 至 n 的节点对应时，称之为完全二叉树。
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
1
2
3
4
5
6
7
8
1 1
/ \ / \
2 3 2 3
/ \ / \ / \ / \
4 5 6 7 4 5 6 7
/
8
a. full tree b. complete tree
| 完全二叉树 | 满二叉树 | |
|---|---|---|
| 总节点数 k | \( 2^h-1 <= k < 2^h - 1 \) | \( k = 2^h - 1 \) |
| 树高 h | \( h = \mathbf{log}_{2}k + 1 \) | \( h = \mathbf{log}_{2}(k + 1) \) |
我们已经了解了数组是将元素连续地排列在内存当中，而二叉树却不是采用连续的内存存放。实际上，通常 BinaryTree 类的实例仅包含根节点（Root Node）实例的引用，而根节点实例又分别指向它的左右孩子节点实例，以此类推。所以关键的不同之处在于，组成二叉树的节点对象实例可以分散到 CLR 托管堆中的任何位置，它们没有必要像数组元素那样连续的存放。
如果要访问二叉树中的某一个节点，通常需要逐个遍历二叉树中的节点，来定位那个节点。它不象数组那样能对指定的节点进行直接的访问。所以查找二叉树的渐进时间是线性的 O(n)，在最坏的情况下需要查找树中所有的节点。也就是说，随着二叉树节点数量增加时，查找任一节点的步骤数量也将相应地增加。
那么，如果一个二叉树的查找时间是线性的，定位时间也是线性的，那相比数组来说到底哪里有优势呢？毕竟数组的查找时间虽然是线性 O(n)，但定位时间却是常量 O(1) 啊？的确是这样，通常来说普通的二叉树确实不能提供比数组更好的性能。然而，如果我们按照一定的规则来组织排列二叉树中的元素时，就可以很大程度地改善查询时间和定位时间。
二叉查找树
二叉查找树（BST：Binary Search Tree） 也称二叉搜索树、有序二叉树（ordered binary tree），排序二叉树（orted binary tree），是指一棵空树或者具有下列性质的二叉树，对于任意一个节点 n:
- 其左子树（left subtree）下的每个后代节点（descendant node）的值都小于节点 n 的值；
- 其右子树（right subtree）下的每个后代节点的值都大于节点 n 的值;
- 没有键值相等的节点
二叉查找树的性质使得其还有一个特性就是”中序遍历”可以让结点有序(升序)。
所谓节点 n 的子树，可以将其看作是以节点 n 为根节点的树。子树的所有节点都是节点 n 的后代，而子树的根则是节点 n 本身。
下图中展示了两个二叉树。二叉树（b）是一个二叉查找树（BST），它符合二叉查找树的性质规定。而二叉树（a），则不是二叉查找树。因为节点 10 的右孩子节点 8 小于节点 10，但却出现在节点 10 的右子树中。同样，节点 8 的右孩子节点 4 小于节点 8，但出现在了它的右子树中。无论是在哪个位置，只要不符合二叉查找树的性质规定，就不是二叉查找树。例如，节点 9 的左子树只能包含值小于节点 9 的节点，也就是 8 和 4。
1
2
3
4
5
6
7
8
9
10
7 7
/ \ / \
3 9 3 11
/ \ / \ / \
1 10 1 5 10 15
\ \ /
2 8 4
\
4
(a) (b)
从二叉查找树的性质可知，BST 各节点存储的数据必须能够与其他的节点进行比较。给定任意两个节点，BST 必须能够判断这两个节点的值是小于、大于还是等于。
操作
插入节点
我们不仅需要了解如何在二叉查找树中查找一个节点，还需要知道如何在二叉查找树中插入和删除一个节点。
1
2
3
4
5
6
7
20 --> 20 ---> 20 ----> 20
/ / \ / \
15 15 25 15 25
/ \ \
10 18 30
\
12
当向树中插入一个新的节点时，该节点将总是作为叶子节点。所以，最困难的地方就是如何找到该节点的父节点。类似于查找算法中的描述，我们将这个新的节点称为节点 n，而遍历的当前节点称为节点 c。开始时，节点 c 为 BST 的根节点。则定位节点 n 父节点的步骤如下：
- 如果节点 c 为空，则节点 c 的父节点将作为节点 n 的父节点。如果节点 n 的值小于该父节点的值，则节点 n 将作为该父节点的左孩子；否则节点 n 将作为该父节点的右孩子。
- 比较节点 c 与节点 n 的值。
- 如果节点 c 的值与节点 n 的值相等，则说明用户在试图插入一个重复的节点。解决办法可以是直接丢弃节点 n，或者可以抛出异常。
- 如果节点 n 的值小于节点 c 的值，则说明节点 n 一定是在节点 c 的左子树中。则将父节点设置为节点 c，并将节点 c 设置为节点 c 的左孩子，然后返回至第
1步。 - 如果节点 n 的值大于节点 c 的值，则说明节点 n 一定是在节点 c 的右子树中。则将父节点设置为节点 c，并将节点 c 设置为节点 c 的右孩子，然后返回至第
1步。
当合适的节点找到时，该算法结束。从而使新节点被放入 BST 中成为某一父节点合适的孩子节点。
1
2
3
4
5
6
7
8
// 有如下的bst， 我们需要插入节点 62
90 62
/ \
50 150
/ \
20 75
/ \
5 25
1
2
3
4
5
6
7
8
9
// 首先将要插入的节点（62）与根节点（90）进行比较
// 由于 62 < 90， 所以 62 应该被插入到根节点（90）的左侧子树中
90 <--------------------> 62
/ \
50 150
/ \
20 75
/ \
5 25
1
2
3
4
5
6
7
8
9
// 接下来我们比较 62 和左侧子节点 (50)
// 62 > 50 ,所以 62 应该在50的右侧子树中
90
/ \
62 <-> 50 150
/ \
20 75
/ \
5 25
1
2
3
4
5
6
7
8
9
// 下一步比较 62 和 右侧子节点（75）
// 75 > 62 ，所以62 一定在 75 的左侧子树中
90
/ \
50 150
/ \
20 75 <--------------> 62
/ \
5 25
1
2
3
4
5
6
7
8
9
// 由于65 的左侧子树不存在，所以我们找到了 62 应该在的位置
// 剩下的就是我们将 62 节点设置为75 的子节点
90
/ \
50 150
/ \
20 75
/ \ /
5 25 62
BST 的插入算法的复杂度与查找算法的复杂度是一样的：最佳情况是 \( O(\mathbf{log}_{2}n) \)，而最坏情况是 O(n)。因为它们对节点的查找定位策略是相同的。
查找
对于二叉查找树，最常见的操作就是查找树中的某个关键字。除了Search操作外，二叉查找树还能支持如 Minimum（最小值）、Maximum（最大值）、Predecessor（前驱）、Successor（后继）等查询。对于高度为 h 的树，这些操作都可以在 Θ(h) 时间内完成。
查找值
BST 的查找是从根结点开始，若二叉树非空，将给定值与根结点的关键字比较，若相等，则查找成功；若不等，则当给定值小于根结点关键字时，在根结点的左子树中查找，否则在根结点的右子树中查找。显然，这是一个递归的过程。
总结来说，我们使用的查找算法过程如下：
假设我们要查找节点 n，从 BST 的根节点开始。算法不断地比较节点值的大小直到找到该节点，或者判定不存在。每一步我们都要处理两个节点：树中的一个节点，称为节点 c，和要查找的节点 n，然后并比较 c 和 n 的值。开始时，节点 c 为 BST 的根节点。然后执行以下步骤：
- 如果 c 值为空，则 n 不在 BST 中；
- 比较 c 和 n 的值；
- 如果值相同，则找到了指定节点 n；
- 如果 n 的值小于 c，那么如果 n 存在，必然在 c 的左子树中。回到第
1步，将 c 的左孩子作为 c； - 如果 n 的值大于 c，那么如果 n 存在，必然在 c 的右子树中。回到第
1步，将 c 的右孩子作为 c；
通过 BST 查找节点，理想情况下我们需要检查的节点数可以减半。如下图中的 BST 树，包含了 15 个节点。从根节点开始执行查找算法，第一次比较决定我们是移向左子树还是右子树。对于任意一种情况，一旦执行这一步，我们需要访问的节点数就减少了一半，从 15 降到了 7。同样，下一步访问的节点也减少了一半，从 7 降到了 3，以此类推。
1
2
3
4
5
6
7
90
/ \
50 150
/ \ / \
20 75 95 175
/ \ / \ / \ / \
5 25 66 80 92 111 166 200
根据这一特点，查找算法的时间复杂度应该是 \( O(\mathbf{log}_{2}n) \)，简写为 O(lg n)。我们在文章《算法复杂度分析》中有一些关于时间复杂度的描述。可知，\( \mathbf{log}_{2}n = y \)，相当于 \( 2^y = n \)。即，如果节点数量增加 n，查找时间只缓慢地增加到 \( \mathbf{log}_{2}n \)。下图中显示了 \( O(\mathbf{log}_{2}n) \) 和线性增长 O(n) 的增长率之间的区别。时间复杂度为 \( O(\mathbf{log}_{2}n) \) 的算法运行时间为下面那条线。
从上图可以看出，\( O(\mathbf{log}_{2}n) \) 曲线几乎是水平的，随着 n 值的增加，曲线增长十分缓慢。举例来说，查找一个具有 1000 个元素的数组，需要查询 1000 个元素，而查找一个具有 1000 个元素的 BST 树，仅需查询不到10 个节点（\( \mathbf{log}_{2}1024 = 10 \)）。
而实际上，对于 BST 查找算法来说，其十分依赖于树中节点的拓扑结构，也就是节点间的布局关系。下图描绘了一个节点插入顺序为 20, 50, 90, 150, 175, 200 的 BST 树。这些节点是按照递升顺序被插入的，结果就是这棵树没有广度（Breadth）可言。也就是说，它的拓扑结构其实就是将节点排布在一条线上，而不是以扇形结构散开，所以查找时间也为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
20
\
50
\
90
\
150
\
175
\
200
当 BST 树中的节点以扇形结构散开时，对它的插入、删除和查找操作最优的情况下可以达到亚线性的运行时间 \( O(\mathbf{log}_{2}n) \)。因为当在 BST 中查找一个节点时，每一步比较操作后都会将节点的数量减少一半。尽管如此，如果拓扑结构像上图中的样子时，运行时间就会退减到线性时间 O(n)。因为每一步比较操作后还是需要逐个比较其余的节点。也就是说，在这种情况下，在 BST 中查找节点与在数组（Array）中查找就基本类似了。
因此，BST 算法查找时间依赖于树的拓扑结构。最佳情况是 O(log2n)，而最坏情况是 O(n)。
最大值与最小值
由二叉查找树的性质可知，最左下结点即为关键字最小的结点，最右下结点即为关键字最大的结点。此过程无需比较，只需要沿着最左和最右的路径查找下去，直到遇到 NULL 为止。
前驱与后继
给定一个二叉查找树的结点，求出它在中序遍历中的前驱与后继。如果所有的关键字均不相同，则某结点 x 的后继是：
- 若结点 x 的右子树不为空，则 x 的后继就是它的右子树中关键字值最小的结点；
- 若结点 x 的右子树为空，为了找到其后继，从结点 x 开始向上查找，直到遇到一个祖先结点 y，它的左儿子也是结点 x 的祖先，则结点 y 就是结点 x 的后继。
1
2
3
4
5
6
7
7
/ \
3 11
/ \ / \
1 5 10 15
/
4
如上 7 的后继为 10, 是由于 10 的 7 的右子树中最左边的节点，即最小节点。
如下 节点 5 的后继为 7。 是由于 7 的左子节点 3 是 5 的父节点。
求前驱（predecessor）的过程对称，对于某个结点 x ，它的前驱是：
- 若结点 x 的左子树不为空，则 x 的前驱是它的左子树中关键字值最大的结点；
- 若结点 x 的左子树为空，为了找到其前驱，从结点 x 开始向上查找，直到遇到一个祖先结点 y，它的右儿子也是结点 x 的祖先，则结点 y 就是结点 x 的前驱。
如上， 节点 7 的前驱节点为 5。 是由于 5 是 7 左子节点中最右边的节点，即最大节点
如上， 节点 10 的前驱节点为 7， 是由于 7 的右子节点 11 是 节点 10 的父节点。
删除节点
从 BST 中删除节点比插入节点难度更大。因为删除一个非叶子节点，就必须选择其他节点来填补因删除节点所造成的树的断裂。如果不选择节点来填补这个断裂，那么就违背了 BST 的性质要求。
删除节点算法的第一步是定位要被删除的节点，这可以使用前面介绍的查找算法，因此运行时间为 \(O(\mathbf{log}_{2}n) \)。接着应该选择合适的节点来代替删除节点的位置，它有以下情况需要考虑：
- 若被删除结点 z 是叶子节点，则直接删除，不会破坏二叉排序树的性质；
- 情况 1： 只有一个子节点，直接用子节点代替当前节点。二叉查找树的性质保证了被删除节点的子树必然符合二叉查找树的性质。因此子树的值要么都大于，要么都小于被删除节点的父节点的值，这取决于被删除节点是左孩子还是右孩子。因此用被删除节点的子树来替代被删除节点，是完全符合二叉搜索树的性质的。
- 情况 2： 如果被删除节点的右孩子没有左孩子，那么这个右孩子被用来替换被删除节点。因为被删除节点的右孩子都大于被删除节点左子树的所有节点，同时也大于或小于被删除节点的父节点，这同样取决于被删除节点是左孩子还是右孩子。因此，用右孩子来替换被删除节点，符合二叉查找树的性质。
- 情况 3： 如果被删除节点的右孩子有左孩子，就需要用被删除节点右孩子的左子树中的最下面的节点来替换它，就是说，我们用被删除节点的右子树中最小值的节点来替换。
1
2
3
4
5
6
7
8
9
10
// case 1
// 假设需要删除节点 50
// 由于 50 没有右子节点， 所以可以直接用左子节点代替
90 90
/ \ / \
---> 50 150 20 150
/ / \
20 5 25
/ \
5 25
1
2
3
4
5
6
7
8
9
10
// case 2
// 假设想删除节点 150
// 由于150 的右子节点没有左子节点, 所以我们直接用 右子节点代替 150 节点
90 90
/ \ / \
50 150 <---- 50 175
/ / \ / /
20 125 175 20 125
/ \ \ / \ \
5 25 140 5 25 140
1
2
3
4
5
6
7
8
9
10
11
12
// case 3
// 假设我们想删除 节点 50
// 由于 节点（50） 的右子节点包含左子节点。我们需要找到 节点（50）的右子节点中最左端的后代节点。这个最左端的后代节点就是节点（50）的右侧子树中的最小节点。在本例中是 节点 66
90 90
/ \ / \
----> 50 150 66 150
/ \ / \
20 75 20 75
/ \ / \ / / \
5 25 66 80 5 68 80
\
68
我们知道，在 BST 中，最小值的节点总是在最左边，最大值的节点总是在最右边。因此替换被删除节点右子树中最小的一个节点，就保证了该节点一定大于被删除节点左子树的所有节点。同时，也保证它替代了被删除节点的位置后，它的右子树的所有节点值都大于它。因此这种选择策略符合二叉查找树的性质。
对于 情况2 和 情况3 还可以用另外一种角度来解释:
首先可以这么想象，如果我们要删除一个数组的元素，那么我们在删除后会将其后面的一个元素顶到被删除的位置，如图
1
2
X <---
6 | 5 | 1 | 2 | 9 | 8 --> 6 | 5 | 1 | 9 | 8
那么二叉树操作同样也是一样，我们根据”中序遍历“找到要删除结点的后一个结点，然后顶上去就行了，原理跟”数组”一样一样的。情况2和情况3 本质上都是在寻找右子节点中的最小值。也就是中序遍历时删除节点的下一个值。
即直接用删除节点的后继节点替代即可。
1
2
3
4
5
6
7
20 20
/ \ / \
(X)15 25 ---> 18 25
/ \ \ / \ \
10 18 30 10 18(X) 30
\ \
12 12
和查找、插入算法类似，删除算法的运行时间也与 BST 的拓扑结构有关，最佳情况是 \( O(\mathbf{log}_{2}n) \)，而最坏情况是 O(n)。
遍历节点
对于线性的连续的数组来说，遍历数组采用的是单向的迭代法。从第一个元素开始，依次向后迭代每个元素。而 BST 则有三种常用的遍历方式：
- 前序遍历（Perorder traversal）
- 中序遍历（Inorder traversal）
- 后序遍历（Postorder traversal）
当然，这三种遍历方式的工作原理是类似的。它们都是从根节点开始，然后访问其子节点。区别在于遍历时，访问节点本身和其子节点的顺序不同。
1
2
3
4
5
6
7
8
90
/ \
50 150
/ \ / \
20 75 95 175
/ \ / \ / \ / \
5 25 66 80 92 111 166 200
前序遍历（Perorder traversal）
前序遍历从当前节点（节点 c）开始访问，然后访问其左孩子，再访问右孩子。开始时，节点 c 为 BST 的根节点。算法如下：
- 访问节点 c；
- 对节点 c 的左孩子重复第
1步； - 对节点 c 的右孩子重复第
1步；
则上图中树的遍历结果为：90, 50, 20, 5, 25, 75, 66, 80, 150, 95, 92, 111, 175, 166, 200。
中序遍历（Inorder traversal）
中序遍历是从当前节点（节点 c）的左孩子开始访问，再访问当前节点，最后是其右节点。开始时，节点 c 为 BST 的根节点。算法如下：
- 访问节点 c 的左孩子；
- 对节点 c 重复第
1步； - 对节点 c 的右孩子重复第
1步。
则上图中树的遍历结果为：5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200。
后序遍历（Postorder traversal）
后序遍历首先从当前节点（节点 c）的左孩子开始访问，然后是右孩子，最后才是当前节点本身。开始时，节点 c 为 BST 的根节点。算法如下：
- 访问节点 c 的左孩子；
- 对节点 c 的右孩子重复第
1步； - 对节点 c 重复第
1步； 则上图中树的遍历结果为：5, 25, 20, 66, 80, 75, 50, 92, 111, 95, 166, 200, 175, 150, 90。
代码实现
插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 插入：将关键字k插入到二叉查找树
*/
int BST_Insert(BSTree &T, int k, Node* parent=NULL)
{
if(T == NULL)
{
T = (BSTree)malloc(sizeof(Node));
T->key = k;
T->left = NULL;
T->right = NULL;
T->parent = parent;
return 1; // 返回1表示成功
}
else if(k == T->key)
return 0; // 树中存在相同关键字
else if(k < T->key)
return BST_Insert(T->left, k, T);
else
return BST_Insert(T->right, k, T);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* 非递归插入：将关键字k插入到二叉查找树
*/
int BST_Insert_NonRecur(BSTree &T, int k)
{
Node* pre = NULL; // 记录上一个结点
Node* t = T;
while(t != NULL)
{
pre = t;
if(k < t->key)
t = t->left;
else if(k > t->key)
t = t->right;
else
return 0;
}
Node* node = (Node*)malloc(sizeof(Node));
node->key = k;
node->left = NULL;
node->right = NULL;
node->parent = pre;
if(pre == NULL)
T = node;
else
{
if(k < pre->key)
pre->left = node;
else
pre->right = node;
}
return 1;
}
查找
查找值
1
2
3
4
5
6
7
8
9
10
11
12
/**
* 递归查找：返回指向包含关键字k的结点的指针
*/
Node* BST_Search(BSTree T, int k)
{
if(T == NULL || k == T->key)
return T;
if(k < T->key)
return BST_Search(T->left, k);
else
return BST_Search(T->right, k);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 非递归查找：返回指向包含关键字k的结点的指针
*/
Node* BST_Search_NonRecur(BSTree T, int k)
{
while(T != NULL && k != T->key)
{
if(k < T->key)
T = T->left;
else
T = T->right;
}
return T;
}
最大值与最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 最小值：查找二叉查找树中关键字最小的结点
*/
Node* BST_Minimum(BSTree T)
{
while(T->left != NULL)
T = T->left;
return T;
}
/**
* 最大值：查找二叉查找树中关键字最大的结点
*/
Node* BST_Maximum(BSTree T)
{
while(T->right != NULL)
T = T->right;
return T;
}
前驱与后继
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 后继：查找给定结点在中序遍历中的后继结点
*/
Node* BST_Successor(Node* node)
{
if(node->right != NULL)
return BST_Minimum(node->right);
Node* p = node->parent;
while(p!=NULL && p->right == node)
{
node = p;
p = p->parent;
}
return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 前驱：查找给定结点在中序遍历中的前驱结点
*/
Node* BST_Predecessor(Node* node)
{
if(node->left != NULL)
return BST_Maximum(node->left);
Node* p = node->parent;
while(p!=NULL && p->left == node)
{
node = p;
p = p->parent;
}
return p;
}
删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
void BST_Delete(BSTree &T,Node* z)
{
if(z->left == NULL && z->right == NULL)
{
if(z->parent != NULL)
{
if(z->parent->left == z)
z->parent->left = NULL;
else
z->parent->right = NULL;
}
else
{
T = NULL; // 只剩一个结点的情况
}
free(z);
}
else if(z->left != NULL && z->right == NULL)
{
z->left->parent = z->parent;
if(z->parent != NULL)
{
if(z->parent->left == z)
z->parent->left = z->left;
else
z->parent->right = z->left;
}
else
{
T = z->left; // 删除左斜单支树的根结点
}
free(z);
}
else if(z->left == NULL && z->right != NULL)
{
z->right->parent = z->parent;
if(z->parent != NULL)
{
if(z->parent->left == z)
z->parent->left = z->right;
else
z->parent->right = z->right;
}
else
{
T = z->right; // 删除右斜单支树的根结点
}
free(z);
}
else
{
Node* s = BST_Successor(z);
z->key = s->key; // s的关键字替换z的关键字
BST_Delete(T, s); // 转换为第一或第二种情况
}
}
构造随机树
二叉查找树可以实现任何一种基本的动态集合操作，且各基本操作的运行时间都是 Θ(h)。当树的高度较低时，这些操作执行的较快；但是，当树的高度较高时，性能会变差。比如，如果各元素是按严格增长的顺序插入的，那么构造出来的树就是一个高度为 n-1 的链。 为了尽量减少这种最坏情况的出现，我们可以随机地构造二叉查找树，即随机地将各关键字插入一棵初始为空的树来构造 BST。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//#include <cstdlib>
//#include <ctime>
/**
* 随机构造二叉查找树
*/
void Create_BST(BSTree &T, int arr[], int n)
{
T = NULL;
// 随机遍历数组，进行插入操作
srand(time(NULL));
for(int i=n-1; i>=0; --i)
{
int j = rand() % (i+1);
BST_Insert(T, arr[j]);
swap(arr[j], arr[i]);
}
}
void swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}
