树与二叉树

发表于 2024-01-02 更新于 2024-01-10 分类于数据结构阅读次数： Valine：

本文字数： 17k 阅读时长 ≈ 15 分钟

😊

0 数据结构

数据三要素：逻辑结构、存储结构和数据的运算。

逻辑结构。通常有四类基本结构（如图1.3），它们的复杂程度依次递进。逻辑结构的层次如图 1.4。
存储结构。数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。

包括：顺序存储、链式存储、索引存储、散列存储。
数据的运算。施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

1 基本概念

1.1 树

基本概念：

节点：树中的一个独立单元。
节点的度：节点拥有的子树的个数称为节点的度。
树的度：树中节点的最大度称为树的度。
叶子结点（终端节点）：度为 0 的节点。
双亲与孩子：具有直接相连关系，子树节点称为孩子，对应的上层的节点称为双亲。
祖先：从根节点到该节点路径所经过的节点，都是该节点的祖先节点。如 A、D、H 都是 M 的祖先节点。
子孙：以该节点为根的子树中所有节点，都是该节点的子孙。
兄弟：同一双亲的孩子互称为兄弟。
堂兄弟：双亲在同一层节点互称为堂兄弟。如 G 与 E、F、H、I、J 互为堂兄弟。
树的深度、高度、层次：
- 层次：从根节点开始，孩子节点为第二层，以此类推。
- 树的深度：从根节点自顶向下 ↓，逐层累加。树的最大层次即为树的深度。
- 树的高度：从叶节点自底向上 ↑，逐层累加。最大高度等于树的深度，但是方向不同。
有序树和无序树：
- 有序树：节点的左右子树是有顺序的，不能互换。
- 无序树：节点的左右子树是无顺序的，可以交换。
路径：树中两个节点之间的路径，由经过这两个节点的所有节点构成。如 A 到 M 的路径为：A→D→H→M。
路径长度：
- 节点路径长度：节点的路径上经过的边的个数。如上 A 到 M 的路径长度为 3。
- 树的路径长度：树中所有节点到根节点路径长度之和。
森林：m(m>=0) 棵互不相交的树的集合。

树的性质：

树中的$结点个数 = 所有结点的度数之和加 1$。
度为 m 的树中，第 i 层上至多有 $m^{i-1}$ 个结点（i>=1）。
高度为 h 的 m 叉树至多有$(m^h-1)\over(m-1)$个结点。推导公式：$S=m^{h-1}+m^{h-2}+m^{h-3}+…+m+1=$$(m^h-1)\over(m-1)$。
具有 n 个结点的 m 叉树的最小高度为 $\lceil log_m[n(m-1)+1] \rceil$。

1.2 二叉树

二叉树与树一样具有递归性质，但是二叉树具有如下性质（与树的区别）：

二叉树的每个节点最多只能有 2 个子节点，树的度 <= 2。
二叉树是有序树，左右子树次序不能颠倒。

二叉树的 5 种基本形态如下图：

二叉树的性质：

非空二叉树的第 i 层上最多有 $2^{i-1}$ 个节点（i >= ）。
深度为 h 的二叉树最多有 $2^{h-1}$ 个节点（h >= 1）。
非空二叉树中，叶子结点个数 $ n_0 $，等于度为 2 的节点数 $ n_2 $ 加 1。即 $ n_0 = n_2+1$。
具有 n(n>0) 个节点的完全二叉树的深度为 $\lfloor log_2n \rfloor + 1$ 或 $\lceil log_2(n+1) \rceil$。

特殊的二叉树：

满二叉树：深度为 h 且含有 $2^{h-1}$ 个节点的二叉树。完
完全二叉树：完全二叉树是由满二叉树而引出来的，完全二叉树从根结点到倒数第二层满足满二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐（参考完美二叉树, 完全二叉树和完满二叉树）。以下 3 条用来解释这句话：
- 完全二叉树的层数 <= 对应的满二叉树层数 - 2；（叶子结点只可能在倒数第一层或倒数第二层出现）
- 完全二叉树中缺失的节点只能在最下层，且必须是右子树上的节点（对任意一结点，如果其右子树的最大层次为L，则其左子树的最大层次为 L 或 L+1，子树必须向左对齐）。
- 在完全二叉树中，若某个节点没有左子树，则一定没有有子树。
二叉排序树：左子树上的所有节点均小于根节点的关键字。
平衡二叉树（AVL）：树上任一节点的左子树与右子树的深度之差不超过 1。

平衡二叉树、完全二叉树、二叉排序树、二叉查找树、二叉搜索树的区别：

