数据结构与算法（九）—— 二叉树结构及其实现和应用

骑猪看日落 2023-07-23 08:59 53阅读 0赞

因为树结构中的内容较多，所以分开介绍。这篇主要介绍二叉树。

**目录**

一. 霍夫曼树(Huffman  Tree)

1.1 霍夫曼树定义

1.2 霍夫曼树的构造

1.3 霍夫曼算法描述

1.4 霍夫曼树的应用

1.4.1 霍夫曼编码

1.4.2 其它

二. 二叉搜索树

2.1 二叉搜索树定义特征

2.2 二叉搜索树的原理

2.3 查找二叉搜索树

2.3.1 查找

2.3.2 最小关键字元素和最大关键字元素

2.3.3 后继和前驱

2.4 插入和删除

2.4.1 插入

2.4.2  删除

2.5 随机构建二叉搜索树

5.6 二叉树的使用及问题

三. 平衡二叉搜索树(AVL树)

四. 红黑树

4.1 红黑树定义性质

4.2 红黑树操作

4.3 红黑树（RBT）与AVL树的区别

4.4 红黑树的应用

--------------------

# 一. 霍夫曼树(Huffman  Tree) #

举个例子说明下。现在考试的结果都以百分制来表示学科的成功。但这带来了一个弊端，那就是很容易让学生、家长和老师以分取人，这样就让分数代表了一切。这样也容易间接导致92与95这种分差很接近的学生受到不公平的待遇，这样自然是不公平的。于是在如今提倡素质教育的背景下，很多学科，特别是小学的学科成绩很多改作了优秀、良好、中等、及格和不及格这样的评测结果，不再通报具体的学科分数。

但这对老师而言，在对席卷评分时，显然不能凭感觉给出优良或及格等，必须要给出每个评测结果对应的分数范围。这样老师才好按照试卷的分数，根据每个评测结果的范围对照，最后给出评测试结果。如下代码（a 表示分数，b 表示评测结果）。

if (a < 60) {
                b = "不及格";
            } else if (a >= 60 && a < 70) {
                b = "及格";
            } else if (a >= 70 && a < 80) {
                b = "中等";
            } else if (a >= 80 && a < 90) {
                b = "良好";
            } else if (a >= 90 && a <= 100) {
                b = "优秀";
            }

上面的逻辑没有问题，也很简单。可是假设有一种情况：一张好的试卷应该是让学生成绩大部分处于中等或良好的范围，优秀和不及格都应该比较少。上面这样的程序，使得所有的成绩都需要先判断是否及格，再逐级而上得到结果。当输入量很大的时候，这个算法的效率还是有问题的。虽然就试卷来说不一定有这假设，但在生活中其实是有不少这样的情况的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70][]

如下表所示，70分以上的学生大约占到了总数的85%，但这些都需要经过3次以上的判断才可以得出结果，显然不太合适。虽然也可以通过调整代码来优化，但在遇到其它的一些情况时，并不是屡试不爽。

![20200110174259748.png][]

仔细观察后发现，中等成绩（70~79）比例最高，其实是良好成功，不及格所占的比例最少。把上面的结果以二叉树重新进行分配，如下图所示。这样来看效率是提高了一些。那到底提高了多少呢？这样的二叉树又如何设计出来的？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 1][]

## 1.1 霍夫曼树定义 ##

先把下面的两棵二叉树简化成叶结点带权的二叉树。其中A表示不及格、B表示及格、C表示中等、D表示良好、E表示优秀。每个叶结点的分支线上数字刚好就是分数在这个评测范围内的占比。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 2][]

**路径长度**

从树中的一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做**路径长度**。上图中的二叉树a中，根结点到结点D的路径长度就是4，上图中的二叉树b中根结点到结点D的路径长度为2。一棵**树的路径长度**就是从树根结点到每一个结点的路径长度之和。二叉树a的树路径长度为1 + 1 + 2 + 2 + 3 + 3 + 4 +4 = 20，二叉树b的路径长度为 1 + 1 + 2 + 2 + 2 + 2 + 3 + 3 = 16。若根结点的层数为1，则从根结点到第 d 层结点的路径长度为 d-1。

**带权的路径长度**

