二叉树的进阶

二叉查找树(Binary Search Tree, BST)

二叉查找树，也称二叉排序树。其特性是：

若左子树非空，则左子树上所有结点的值均小于根结点的值。
若右子树非空，则右子树上所有结点的值均大于根结点的值。
左右子树也分别是二叉查找树。

二叉查找树的基本操作的时间复杂度和树的高度成正比，即对于一棵$n$个结点的完全二叉树，操作的最坏运行时间是$O(\log_2 n)$。

二叉查找树的构造

设$K=(k_1,k_2,k_3,…,k_n)$为具有$n$个数据元素的序列。从序列的第一个元素开始，依次取序列中的元素，按照下述原则将$k_i$插入到二叉树中:

若二叉树非空，则$k_i$作为二叉查找树的根结点。
若二叉树非空，则将$k_i$与该二叉树的根结点的值进行比较, 若$k_i$小于根结点的值,则将$k_i$插入到根结点的左子树中；否则,将$k_i$插入到根结点的右子树中。将$k_i$按照上述原则递归插入到左子树或者右子树中。

二叉查找树的插入

原理和构造一致。

二叉查找树新结点的插入也有递归算法和非递归算法。

二叉查找树的删除

删除原则：

被删除结点为叶结点，则直接删除；
被删除结点无左子树,则用右子树的根结点取代被删除结点；
被删除结点无右子树，则用左子树的根结点取代被删除结点；
被删除结点的左、右子树都存在，则用被删除结点的右子树中值最小的结点（或被删除结点的左子树中值最大的结点）取代被删除结点。因为是最小/最大的结点，所以选择的是子树的叶结点。

二叉查找树的查找

查找原则：

若二叉查找树为空，则查找失败。
若二叉查找树非空，则将被查找元素与二叉排序树的根结点的值进行比较：
- 若等于根结点的值,则查找成功；
- 若小于根结点的值,则到根结点的左子树中重复上述查找过程;
- 若大于根结点的值,则到根结点的右子树中重复上述查找过程;

二叉查找树新结点的查找也有递归算法和非递归算法。

查找效率

平均查找长度(Average Search Length, ASL)：确定一个元素在树中位置所需要进行的元素间的比较次数的期望值(平均值)。
计算公式：

$ASL= \sum_{i=1}^n p_ic_i$

其中，$n$是二叉树中结点的总数；$p_i$表示查找第$i$个元素的概率；$c_i$表示查找第$i$个元素需要进行的元素之间的比较次数。

普通二叉树的缺陷

假设被插入的元素序列是单调序列，那么就成为了退化二叉树，查找时间复杂度为$O(n)$。为了应对左右子树深度差距较大的情况，引入了平衡二叉树。

平衡二叉树（Adelson-Velskii and Landis, AVL）

平衡二叉树又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过$1$。

平衡因子：结点的左右子树的高度差称为结点的平衡因子。\
左旋：\
右旋：\
参考文章：https://blog.csdn.net/m0_57466457/article/details/127400601

平衡二叉树的插入

插入原则：

将新结点按照二叉树的插入原则插入到平衡二叉树中；
检查新结点插入路径上的结点是否因为此次操作导致了不平衡，若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于$1$的结点$A$；
对以$A$为根的子树，在保持二叉查找树的前提下，按照规律调整结点的位置关系。

调整规律：

LL平衡旋转（右单旋转）
RR平衡旋转（左单旋转）
LR平衡旋转
RL平衡旋转

绘制旋转图解

平衡二叉树的删除

删除原则：

使用二叉查找树的方式对结点$w$进行删除操作。
若导致了不平衡，则从结点$w$向上回溯，找到第一个不平衡的结点$z$。对以结点$z$为根的二叉树进行调整操作。

平衡二叉树的缺陷

为了保持二叉树的平衡，在每次插入和删除操作后，会非常频繁地调整全树的拓扑结构，代价较大，所以引入了红黑树的结构。

红黑树(Red Black Tree)

红黑树是一种二叉查找树，在每个结点上添加一个存储位表示结点的颜色，$Red$或$Black$。并且，引入外部叶结点($NIL$)，保证红黑树的每个内部结点的左、右孩子均非空。

红黑树的的红黑性质：

性质1：每个结点只有红色和黑色。
性质2：根结点是黑色的。
性质3：外部叶结点都是黑色的。
性质4：不存在两个相邻的红结点。（红色父结点的两个孩子均为黑色）
性质5：对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量相同。