二叉排序树，又叫做二叉查找树、或二叉搜索树。$左子树结点值＜根结点值＜右子树结点值$。
平衡二叉树，又叫做 AVL 树，他是空树或二叉排序树，|左右子树深度差| <= 1。
完全二叉树，从根结点到倒数第二层满足满二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。完全二叉树确实平衡（平衡因子绝对值小于等于一），但不一定是平衡二叉树，原因是平衡二叉树本质上是二叉排序树，但完全二叉树不一定是有序的。
平衡二叉树也不一定是完全二叉树。因为平衡二叉树最底层结点不一定集中在最左边。

1.3 二叉树的存储

二叉树的节点的存储可使用顺序存储与链式存储两种方式：

顺序存储：使用一维数组，将树的节点自上而下，自左而右进行存储，不存在的节点使用 0 表示。缺点：对于除满二叉树、完全二叉树外的其他树，非常浪费空间。
链式存储：二叉树链表至少包含 3 个成员：数据域（data）、左指针（lchild）、右指针（rchild）。有时为了方便查找双亲，还会增加一个指向双亲的指针（parent）。

2 遍历二叉树

二叉树的遍历是按某条搜索路径访问数中的所有节点，使得每个节点被访问一次，而且仅被访问一次。遍历的实质是对二叉树进行线性化的过程，即遍历的结果是将非线性结构的树中节点排成一个线性序列。

假如从 L、D、R 分别表示遍历左子树、根节点、遍历右子树，则可能有 LDR、LRD、DLR、DRL、RDL、RLD 共 6 种遍历二叉树的情况。若限定先左后右，则只有 3 种情况：先（根）序遍历中（根）序遍历后（根）序遍历。

基于二叉树的递归定义，遍历二叉树也可基于递归进行计算，如下是中序遍历的使用：

void InOrderTraverse(BitTree T)
{
    InOrderTraverse(T->lchild);
    Visit(T);
    InOrderTraverse(T->rchild);
}

说明：不管是哪种遍历算法，在递归遍历中，每个节点都仅被访问一次，所以时间复杂度为 O(n) 。递归堆栈的栈深恰好为树的深度，所以在最坏情况下，有 n 个节点的二叉树深度也为 n 的单支树，遍历算法的空间复杂度为 O(n)。

对于使用堆栈，非递归的遍历方法，可参考：《数据结构（C语言版）5.5.1》、《王道考研2023版 5.3》。

3 二叉树的经典应用

3.1 线索二叉树

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。

二叉树以二叉链表作为存储结构时（不包含 parent 成员），只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到，为此引入线索二叉树来保存这些在动态过程中得到的有关前驱和后继的信息。

这里使用到一个基本结论：在含 n 个结点的二叉树中，有 n+1 个空指针。这是因为每个叶结点有 2 个空指针，每个度为 1 的结点有 1 个空指针，空指针总数为 $2n_0+n_1$，又因为 $ n_0 = n_2+1$，所以空指针总数为 $ n_0 + n_1 + n_2+1=n+1$。由此设想能否利用这些空指针来存放指向其前驱或后继的指针？这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。

规定：若无左子树，令 lchild 指向其前驱结点；若无右子树，令 rchild 指向其后继结点。如图 5.10 所示，还需增加两个标志域标识指针域是指向左（右）孩子还是指向前驱（后继)。

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树（Threaded Binary Tree）。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

关于线索二叉树的构造、遍历方法详细参考《数据结构（C语言版）5.5.2 P128》、《王道考研2023版 5.3.2 P143》。

3.2 哈夫曼树

哈夫曼（Huffman）树又称最优二叉树，是一类带权路径长度最短的树，在实际中有广泛的用途。

3.3 哈夫曼树的构造

根据【哈夫曼树中，权值越大的结点离根结点越近】这个特点，哈夫曼最早给出了一个构造哈夫曼树的方法，称哈夫曼算法。

给定 n 个权值分别为 $w_1, w_2, … ,w_n$ 的结点，构造哈夫曼树的过程：

使用这 n 个结点，构造成 n 棵只有根结点的二叉树，这 n 棵二叉树构成一个森林 $F$。
从 $F$ 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
从 $F$ 中删除刚才选出的那两棵树，同时将新得到的树加入 $F$ 中。
重复步骤 2 和 3，直至 $F$ 中只剩下一棵树为止。

从上述构造过程中可以看出哈夫曼树具有如下特点：

森林 $F$ 中的初始结点最终都成为叶结点。首先选择权小的，这样保证权大的离根较近；
构造过程中共新建了 n-1 个结点（双分支结点），因此哈夫曼树的结点总数为 2n-1。
每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点。

例 1。权值 {7, 5, 2, 4} 的哈夫曼树的构造过程如图 5.19 所示。

例 2。已知 $w=(5, 29, 7, 8, 14, 23, 3, 11)$，利用哈夫曼算法构造一棵哈夫曼树，计算树的带权路径长度。