若考虑到带权的结点（这里的权可以理解为赋给树中每个结点的一种带有某种含义的数值），**结点的带权路径长度**为从该结点到树根结点之间的路径长度与结点上权的乘积。树的带权路径长度为树中的所有叶结点的带权路径长度之和。假设有 n 个权值｛![w\_\{1\},w\_\{2\},...,w\_\{n\}][w_1_w_2_..._w_n]｝，构造一棵有 n 个叶结点的二叉树，每个叶结点带权为![w\_\{k\}][w_k]，每个叶结点的带权路径长度为路径长长 \* 权，，其中带权路径长度WPL最小的二叉树称做霍夫曼树(Huffman  Tree)，也称赫夫曼树、哈夫曼树、最优二叉树。霍夫曼树也是一种有序树。

根据上面的定义描述，上图中二叉树 a 的WPL = 5\*1 + 15\*2 + 40\*3 + 30\*4 + 10 \* 4 = 315，二叉树 b 的WPL = 5\*3 + 15\*3 + 40\*2 + 30\*2 + 10\*2 = 220。从WPL的结果意味着：若需要知道100个学生百分制成绩的评测结果，用二叉树 a 的判断方法需要做315次比较；而二叉树 b 则只需要做220次判断。从判断次数来看，差的比较大，接近1/3，由引可见性能提高的不只是一点点。

## 1.2 霍夫曼树的构造 ##

下面来看看二叉树 b 是如何构造出来的。根据上面的成绩表构造霍夫曼树 的步骤如下：

*  1. 先把有权值的叶结点按照从小到大的顺序排列成一个有序序列，即A5，E10，B15，D30，C40；
 *  2. 然后取两个权值最小的结点作为一个新结点![N\_\{1\}][N_1]的两个子结点，权值相对较小的是左子结点。这里结点A为![N\_\{1\}][N_1]的左子结点，E为![N\_\{1\}][N_1]的右子结点。结点![N\_\{1\}][N_1]的权值为5 + 10 = 15。如下图的左图所示。

![202001101842089.png][]

*  3. 将A与E两个结点用![N\_\{1\}][N_1]替换（即不要A与E了，只要![N\_\{1\}][N_1]），插入到有序序列中，保持从小到大的排列顺序。即：![N\_\{1\}][N_1]15，B15，D30，C40；
 *  4. 重复步骤2，将结点![N\_\{1\}][N_1]与B作为一个新结点![N\_\{2\}][N_2]的两个子结点，结点![N\_\{2\}][N_2]的权值为15+ 15 = 30。如上图的右图所示；
 *  5. 将![N\_\{1\}][N_1]结点与B结点替换为![N\_\{2\}][N_2]，然后插入到有序序列中，保持从小到大的排列顺序。即：![N\_\{2\}][N_2]30，D30，C40；
 *  6. 重复步骤2，将结点![N\_\{2\}][N_2]与D作为一个新结点![N\_\{3\}][N_3]的两个子结点，结点![N\_\{3\}][N_3]的权值为30 + 30 = 60。如下图的左图所示；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 3][]

*  7. 将结点![N\_\{2\}][N_2]和D替换为![N\_\{3\}][N_3]，然后插入到有序序列中，保持从小到大的排列顺序，即C40，![N\_\{3\}][N_3]60；
 *  8. 重复步骤2，将结点C与![N\_\{3\}][N_3]作为一个新结点T的两个子结点，如上图的右图所示。由于T即是根结点，到此完成霍夫曼树的构造（此时只有一棵树了）。

上图中的右图，其二叉树的带权路径长度WPL = 40\*1 + 30\*2 + 15\*3 + 10\*4 + 5\*4 = 205。比上面的二叉树 b 的WPL值220还少了15，由此来看上图中右图的二叉树才是最优的霍夫曼树。

但现实往往比理想要复杂很多。刚构造的优霍夫曼树树，由于每次判断都要进行两次比较（如根结点就是a >= 70 && a < 80，两次比较后才能得到结果），所以从总体性能上看，反而不如下图的高。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 4][]

## 1.3 霍夫曼算法描述 ##

通过上面的构造步骤，可以得出霍夫曼树的算法描述。

1.  根据给定的 n 个权值｛![w\_\{1\},w\_\{2\},...,w\_\{n\}][w_1_w_2_..._w_n]｝构成的 n 棵二叉树的集合 F = ｛![T\_\{i\},T\_\{2\},...,T\_\{n\}][T_i_T_2_..._T_n]｝，其中每棵二叉树 ![T\_\{i\}][T_i] 中只有一个带权为![w\_\{i\}][w_i] 的根结点，其左右子树均为空；
2.  在 F 中选取两棵根结点的权值最小的树为作为左右子树来构造一棵新的二叉树，且新的二叉树的根结点的权值为其左右子树上根点的权值之和；
3.  在 F 中删除这两棵树，同时将新得到的二叉树加入到 F 中；
4.  重复步骤 2 和 3，直到 F 只含有一棵树为止。这棵树便是霍夫曼树。