简单路径：其中每个结点只能被访问一次，且没有重复的边的路径。

红黑树的结点插入

新插入红黑树的结点初始着为红色。新结点的插入容易破坏性质4，出现两个连续的红色结点，所以需要使用染色和旋转的方式使之重新满足红黑树的性质。

设新插入的结点$z$：

用二叉查找树插入法插入，并将结点$z$着为红色，若结点$z$的父结点是黑色，无需调整。
若结点$z$是根结点，则将$z$着为黑色，结束。
若结点$z$不是根结点，且$z$的父结点是红色的，分为三种情况，区别在于叔结点$y$的颜色不同。
1. 叔结点$y$是黑色的，$z$是一个右孩子：（父结点+$z$结点）先左旋，整体再右旋。（旋转）
2. 叔结点$y$是黑色的，$z$是一个左孩子：整体右旋。（旋转）
3. 叔结点$y$是红色的：父结点和叔结点染成黑色，爷结点染成红色。（染色）

手绘结点插入的示意图。

红黑树的结点删除

如果说插入新结点可能导致两个连续的红结点，那么删除的结点是黑结点的话，会破坏性质5。

后续二轮复习学习。

树的应用

哈夫曼树(Huffman Tree)

路径：从树的一个结点到另一个结点之间的分支。

路径长度：路径上的分支数目。

权：树中结点被赋予的一个表示某种意义的值。

带权路径长度(Weighted Path Length)：所有叶结点的带权路径长度之和。

$WPL=\sum_{i=0}^n w_il_i$

其中，$w_i$是第$i$个叶结点的权，$l_i$是叶结点到根结点的路径长度。

在含有$n$个带权叶结点的二叉树中，带权路径长度最小的二叉树称为哈夫曼树。

哈夫曼树的构造

给定$n$个权值分别$w_1,w_2,…,w_n$的结点，构造哈夫曼树的算法如下：

将这$n$个结点分别作为$n$棵含有一个结点的二叉树，构成森林$F$。
构造一个新结点，从$F$中选取根结点权值最小的两棵二叉树作为新结点的左右子树，并且将新结点的权值设置为左、右两棵子树的根结点权值和。
从F中删去选取的两棵树，同时将新得到的树加入$F$中。
重复步骤2和3，直到$F$中只剩下一棵树为止。

哈夫曼编码

在数据通信中，如果对每个字符用长度相等的二进制位表示，则称为固定长度编码；如果不等长，则称为可变长度编码。

前缀编码：没有一个编码是另外一个编码的前缀。

二叉树可以实现二进制前缀编码。

哈夫曼编码：假设我们需要对一个单词编码，每个待编码的字符都是哈夫曼树的叶结点，结点的权值是它出现的频次。

哈夫曼树的带权路径长度可视为最终编码得到的二进制编码的长度，即各个字符的编码长度 × 字符出现的频次。

并查集

并查集是一种简单的集合表示，它支持以下三种操作：

初始化：将集合$S$中的每个元素都初始化只有一个单元素的子集合。
合并子集合：把集合$S$中的子集合$S_2$并入子集合$S_1$，要求这两个子集合不相交。
查找某个元素：查找集合$S$中某个元素所在的子集合，并返回该子集合的根结点。

并查集的实现

定义父结点指针数组$Father[SIZE]$，$Father[i]$代表集合中第$i$个元素的父结点，如果该结点是根结点，则$Father[i]=-1$。

并查集的初始化

1
2
3

for (int i=0; i < SIZE; i++) {
    Father[i] = -1;
}

并查集的合并(Union)

if (root1 == root2) {
    return;
}
Father[root2] = root1;

合并操作的时间复杂度是$O(1)$。

并查集的查找(Find)

while(Father[node] >= 0) {
    // 还有父结点
    node = Father[node]; 
}
return node;

查找操作的时间复杂度是$O(d)$，$d$为树的深度。

在极端情况下，$n$个元素构成的集合树深度为$n$，那么查找操作的最坏时间复杂度是$O(n)$，所以需要对并查集的操作进行优化。

并查集实现的优化

优化思路：在合并操作前判断两个子集的元素数量，令成员少的根指向成员多的根，即把小树合并到大树。可以开一个数据保存根结点的的元素数量$Member[SIZE]$。

二叉树进阶和树的应用