$WPL=\sum\limits_{k=1}^{n}w_kl_k=23×2+11×3+5×4+3×4+29×2+14×3+7×4+8×4=271$。

例 3。有 n = 8，权值为 $w={7, 19, 2, 6, 32, 3, 21, 10}$，构造哈夫曼树。

3.3 哈夫曼编码

固定长度编码：在数据通信中（举例的场景），若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。

可变长度编码：若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。

哈夫曼编码的基本思想：为出现次数较多的字符编以较短的编码。

下面给出有关编码的两个概念：

前缀编码：如果在一个编码方案中，任一个编码都不是其他任何编码的前缀，则称编码是前缀编码。编码 0，10，110，111 是前缀编码；而编码 0，01，010，111 就不是前缀编码。
哈夫曼编码：对一棵具有 n 个叶子的哈夫曼树，若对树中的每个左分支赋予 0，右分支赋予 1，则从根到每个叶子的路径上，各分支的赋值（边的权）分别构成一个二进制串，该二进制串就称为哈夫曼编码。

哈夫曼编码的性质：

哈夫曼编码是前缀编码。每个字符的编码，使用从哈夫曼树的根节点到每一个叶节点路径上边的权构成。
哈夫曼编码是最优前缀编码。

哈弗曼编码得到的报文长度正好等于哈夫曼树带权路径长度 WPL。

图 5.20 所示为一个由哈夫曼树构造哈夫曼编码的示例，矩形方块表示字符及其出现的次数。

注意：0 和 1 究竞是表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度 WPL 相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但 WPL 必然相同且是最优的。

4 查找

查找的知识框架：

4.1 基本概念

查找表（查找结构)。用于查找的数据元素构成的集合称为查找表，它由同一类型的数据元素（或记录）组成，可以是一个数组或链表等数据类型。如线性表、树表及散列表等。对查找表经常进行的操作一般有 4 种：
1. 查询某个特定的数据元素是否在查找表中；
2. 检索满足条件的某个特定的数据元素的各种属性；
3. 在查找表中插入一个数据元素；
4. 从查找表中删除某个数据元素。
关键字。数据元素中某个数据项的值，它可以唯一标识该元素。使用基于关键字的查找，查找结果应该是唯一的。例如，在由一个学生元素构成的数据集合中，学生元素中“学号”这一数据项的值唯一地标识一名学生。
查找的结果：一是查找成功，即在数据集合中找到了满足条件的数据元素；二是查找失败。
动态查找表和静态查找表。
1. 动态查找表。在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表。适合动态查找表的查找方法有二叉排序树的查找、散列查找等。二叉平衡树和 B 树都是二叉排序树的改进。
2. 静态查找表。在查找的同时不对表做修改操作。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等。
平均查找长度（Average Search Length, ASL）。在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值（或期望值），其数学定义为 $ASL=\sum\limits_{i=1}^{n}P_iC_i$。是衡量查找算法效率的最主要的指标。
1. $n$ 是查找表的长度；
2. $P_i$ 是查找第 $i$ 个数据元素的概率，一般认为每个数据元素的查找概率相等，即 $P_i=$$1\over n$；
3. $C_i$ 是找到第 $i$ 个数据元素所需进行的比较次数。

4.2 线性表的查找

4.2.1 顺序查找

顺序查找又称线性查找，它对顺序、链式存储结构的数据查找都是适用的。对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于链表，可通过指针 next 来依次扫描每个元素。

顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的线性表的顺序查找。

举例：在顺序表 ST 中顺序查找其关键字等于 key 的数据元素。若找到，则函数值为该元素在表中的位置，否则为 0。

无哨兵的方式。

int Search_Seg (SSTable ST, KeyType key)
{
  for(i = ST.length; i >= 1; --i)
    if(ST.R[i].key == key) return i;
  return 0;
}

有哨兵的方式。
1
2
3
4
5
6
int Search_Seg (SSTable ST, KeyType key)
{
ST.R[O].key = key; // ST.R[O].key 即为哨兵
for(i = ST.length; ST.R[i].key != key; --i);
return i;
}
即通过设置监视哨，免去查找过程中每一步都要检测整个表是否查找完毕。然而实践证明，这个改进能使顺序查找在 ST.length ≥ 1000 时，进行一次查找所需的平均时间几乎减少一半。

性能分析：对于有 $n$ 个元素的表，给定值 $key$ 与表中第 $i$ 个元素相等，即定位第 $i$ 个元素时，需进行 $n-i+1$ 次关键字的比较，即 $C_i=n-i+1$。

查找成功时，顺序查找的平均长度为 $ASL_{成功}=\sum\limits_{i=1}^{n}P_i(n-i+1)$。当每个元素的查找概率相等，即 $P_i=$$1\over n$ 时，有 $ASL_{成功}=\sum\limits_{i=1}^{n}P_i(n-i+1)=$${n+1}\over 2$。
查找不成功时，与表中各关键字的比较次数显然是 $n+1$ 次，从而顺序查找不成功的平均查找长度为 $ASL_{不成功}=n+1$。