## 1.4 霍夫曼树的应用 ##

### 1.4.1 霍夫曼编码 ###

在日常办法中常遇到的文件传输，如果文件很大一般先进行压缩。尽管以现在最新技术来说，编码已经很好很强大，但这都来自于曾经的技术积累。这里不得不提一下霍夫曼编码，因为它是最基本的压缩编码方法。它于1952年由美国数学家霍夫曼（David  Huffman）发明。为了纪念他的成就，于是把他在编码中用到的特殊的二叉树称之为霍夫曼树。

霍夫曼当初研究这种树的目的主要是为了解决当时远距离通信（主要是电报）的数据传输的最优化问题。比如有一段文字内容为“BADCADFEED”要网络传输给其他人，显然用二进制的数字（0和1）来表示是很自然的想法。现在这段文字只有6个字母ABCDEF，那可以用相应的二进制数据来表示，如下图所示。

![2020011817004453.png][]

用二进制表示后，真正传输的数据就是“001000011010000011101100100011”，对方接收时可以按照3位数据分段来进行译码。但对一篇内容很长的文章，这样的二进制串就太长了。而且事实上，不管是英文、中文还是其他语言，字母或汉字的出现频率是不相同的。

假设有6个字母的频率为A  27，B  8，C  15，D  15，E  30，F  5，频率和正好是100%。这意味着完全可以重新按照霍夫曼树来规划它们。

如下图所示，左图为构造霍夫曼树的过程中的权值显示。右图为将权值左分支改为0，右分支改为1后的霍夫曼树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 5][]

此时对6个字母用其从树根到叶子所经过的路径的0或1编码，可以得到如下表所示这样的定义。

![20200118170801905.png][]

将文字内容为“BADCADFEED”再次编码，对比可以看出使用霍夫曼树来表示后的结果串变小了。

*  原编码的二进制串：001000011010000011101100100011（共30个字符）
 *  新编码的二进制串：100101001010100100011100（共25个字符）

新编码后的数据被压缩了，节约了大约17%的存储或传输成本。随着字符的增加和多字符权重的不同，这种压缩会更加显出其优势。

反过来，当接收到1001010010101001000111100这样经过压缩后的编码时，该如何把它解码呢？编码中非0即1，长短不等的话其实很容易混淆的，所以若要设计长短不等的编码，则必须是任一个字符编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。

仔细观察会发现，上表的编码就不存在容易与1001、1000混淆的“10”和“100”编码。但仅仅是这样也不足以方便的解码，因此在解码时还是要用到霍夫曼树，即发送方和接收方必须要约定好同样的霍夫曼编码规则。

在接收到1001010010101001000111100时，由约定好的霍夫曼树可知，1001得到第一个字母是B，接下来01意味着第二个字符是A，如下图所示，其余的字母也可以相应的得到，这样就解码成功了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 6][]

一般地，设需要编码的字符集为｛![d\_\{1\},d\_\{2\},...,d\_\{n\}][d_1_d_2_..._d_n]｝，各个字符在电文中出现的次数或频率集合为｛![w\_\{1\},w\_\{2\},...,w\_\{n\}][w_1_w_2_..._w_n]｝，以![d\_\{1\},d\_\{2\},...,d\_\{n\}][d_1_d_2_..._d_n]作为叶结点，以![w\_\{1\},w\_\{2\},...,w\_\{n\}][w_1_w_2_..._w_n]作为相应叶结点的权值来构造一棵霍夫曼树。规定霍夫曼树的左分支代表0，右分支代表1，则从根结点到叶结点所经过的路径分支组成的0和1的序列便是该结点对应字符的编码，这就是**霍夫曼编码**。

### 1.4.2 其它 ###

霍夫曼树，除了霍夫曼编码外，还有一些其它方面的应用，上面举例中说的成绩转换问题就是其中之一。

# 二. 二叉搜索树 #