4.2.2 折半查找

折半查找也叫做二分查找，仅适用于有序的线性表（表中的元素按照关键字有序排列）。

约束条件：仅适用于顺序存储的，已经排好序的线性表。

折半查找的过程：首先将给定值 key 与表中间位置的元素进行比较，若相等则查找成功，返回该元素的存储位置；若不相等，则只能在表的前半部分或后半部分进行查找。

查找算法描述：

将待查找的数据从小到大排序到一个表中：

设置 low = 0，hight 为表的长度 - 1，mid = (low + high)/2（low 和 high 分别为表的上界与下界）；
将给定值 key 与下标为 mid 的元素进行比较，若相等则返回 mid；
若不相等，则将表从 mid 的位置分成前后两个子表。如果 key < mid，则 high 取 mid - 1；如果 mid < key，则 low 取 mid + 1。

若循环执行到结束，则表示没有查找到数据，查找失败。

long Search_Bin(SSTable ST, KeyType key)
{
    int low = 0; high = ST.Length - 1;
    
    while(low <= high)
    {
        mid = (low + high)/2;
        if(key == ST.elem[mid]) return mid;
        else if(key < mid) high = mid - 1;
        else low = mid + 1;
    }
    
    return 0;  
}

折半查找的过程可以使用一种特殊的二叉树来进行描述，叫做判定树。判定树的节点可以使用元素的值表示，也可以使用元素在表中的下标来表示。

判定树：将中间位置的元素作为二叉树的根，左子表和右子表分别作为左子树和右子树，由此得到的二叉树称为判定树。

若有序列表有 n 个元素，将这 n 个元素构造成判定树中的节点，如果使这 n 个节点都为非叶节点（下图圆形节点）。则有 n+1 个叶节点下图方框节点），如图 7.2，补上来的 n+1 个叶节点称为外（部）节点，原来的 n 个节点称为内（部）节点。查找成功时只会走到内节点，查找失败会走到外节点。

判定树的特性：

判定树是二叉排序树（左子树结点值＜根结点值＜右子树结点值）。
判定树是平衡二叉树（平衡因子 = |左右子树深度差| <= 1）。
判定树有 n 个内（部）节点，有 n+1 个外（部）节点。

折半查找的性质：

折半查找的次数不超过判定树的深度；
具有 n 个结点的判定树的深度为 $\lfloor log_2n \rfloor + 1$。即 $折半查找的次数 <= \lfloor log_2n \rfloor + 1$。

平均查找长度计算：

为了方便讨论，设具有 n 个节点的判定树为满二叉树（则有 $n=2^h-1$，$h=log_2{n+1}$，$h$ 为树的深度），深度为 1 的节点有 1 个，深度为 2 的节点有 2 个，深度为 h 的节点有 $2^h-1$ 个。在等概率情况下，每个结点被查找的概率分布为 $P_i=$$1 \over n$，折半查找平均查找长度为：

$ASL=\sum\limits_{i=1}^{n}P_iC_i=$${1}\over{n}$$\sum\limits_{i=1}^{n}h*2^h-1=$${n+1}\over{n}$$log_2{(n+1)}-1$

当 $n$ 较大时（$n>50$），近似为 $ASL=log_2{(n+1)}-1$。

折半查找的时间复杂度为 $O(log_2 n)$，好于顺序查找的 $O(n)$。

参考：折半查找平均查找长度推导。

4.2.3 分块查找

分块查找（Blocking Search）又称索引顺序查找，查找性能介于折半查找和顺序查找之间。由于将数据分成块时繁琐麻烦，不常用。

分块查找的基本思想：

分块。将查找表中的数据分成若干块（子表），块内的元素可以使无序的，但是块间的数据必须是有序的（第一个块中的最大关键字小于第二个块中的所有数据的关键字，以此类推）；
建立索引。再建立一个索引表，索引表的每项至少包括两个基本内容：各块子表中的最大关键字、各块子表第一个元素的地址。索引表按关键字进行有序排序。

分块查找的过程分为两步：

第一步，先在索引表中确定目标数据所在的子块，可以使用折半查找或顺序查找；
第二步，在块内顺序查找。

平均查找长度计算：分块查找的平均查找长度为索引查找和块内查找的平均长度之和。将长度为 $n$ 的查找表均匀地分为 $b$ 块，每块有 $s$ 个记录（$n=b*s$），设索引查找和块内查找的平均查找长度分别为 $L_I, L_s$，则分块查找的平均查找长度为 $ASL=L_I+L_s$。有以下两种情况：

块内和索引表中均采用顺序查找，则平均查找长度为：

$ASL=L_I+L_s$

$=$${1}\over{b}$$\sum\limits_{j=1}^{b}j + $${1}\over{s}$$\sum\limits_{i=1}^{s}i$

$=$${b+1}\over{2}$$+$${s+1}\over{2}$ $=$${1}\over{2}$$($${n}\over{s}$$+s)+1$

此时，若 $s=\sqrt{n}$，则平均查找长度取最小值 $ASL_{min}=\sqrt{n}+1$；

这个值比顺序查找 $O(n)$ 有了很大改进，但远不及折半查找 $O(log_2 n)$。
索引表采用折半查找时，块内采用顺序查找，则平均查找长为：

$ASL=L_I+L_s$$=\lceil log_2(b+1) \rceil+$${s+1}\over{2}$

分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。其缺点是：要增加一个索引表的存储空间并对初始索引表进行排序运算。

4.3 树型查找

前面介绍的 3 种查找方法都是用线性表作为查找表的组织形式，其中折半查找效率较高。但由于折半查找要求表中记录按关键字有序排列，且不能用链表做存储结构，因此，当表的插入或删除操作频繁时，为维护表的有序性，需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消折半查找的优点。所以，线性表的查找更适用于静态查找表，若要对动态查找表进行高效率的查找，可采用几种特殊的二叉树作为查找表的组织形式，在此将它们统称为树表。

4.3.1 二叉排序树

二叉排序树（Binary Sort Tree）又称为二叉查找树或二叉搜索树，它是一种对排序和查找都很有用的特殊二叉树。

二叉排序树的定义：

若左子树非空，则左子树上所有节点的值均小于根节点的值；
若右子树非空，则右子树上所有节点的值均大于根节点的值；
左、右子树分别是一棵二叉排序树。

重要性质：二叉排序树是递归定义的，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

二叉排序树，常适用二叉链表作为存储结构，根据关键字来对二叉排序树进行操作，定义如下：

typedef struct
{
    KeyType key;	// 关键字
    InfoType otherinfo;	// 其他数据
}ElemType;

typedef struct BSTNode
{
    ElemType data;			// 数据项
    struct BSTNode *lchild, rchild;	// 左右孩子指针
}BSTNode, *pBSTNode;

1、二叉排序树的查找	2、二叉排序树的插入	3、二叉排序树的创建	4、二叉排序树的删除

一、二叉排序树的查找

因为二叉排序树可以看成是一个有序表，所以在二叉排序树上进行查找和折半查找类似，可分为递归查找和非递归查找。

递归查找方法。

BSTNode Search_Recursion(BitTree T, ElemType key)
{
  if(!T || T->data == key) return T;					// 查找结束（失败/成功）
  else if(key < T->data) return Search_Recursion(T->lchild, key);	// 递归查找左子树
  else return Search_Recursion(T->rchild, key);				// 递归查找右子树
}

非递归查找方法。

BSTNode Search_Recursion(BitTree T, ElemType key)
{
  while(T != NULL && T->data != key)
  {
    if(key < T->data) T = T->lchild;
    else T = T->rchild;
  }
  
  return T;	// 查找结束（失败/成功）
}

查找性能：最坏情况下，n 个节点的树深度为 n，其平均查找长度为 ${n+1}\over{2}$$O(n)$（和顺序查找相同）；最好的情况下，二叉排序树的形态和折半查找的判定树相似，其平均查找长度和 $O(log_2n)$ 成正比。

二、二叉排序树的插入

二叉排序树的插入操作是以查找为基础的，需要从根结点向下查找，当树中不存在关键字等于 key 的结点时才进行插入。新插入的结点一定是一个叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

插入结点的过程如下：

若原二叉排序树为空，则直接插入结点；
若二叉排序树非空，则将要插入的 key 与根结点的关键字进行比较：
- 若 key 小于根节点的值，则插入到左子树；
- 若 key 大于根节点的值，则插入到右子树。

递归算法：

bool InsertBST(BitTree &T, ElemType key)
{
  if(T == NULL)	// 原树为空，新插入的 key 为根结点
  {
    T = (BiTree)malloc(sizeof(BSTNode));
    T->data = key;
    T->lchild = NULL; T->rchild = NULL;
    return true;
  }
  
  else if(key == T->data) 
    return false;	// 树中存在相同关键字的结点，插入失败
  
  else if(key < T->data) 
    return InsertBST(T->lchild, key);
  else 
    return InsertBST(T->rchild, key);
}

性能分析：二叉排序树插入的基本过程是查找，所以时间复杂度同查找一样，是 $O(log_2n)$。

三、二叉排序树的创建

bool CreateBST(BiTree &T, KeyType strt[], int n)
{
  if(n <= 0) return false;
  
  T = NULL;	// 初始时 T 为空树
  
  int i = 0;
  while(i < n)
    InsertBST(T->rchild, strt[i]);
  return true;
}