二叉搜索树的基本操作所花费的时间与这棵树的高度成正比。对于有 n 个结点的一棵完全二叉树来说，这些操作的最坏运行时间为O(lgn)。因此这样一棵树上的动态集合的基本操作的平均运行时间是Θ(lgn)。

## 2.1 二叉搜索树定义特征 ##

一棵二叉搜索树是以一棵二叉树来组织的，如下图所示。这样的一棵树可以使用一个链表来表示，其中每个结点就是一个对象。除了关键字和卫星数据外，每个结点还包含属性left、right、parent，它们分别指向结点的左子结点、右子结点和双亲。根结点是树中唯一双新引用为空的结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 7][]

上图（a）是一棵包含6个结点、高度为2的二叉搜索树。树根的关键字为6，在其左子树中有关键字2、5和5，它们均不大于6，而在其右子树中有关键字7和8，它们均不小于6。图（b）是一棵包含相同关键字、高度为4的低效二叉搜索树。

二叉搜索树，Binary  Search  Tree，也称二叉查找树、有序二叉树、二叉排序树。使用一棵二叉搜索树既可以作为一个字典又可以作为一个优先队列。 它有以下特征：

1.  若左子树不为空，则左子树的所有结点的值都小于它的根结点的值；
2.  若右子树不为空，则右子树的所有节点的值都大于根节点的值；
3.  左右子树也分别为二叉搜索树；
4.  没有键值相等的结点，每个结点存储一个关键字。

## 2.2 二叉搜索树的原理 ##

二叉搜索树的查找过程和平衡二叉树类似，通常采用二叉链表作为二叉搜索树的存储结构。中序遍历二叉树可得到一个关键字的有序排列，一个无序排列可以通过构造一棵二叉搜索树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉搜索树上新的叶结点，在进行插入操作时，不必移动其它结点，只需要改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，为O(logn)。

## 2.3 查找二叉搜索树 ##

经常需要查找一个存储在二叉搜索树中的关键字。除了search操作外，二叉搜索树还能支持如minimum（最小元素）、maximum（最大元素）、successor（前驱元素）和predecessor（后继元素）的查找操作。这里将讨论这些操作，并且说明在任何高度为 h 的二叉搜索树上，如何在O(h)时间度执行完每个操作。

### 2.3.1 查找 ###

使用下面的过程在一棵二叉搜索树中查找一个具有给定关键字的结点。输入一个指向树根的结点和一个关键字，若这个结点存在，则返回一个指向关键字的结点的指针，否则返回空。如下图的左图。

这个过程从树根开始查找，并沿着这棵树中的一条简单路径向下进行。如下图的右图，对于遇到的每个结点 x，比较关键字 k 与结点 x 的关键字。若两个关键字相等，查找终止。若 k 小于结点 x 的关键字，则继续在 x 的左子树中进行查找，因为二叉搜索树的性质中蕴涵了 k 不可能被存储于右子树中（二叉搜索树中的左子树的所有结点都要小于其根结点的值）。对称地，若 k 大于结点 x 的关键字，则继续在 x 的右子树中进行查找。从树根开始递归期间遇到的结点就形成了一条向下的简单路径。所以运行时间为O(h)，其中 h 是树的高度。

![20200120212946162.png][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 8][]

如上图的右图，为了查找这棵树中关键字为13的结点，从树根开始沿着15—>6—>7—>13路径进行查找。这棵树中最小的关键字为2，它是从树根开始一直沿着左边指针被找到的。最大的关键字为20，是从树根开始一直沿着右边指针被找到的。关键字15的结点的后继是关键字为17的结点，因为它是15的右子树中最小的关键字。关键字为13的结点没有右子树，因此它的后继是最低的祖先并且其右子结点也是一个祖先。这种情况下，关键字为15的结点就是它的后继。

可以采用while的循环展开递归，用一种迭代方式重写这个过程。对大多数计算机，迭代版本的效率要高得多。

![2020012021392618.png][]

### 2.3.2 最小关键字元素和最大关键字元素 ###

通过树根开始沿着左子结点指针直到遇一个空元素，总能在一棵二叉搜索树中找到一个元素，上面的二叉搜索树图例就是这样的。下面的过程返回了一个指向在以给定结点 x 为根的子树中的最小元素的指针，这里假设不为空。

![20200120214340855.png][]![20200120214639232.png][]

二叉搜索树的性质保证了minimum是正确的。若结点 x 没有左子树，那么由于 x 右子树中的每个关键中都不小于 x 的关键字，则认为以 x 为根的子树中的最小关键字是 x 的关键字。若 x 有左子树，则以 x 为根的子树中的最小关键字一定在以 x 的右子结点的子树中。