性能分析：假设有 $n$ 个结点，则需要 $n$ 次插入操作，而插入一个结点的算法时间复杂度为 $O(log_2n)$，所以创建二叉排序树算法的时间复杂度为 $O(nlog_2n)$。

四、二叉排序树的删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。删除操作的实现过程按 3 种情说来处理：

若被删除结点 z 是叶结点，则直接删除，不会破坏二叉排序树的性质。
若结点 z 只有一棵左子树或右子树，则让 z 的子树成为 z 父结点的子树，替代 z 的位置。
若结点 z 有左、右两棵子树，则有三种方式：
- 方法一：使用左子树中值最大的节点代替被删除的节点（使用中序遍历）。
- 方法二：使用右子树中值最小的节点代替被删除的节点。
- 方法三：使被删除节点的左子树成为父节点的左子树，被删除节点的右子树成为左子树中最大节点的右子树。

如下图：上述方法一、方法三对应于左上和左下；方法二对应于右上和右下。

4.3.2 平衡二叉树

树的高度越小，查找速度越快。因此，希望二叉树的高度应尽可能小。二叉排序树查找性能在 $[O(n), O(log_2n)]$ 区间。

平衡二叉树（Balanced Binary Tree），简称平衡树，又叫做 AVL 树，要么是空树，要么是具有以下性质的二叉排序树：

|左右子树深度差| <= 1；
左子树和右子树分别都是平衡二叉树。

平衡因子：节点平衡因子 = 左子树深度 - 右子树的深度。平衡二叉树的平衡因子只能为 -1, 0, 1。

平衡调整：平衡二叉树是二叉排序树，每当往平衡二叉树中插入新的节点时，首先按照二叉排序树的方式进行插入，若插入的节点破坏了平衡二叉树的特性，需对平衡二叉树进行调整（先插入，再调整）。

调整的方法是：找到离新插入节点最近且平衡因子绝对值大于 1 的祖先节点，以该祖先节点为根的子树称为最小不平衡子树，可将重新平衡的范围局限在这棵子树。

一般情况下，假设最小不平衡子树的根节点为 A，平衡调整的规律主要有以下 4 种方式：

LL 型（右单旋转）。由于在节点 A 的左孩子（L）的左子树（L）上插入了新的节点，A 的平衡因子由 1 增加到 2，导致以 A为根的子树失去平衡：

需要对整棵子树进行一次向右旋转的操作：将 A 的左子树、A、A 的右子树一起进行旋转（即旋转整棵最小不平衡子树）。
- （1）按照二叉排序树插入方式，先将节点插入到树中，成为叶子结点；
- （2）从该叶节点开始，以第一个平衡因子绝对值等于 2 的祖先节点为根的子树，进行向右单次旋转；
- （3）使 A 节点的左孩子 B 成为该子树的根节点，B 节点的原右子树成为 A 节点的左子树。
RR（左单旋转）。由于在节点 A 的右孩子（R）的右子树（R）上插入了新的节点，A 的平衡因子由 -1 减至 -2，导致以 A为根的子树失去平衡，

需要对整棵子树进行一次向左旋转的操作：将 A 的左子树、A、A 的右子树一起进行旋转（即旋转整棵最小不平衡子树）。
- （1）按照二叉排序树插入方式，先将节点插入到树中，成为叶子结点；
- （2）从该叶节点开始，以第一个平衡因子绝对值等于 2 的祖先节点为根的子树，进行向左单次旋转；
- （3）使 A 节点的右孩子 B 成为该子树的根节点，B 节点的原左子树成为 A 节点的右子树。
LR 型（先左后右旋转）。由于在节点 A 的左孩子（L）的右子树（R）上插入了新的节点，A 的平衡因子由 1 增加到 2，导致以 A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转：

LRL、LRR：先对以 B 为根节点的子树进行左旋转（旋转方法同 RR 型），然后以 A 节点为根的树整体进行右旋转（旋转方法同 LL 型）。
- （1）按照二叉排序树插入方式，先将节点插入到树中，成为叶子结点；
- （2）从该叶节点开始，找到以第一个平衡因子绝对值等于 2 的祖先节点为根的子树（最小不平衡子树），先向左旋转最小不平衡子树的左子树（方法同 RR 型），然后向右旋转整棵最小不平衡子树（方法同 LL 型）。
RL 型（先右后左旋转）。由于在节点 A 的右孩子（R）的左子树（L）上插入了新的节点，A 的平衡因子由 -1 减至 -2，导致以 A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转：

RLR、RLL：先对以 B 为根节点的子树进行右旋转（旋转方法同 LL 型），然后以 A 节点为根的树整体进行左旋转（旋转方法同 RR 型）。
- （1）按照二叉排序树插入方式，先将节点插入到树中，成为叶子结点；
- （2）从该叶节点开始，找到以第一个平衡因子绝对值等于 2 的祖先节点为根的子树（最小不平衡子树），先向右旋转最小不平衡子树的左子树（方法同 LL 型），然后向左旋转整棵最小不平衡子树（方法同 RR 型）。

二叉平衡树节点的删除：

4.3.3 红黑树

红黑树是具有特殊性质的二叉排序树，是一种近似平衡的二叉排序树。已知二叉平衡树的查找性能为 $[O(n), O(log_2n)]$，树的高度越小查找性能越好。

对于一棵动态查找树，如果插入和删除的操作比较少，查找操作比较多，采用二叉平衡树（AVL）比较合适，否则采用红黑树比较合适。

红黑树动态插入和删除在线网站：美国旧金山大学—Red/Black Tree。

红黑树是一棵二叉排序树，在每个节点上增加了一个颜色成员（可以是红色或黑色），在 AVL 树的平衡标准上进一步放宽条件，具有以下性质：

每个节点都有颜色，红色或者黑色。
根节点是黑色。
叶节点都是虚构的外部节点，都是黑色的。
不存在两个相邻的红节点。
对每个节点，从该节点到任一叶节点的简单路径（不构成回路）上，所含黑节点数量相同。

红黑树具有以下特性：

从某个节点到任一叶节点的简单路径（不构成回路）上，所含黑节点数量称为该节点的黑高（black-height）。根节点的黑高称为红黑树的黑高。
从某个节点到达叶节点的最长路径长度 <= 2 倍最短路径长度。（最短路径上一般是全黑节点）
有 n 个内部节点的红黑树的高度 $h <= 2log_2{(n+1)}$。
红黑树中新插入的节点，初始颜色需要着色为红色。

红黑树是一种近似平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明，在当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。

1、红黑树的节点插入	2、红黑树的节点删除

一、红黑树的节点插入

新节点的插入过程和二叉排序树基本相同，只不过节点插入后需要对树中节点颜色调整和旋转，以满足红黑树上述的 5 条性质。在一棵具有 n 个内部节点的红黑树中插入一个新节点的时间不超过 $O(log_2n)$。

红黑树中新插入的节点，初始颜色需要着色为红色。如果插入的节点是黑色，那么这个节点所在路径比其他路径多出一个黑色节点（不满足性质 5），这个调整起来会比较麻烦。如果插入的节点是红色，此时所有路径上的黑色节点数量不变，仅可能会出现两个连续的红色节点的情况（破坏性质 4）。如果是添加根节点，则将节点设定为黑色。

如上所述，当插入的新节点将其颜色着色为红色的话，最坏情况下只会破坏性质 4（出现两个连续红色的节点），对此进行调整即可（较为简单）。

设节点 z 为新插入的节点，插入的过程如下：

（1）用二叉排序树插入的方法插入新节点，并将节点 z 着色为红色。若节点 z 的父节点为黑色，则无需调整（此时就是一棵标准的红黑树）。

（2）如果 z 节点是根节点，将 z 着色为黑色（树的黑高增 1），结束。

（3）如果 z 节点的父节点 z.p 为红色，则可能有以下 3 种情况需要进行调整，区别在于 z 的叔节点 y 是否是红色：

z 的叔节点 y 是黑色的（则 y 一定是外节点，否则不满足性质 5），且父节点 z.p 是祖父节点 z.p.p 的左孩子（z.p.p 一定是黑色）：
- z 节点是一个左孩子。LL 型（即 z 是爷结点的左孩子的左孩子），先带着爷节点一起向右旋转，然后交换 z.p 和 z.p.p 的颜色。
- z 节点是一个右孩子。LR 型，需要先左旋转（不带爷节点，颜色不调整），此时将相邻的两个红节点中深度最深的红节点改为 z 节点，再右旋转（使用 LL 型旋转调整颜色法，带爷节点）。
z 的叔节点 y 是黑色的（则 y 一定是外节点，否则不满足性质 5），且父节点 z 是祖父节点 z.p.p 的右孩子：
- z 节点是一个右孩子。RR 型，先带着爷节点一起向左旋转，然后交换 z.p 和 z.p.p 的颜色。
- z 节点是一个左孩子。RL 型，需要先右旋转（不带爷节点，颜色不调整），此时将相邻的两个红节点中深度最深的红节点改为 z 节点，再左旋转（使用 RR 型旋转调整颜色法，带爷节点）。
z 的叔节点 y 是红色的，父节点 z 是祖父节点 z.p.p 的左孩子或右孩子：

z 节点是一个左孩子或右孩子。上移 LL、RR、LR、RL 型，调整方法只需要染色，无需旋转：将 z.p 和 y 都变成黑色，z.p.p 变成红色，然后将 z.p.p 当做一个新的节点 z 进行循环处理。相当于 z 在树中上移两层。