### 2.3.3 后继和前驱 ###

有时候需要按中序遍历的次序查找它的后继。若所有的关键字都不相同，则一个结点 x 的后继是大于 x 的关键字的最小关键字的结点。二叉搜索树的结构允许通过没有任何关键字的比较来确定一个结点的后继。若后继存在，下面的过程将返回一棵二叉搜索树中的结点 x 的后继；若 x  是这棵树中的最大关键字，则返回空。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 9][]

把上图的伪代码分为两种情况。若结点 x 的右子树非空，那么 x 的后继恰是 x 右子树中的最左结点（伪代码的第2行）。例如在上面的二叉搜索树图例中，关键字为15的结点的后继就是关键字为17的结点。

另一方面，若结点 x 的右子树非空且有一个后继 y，那么 y 就是 x 的有右子结点的最底层祖先，并且它也是 x 的一个祖先。在上面的二叉搜索树图例中，关键字为13的结点的后继是关键字为15的结点。为了找到 y，只需简单的从 x 开始沿树而上直到遇到一个其双亲有左子结点的结点。上面伪代码中的第3~7行正是这种情况。

## 2.4 插入和删除 ##

插入一个新结点带来的树修改要相对简单些，而删除的处理有些复杂。插入和删除操作都要保证二叉搜索树的性质不变。

### 2.4.1 插入 ###

将一个新值 v 插入到一棵二叉搜索树T中，该过程以结点 z 作为输入，其中 z 的关键字等于 v，z 的左子结点和右子结点为空。这个过程要修改T和 z 的某些属性，来把 z 插入到树中的相应位置上。

![20200120221404179.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 10][]

从树根开始，指针 x 记录了一条向下的简单路径，并查找要替换的输入项 z 的空结点。该过程保持遍历指针 y 作为 x 的双亲。初始化后，第3~7行的while循环使得这两个指针沿树向下移动，向左或向移动取决于 z 的关键字和 x 的关键字的比较，直到 x 变为空。这个空结点占据的位置就是输入项 z 要放置的地方。需要遍历指针 y，是因为找到空结点时要知道 z 属于哪个结点。第8~13行设置了相应的指针，使得 z 插入其中。插入到一棵高度为 h 的树上的运行时间为O(h)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 11][]

如上图，将关键字为13的数据项插入到二叉搜索树中，浅色阴影结点指示了一条从树根向下到要插入数据项位置处的简单路径。虚线表示了为插入数据项而加入的树中的一条链。

### 2.4.2  删除 ###

从一棵二叉搜索树T中删除一个结点 z 的整个策略分为三种基本情况，但只有一种情况有点棘手。

1.  若 z 没有子结点，那只是简单的将它删除，并修改它的的父结点，用空作为子结点来替换 z ；
2.  若 z 只有一个子结点，那将这个子结点提升到树中 z 的位置上，并修改 z 的父结点，用 z 的孩子来替换 z；
3.  若 z 有两个孩子，那找 z 的后继 y （一定在 z 的右子树中），并让 y 占据树中 z 的位置。 z 的原来右子树部分成为 y 的新的右子树，并且 z 的左子树成为 y 的新的左子树。这种情况稍显麻烦，因为还与 y 是否与 z 的右子结点相关。

从一棵二叉搜索树T中删除一个结点 z ，这个过程取指向 T 和 z 的指针作为输入参数。考虑到下图中的4种情况，它与前面概括的三种情况有些不同。

1.  若 z 没有左子结点（下图（a）），那么用其右子结点来替换 z ，这个右子结点可以是空，也可以不是。当 z 的右子结点为空时，这种情况归为 z 没有子结点的情形。当 z 的右子结点非空时，这种情况就是 z 仅有一个子结点的情形，该子结点是右子结点。
2.  若 z 仅有一个左子结点（如下图（b）），那么用其左子结点来替换 z 。
3.  否则， z 既然有一个左子结点又有一个右子结点，要查找 z 的后继 y，这个后继位于 z 的右子树中并且没有左子结点。现需要将 y 移出原来的位置进行拼接，并替换树中的 z 。
4.  若 y 是 z 的右子结点（如下图（c）），那么用 y 替换 z，并仅留下 y 的右子结点。
5.  否则， y 位于z 的右子树中但并不是 z 的右子结点（如下图（d））。在这种情况下，先用 y 的右子结点替换 y，然后再用 y 替换 z。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 12][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 13][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 14][]