二、红黑树的节点删除

删除过程较复杂，按照二叉排序树的节点删除方法进行删除。若节点有两个孩子节点，则不知能直接删除，而要找到该节点的中序遍历下直接后继（或前驱）节点进行填补，即右子树中的最小节点。这样一来，删除目标节点的问题就可转换为删除该节点的后继节点（中序遍历）。由于后继节点至多只有一个孩子节点，这样就转换为待删节点是叶节点或仅有一个孩子的情况。即以下两种情况：

待删节点没有孩子节点。
待删节点只有左子树节点或右子树节点。

假设待删结点为 y，x 是用来替换 y 的结点（注意，当 y 是终端结点时，× 是黑色的 NULL 结点)。删除 y 后将导致先前包含 y 的任何路径上的黑结点数量减 1，因此 y 的任何祖先都不再满足性质 ⑤，简单的修正办法就是将替换 y 的结点 × 视为还有额外一重黑色，定义为双黑结点（x 节点）。也就是说，如果将任何包含结点 × 的路径上的黑结点数量加 1，在此假设下，性质 ⑤ 得到满足，但破坏了性质 ①。于是，删除操作的任务就转化为将双黑结点恢复为普道结点。。

删除方法：先看被删节点的颜色，接着看该节点有几个子树，然后继续如下的方法处理：

红色节点删除总结：
- 红色节点是叶节点，直接删除。
- 红色节点有子树，使用左子树最大节点（或右子树最小节点）上移代替，此时转换为删除上移前的节点，继续处理。
黑色节点删除方法总结：
- 被删节点有子树，使用左子树最大节点（或右子树最小节点）上移代替，并将上移的子节点其着成黑色，此时转换为删除上移前的节点，继续处理；
- 被删节点没有子树，如果是根节点直接删除，否则再看符合RR、RL、LL、LR 中的哪一种。

具体如下：

（1）如果待删结点只有右子树或左子树，若子树只有一个结点，则必然是红色，否则会破坏性质 ⑤，所以待删的节点一定是黑色。即：待删节点为黑色，且只有一个红色的子节点。删除方法：红色子节点上移代替待删的节点，并将上移的子节点其着成黑色。

（2）如果待删结点有两个红色子树节点，则任选其一个红色子节点上移取代，并将上移的子节点其着成黑色。

（3）待删节点是黑色，且该节点没有子树节点。区别主要在于双黑节点 x 的兄弟节点 w 及 w 的孩子节点的颜色不同，主要有以下几种情况：

x 是左孩子，x 的兄弟节点 w 是黑色的，w 至少有一个红色子节点。
- w 的右孩子是红色的，左孩子是黑色（外部节点）。RR 型（即红结点是其爷结点的右孩子的右孩子），交换 w 和 x.p 的颜色，把 w 的右孩子着色为黑色，最后对以 x.p 为根节点的子树进行左旋转。
- w 的左孩子是红色的，右孩子是黑色（外部节点）。RL 型（即红结点是其爷结点的右孩子的左孩子），交换 w 和左孩子的颜色，然后对以 w 为根节点的子树进行右旋，此时变成 RR 型，但是 w 节点更新为 x 的兄弟节点。接着按 RR 型再调整一次即可。
- w 的左右孩子是红色的，按照 RR 型处理即可（比 RL 型简单）。
x 是右孩子，x 的兄弟节点 w 是黑色的，w 至少有一个红色子节点。
- w 的左孩子是红色的，右孩子是黑色（外部节点）。LL 型，交换 w 和 x.p 的颜色，把 w 的左孩子着色为黑色，最后对以 x.p 为根节点的子树进行右旋转。
- w 的右孩子是红色的，左孩子是黑色（外部节点）。LR 型，交换 w 和右孩子的颜色，然后对以 w 为根节点的子树进行左旋，此时变成 LL 型，但是 w 节点更新为 x 的兄弟节点。接着按 LL 型再调整一次即可。
- w 的左右孩子是红色的，按照 LL 型处理即可（比 LR 型简单）。
x 的兄弟节点 w 是黑色的，且 w 是有两个黑色子节点（外节点）。

将 w 着成红色，x.p 着成黑色。
- 如果 x.p 原来的颜色为红色，结束。
- 如果 x.p 原来的颜色为黑色，则需要将 x.p 更新为 x 节点，当成被删除的节点处理（相当于 x 上移），继续处理。
x 的兄弟节点 w 是红色的。此时 w 的左右孩子和父节点必然是黑色。

处理方法：交换 w 和 x.p 的颜色，然后对以 x.p 为根的子树做一次左旋，接着按 RR、RL、LL、LR 的方法处理。