为了在二叉搜索树内移动子树，定义一个子过程 plan，它是用另一棵子树替换一棵子树并成为其双亲的子结点。当 plan 用一棵以 v 为根的子树来替换一棵以 u 为根的子树时，结点 u 的双亲就变为结点 v 的双亲，并且最后 v 成为 u 的双亲的相应子结点了。

![20200121163905391.png][]

第1~2行处理 u 是 T 树根的情况。若不是，u 是其双亲的左子结点或右子结点。若 u 是一个右子结点，第3~4行负责u.p.left的更新；若 u 是一个右子结点，第5行更新u.p.right。允许 v 为空，若 v 非空时，第6~7行更新v.p。注意到，此方法并没有处理 v.left 和 v.right 的更新；这些更新都由此函数的调用者来负责。

利用现成的TRANSPLANT（上图中的函数名）过程，来组织从二叉搜索树 T 中删除结点 z 的删除过程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 15][]

## 2.5 随机构建二叉搜索树 ##

上面提到了二叉搜索树上的每个基本操作都能在O(h)时间内完成，其中 h 为这棵树的高度。然后，随着元素的插入和删除，二叉搜索树的高度是变化的。当树是由插入操作单独生成的，分析就会变得容易很多。因此定义 n 个关键字的一棵随机构建二叉搜索树（randomly  built  binary  search  tree）为随机次序插入这些关键字到一棵初始的空树中而生成的树，这里输入关键字的 n!个排列中的每个都是等可能地出现。

## 5.6 二叉树的使用及问题 ##

因为二叉搜索树遍历的结果是单调的，可以用来进行二分查找，左小右大，在查找时若关键字大于根节点，那只需要从一个分支查下去即可。但二叉搜索树在插入或删除结点时，会改变二叉树的结构，多次插入和删除后，可能变成下面这样的结构。

![20200407172043909.png][]

这样再来查找，就是线性的了。同样的关键字集合导致不同的树结构。可以明显看出，这棵是非常不平衡的。比如查找53这个数，若是平衡的树（就是有左右两个子结点），那从树的层级角度来看，肯定不用进入更深的层级来查找。所以说，二叉搜索树的一个很大问题就是树的平衡性问题，因为它无法保证树的平衡，给查找带来了问题。下面就来看几种平衡的树。

# 三. 平衡二叉搜索树(AVL树) #

含有相同节点的二叉搜索树可以有不同的形态，而二叉搜索树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵树，那就是平衡二叉树。平衡二叉树，也叫AVL树，它是一种结构平衡的二叉搜索树，也可为空树，它有以下几点特征：

1.  叶结点高度差的绝对值不超过1；
2.  左右两个子树都是一棵平衡二叉树；
3.  二叉树节点的平衡因子定义为该结点的左子树的深度减去右子树的深度，则平衡二叉树的所有结点的平衡因子只可能是-1，0，1。即左右子树深度之差的绝对值不超过1。

![SouthEast][]

如上图所示，图（a）为平衡树，图（b）为非平衡树。AVL树是严格平衡树，因此在增加或删除节点时，根据不同情况，旋转的次数比红黑树要多。

# 四. 红黑树 #

上面介绍了二叉搜索树，它可以支持任何一种基本动态集合操作，时间复杂度为O(h)。h 为树的高度，因此，若搜索树的高度较低时，这些集合操作会执行的较快。然而，若树的高度较高时，这些集合操作可能并不比在链表上执行的快。红黑树（red-black  tree）是许多“平衡”搜索树中的一种，可以保证在最坏情况下基本动态集合操作的时间复杂度为O(lgn)。

## 4.1 红黑树定义性质 ##

红黑树是一种自平衡二叉查找树，它于1972年由鲁道夫 ![\\cdot][cdot] 贝尔发明，他称之为“对称二叉B树”。它在平衡二叉树的基础上每个结点又增加了一个颜色的属性，节点的颜色只能是红色或者黑色。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。其左右子树的高度差有可能超过1。所以它不是严格意义上的平衡二叉树。

树中每个结点包含5个属性：颜色（color）、key（关键字）、left（左子结点）、right（右子结点）和p（父结点）。一棵红黑树是满足以下红黑性质的二叉搜索树：

1.  根结点只能是黑色；
2.  所有结点的颜色只能是红色或黑色；
3.  每个叶结点（空）是黑色的（红黑树中所有的叶结点后面再接左右两个空结点，这样可以保证算法的一致性，且所有的空结点都是黑色）；
4.  若一个结点是红色的，那么它的左右两个子结点都是黑色；
5.  在任何一棵子树中，从根结点向下到达空结点的路径上所经过的黑节点的数目相同（或说对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑色结点），从而保证了是一个平衡二叉树。

![format_png][]

如上图，表示一棵红黑树（忽略了叶结点的空结点）。从某个结点 x 出发（不含该结点）到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高（black-height），记为 bh(x)。从该结点出发的所有下降到其叶结点的简单路径的黑结点个数都相同，于是定义红黑树的黑高为其根结点的黑高。

可以将结点 x 的空子结点视为一个普通结点，其父结点为 x。常将注意力放在红黑树的内部结点上，因为它们存储了关键字的值。一棵有 n 个内部结点的红黑树的高度至多为2 lg(n+1)。假设树的高度为 h，根据性质4可知，从根到叶结点（不包含根结点）的任何一条简单路径上都至少有一半的结点为黑色。因此，根的黑高至少为 h/2，于是有![n \\geqslant 2^\{h/2\}-1][n _geqslant 2_h_2_-1]，把1移到不等式的左边，再两边取对数，得到![\\lg (n+1) \\geqslant h/2][lg _n_1_ _geqslant h_2]，或![h \\leqslant 2\\lg (n+1)][h _leqslant 2_lg _n_1]。动态集合操作查找、最小值、最大值、前驱和后继可在红黑树上在O(lgn)时间内执行。

## 4.2 红黑树操作 ##

搜索树操作插入和删除在含有 n 个关键字的红黑树上，时间复杂度为O(lgn)。由于这两个操作对树做了修改，结果可能违反了红黑性质。为了维护这些性质，必须要改变树中某些结点的颜色以及指针结构。

指针结点的修改是通过旋转（ratation）来完成的，这是一种能保持二叉搜索树性质的搜索局部操作。下图给出了两种旋转：左旋和右旋。当在某个结点 x 上做左旋转时，假设它的右子结点是 y，x 可以为其右子结点不为空的树内的任意结点。左旋以 x 到 y 链为“支轴”进行。它使 y 成新子树的根结点， x 成为 y 的左子结点， y 的左子结点成为 x 的右孩子。

![20200124202728118.png][]

下面是左旋转的伪代码。假设 x.right ![\\neq][neq] T.nil，且根结点的父结点为 T.nil。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 16][]

下图给出了一个左旋转操作修改二叉搜索树的例子。左旋转和右旋转都在O(1)时间内完成 ，在旋转操作内只有指针改变，其它所有属性都保持不变。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 17][]

## 4.3 红黑树（RBT）与AVL树的区别 ##

AVL树是严格平衡树，因此在增加或删除节点时，根据不同情况，旋转的次数比红黑树要多；而红黑树是弱平衡的，用非严格的平衡来换取增删结点时旋转次数的降低。所以简单来说，若搜索的次数远远大于插入和删除次数，那建议使用AVL树，若搜索、插入、删除次数差不多，那建议使用红黑树。

更通俗的说，平衡二叉树的优点在于快速查找，搜索任意元素者是O(logn)，一般插入和删除也是O(logn)。平衡二叉树相对于二叉搜索树，是较为平衡的，能把查找时间控制在O(logn)，但仍不是最佳的。因为平衡树要求每个节点的左右子树的高度差不超过1，这个要求有点严格了，导致每次进行插入或删除操作后，几乎都会破坏这个规则。这时需要通过左旋和右旋来进行调整，使这棵树成为一棵平衡二叉树。若在插入和删除操作频繁的情况下，就意味着要对树进行频繁的调整，这样性能自然就不高了。

由于红黑树的这些性质，使得它能在最坏的情况下，仍能以O(logn)的时间复杂度查找。若仅从查找的效率来说，平衡树比红黑树快，因为它的规则就是有利于查找的。可以说，红黑树解决了平衡树在插入、删除等操作下需要频繁调整树结构的情况。

## 4.4 红黑树的应用 ##

Java集合容器中的HashMap、TreeMap，内部就使用了红黑树。

**未完待续.....!!!**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70]: /images/20230528/6004c0c722914e34bf37d3a1eb2ecf0d.png
[20200110174259748.png]: /images/20230528/cdec67f4259640eabb14bc97ec238b58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 1]: /images/20230528/4e0b5c908a884132a904396e6f3c9f11.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 2]: /images/20230528/94cfa85e57ed4661a912205cb9c12286.png
[w_1_w_2_..._w_n]: https://private.codecogs.com/gif.latex?w_%7B1%7D%2Cw_%7B2%7D%2C...%2Cw_%7Bn%7D
[w_k]: https://private.codecogs.com/gif.latex?w_%7Bk%7D
[N_1]: https://private.codecogs.com/gif.latex?N_%7B1%7D
[202001101842089.png]: /images/20230528/a2c7237b604c4b9e83570a8983c85e3b.png
[N_2]: https://private.codecogs.com/gif.latex?N_%7B2%7D
[N_3]: https://private.codecogs.com/gif.latex?N_%7B3%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 3]: /images/20230528/af3cb61a7fb34348a1fe87b436620f19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 4]: /images/20230528/cf84f85e094748e5a386ad89e42366d2.png
[T_i_T_2_..._T_n]: https://private.codecogs.com/gif.latex?T_%7Bi%7D%2CT_%7B2%7D%2C...%2CT_%7Bn%7D
[T_i]: https://private.codecogs.com/gif.latex?T_%7Bi%7D
[w_i]: https://private.codecogs.com/gif.latex?w_%7Bi%7D
[2020011817004453.png]: /images/20230528/4a7abe15474f40deb91a99fe3e927ef2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 5]: /images/20230528/0a51cc12b46343bebc05d069cafbbbd8.png
[20200118170801905.png]: /images/20230528/e733b519156f4dbca82c02751b25d62f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 6]: /images/20230528/52a12fcc744341e7a54b8cd64ae10575.png
[d_1_d_2_..._d_n]: https://private.codecogs.com/gif.latex?d_%7B1%7D%2Cd_%7B2%7D%2C...%2Cd_%7Bn%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 7]: /images/20230528/da3abeb7c5e2438291e1dfa84ccd3e17.png
[20200120212946162.png]: https://img-blog.csdnimg.cn/20200120212946162.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 8]: /images/20230528/4fcf6d5717154f3d8beac43a13604c29.png
[2020012021392618.png]: /images/20230528/dd59793614cf4427a18d9362542cdaef.png
[20200120214340855.png]: https://img-blog.csdnimg.cn/20200120214340855.png
[20200120214639232.png]: /images/20230528/ceccf431ebf6430fa95a10b0658c9970.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 9]: /images/20230528/223557cff0e94827ba51f8fc6495a4c2.png
[20200120221404179.png]: /images/20230528/53993a2c2d694212a2b5e5270a94bd86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 10]: /images/20230528/0a1765591d7d436b8d9ef0cad510e1e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 11]: /images/20230528/931160afabbd4e7ca783797cb6613e3e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200121143859636.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 13]: /images/20230528/ac61617e53c040cda89e06dbd43909b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 14]: /images/20230528/9410569c525542f9ad32c7ab49a93d9b.png
[20200121163905391.png]: /images/20230528/38a3630a043a4cadad202c54c4c3a02c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 15]: /images/20230528/4309d180d55d4af2bceeff92b4a7d999.png
[20200407172043909.png]: /images/20230528/cb07ab9cf22c4a78b50e7c5cd47e4810.png
[SouthEast]: /images/20230528/4f1f189f1fab4cc68505df93c56b1db7.png
[cdot]: https://private.codecogs.com/gif.latex?%5Cdpi%7B80%7D%20%5Ccdot
[format_png]: /images/20230528/a3314ac4d4304ddd81b273ee7caff755.png
[n _geqslant 2_h_2_-1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20n%20%5Cgeqslant%202%5E%7Bh/2%7D-1
[lg _n_1_ _geqslant h_2]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Clg%20%28n&plus;1%29%20%5Cgeqslant%20h/2
[h _leqslant 2_lg _n_1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h%20%5Cleqslant%202%5Clg%20%28n&plus;1%29
[20200124202728118.png]: /images/20230528/7fda85a25fc74e65b2b7bc7632b82efd.png
[neq]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Cneq
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 16]: /images/20230528/e28feb9562d44ed39d52b709665e3a53.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 17]: /images/20230528/2d3a0b7afa384834b0591173efe4a8f8.png