数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树

树与二叉树的应用

文章目录：

1.哈夫曼树与哈夫曼曼编码

引入1.1：在学习哈夫曼树和哈夫曼编码之前预备知识

1.1 带权路径长度

结点的权：理解为权重，重要性。
结点的带权路径长度：树根到该结点的路径长度（经过的边数✖️该结点的权值）
树的带权路径长度（WPL):树中所有叶结点的带权路径长度之和。

引入1.2 ：在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。

1.2 哈夫曼树

1.2.1 哈夫曼树的构造

构造步骤：
1️⃣ 找到当前权值最小的两个结点（包括两个结点构造出的新结点）
2️⃣ 将这两个结点通过一个构造出的父结点联系起来，父结点的权值是他俩权值之和。
3️⃣重复上面的步骤，直到没有结点可以添加

哈夫曼树特点：

• 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
• 哈夫曼树的结点总数为2n-1
• 哈夫曼树中不存在度为1的结点
• 哈夫曼树并不唯一，但WPL必然相同且为最优。
  
  引入1.3 ：哈夫曼树的应用->哈夫曼编码，简单理解成，把英文字母用最少的比特表达出来。常用的字母，访问的频率高，权值就高，尽可能的放在树层次低的位置，好进行查找。而构造哈夫曼树，就是用编码的字母配上上他们的权值，构造出一个哈夫曼树，然后做分支算0，右分支算1，将字母编码，不重不漏，且最优，访问时间最快。

1.3 哈夫曼编码

固定长度编码：每个字符用相等长度的二进制位表示
可变长度编码：允许对不同字符用不等长长的二进制位表示
前缀编码：若没有
一个编码是另一个编码的前缀，则称这样的编码为前缀编码。

特点：哈夫曼树不唯一，哈夫曼编码也不唯一，但是WPL是一样的

2.并查集

2.1 并查集的三要素

2.1.1 并查集的逻辑结构

并查集划分不同的集合。
将各种元素划分为若干互不相交的子集。

让这些子集组成一颗树，指向一个子集的根结点

根据逻辑结构描述基本操作：
查：如查找两个结点，是否属于一个集合，两个结点分别查到对应集合树的根结点，并比较根结点是否相同
并：将一个子树的根结点，放到另一根子树根结点的下面，做它的孩子

2.1.2 并查集的存储结构

解释说明：

• 存储结构是静态数组，数组下标代表元素是哪个，数组中存储的值，代表它的父结点的下标是哪个，如果是-1，代表没有父结点，即就是根结点
• 注意，这个树的箭头，是由孩子指向双亲的

集合的两个操作：
查操作：从一个结点出发，一步一步找到根结点
并操作：将一个结点的存储值，改成合并的结点的下标。

2.2 并查集的优化

2.2.1 初步优化（并操作优化）

引入思考：

我们希望并查集的树是越宽越好，因为越深我们查找起来越慢，所以说，在并操作这个步骤，有可以改进的地方。我们应该确定两颗树，到底谁应该是谁的孩子，我们的核心目的是让更多的结点在树中的位置离根结点更近，所以，通过结点的个数确定两颗树的关系，结点少的做结点多的孩子，即小树合并到大树

存储结构的改变：

• 根结点存储的值不再是-1，而是根据他所构成的树所有的结点数确定这个值，如他有6个结点，根结点值就是-6，这样方便两个树比较结点数。
• 然后合并之后，把大树的值改成他俩原先的存储值之和，小树根存储值改为大树下标

2.2.2 终极优化（查操作优化即压缩存储）

引入思考：

我们希望并查集的树越宽越好，我们当然可以把某一段树放到根结点下面，降低他的深度，这个操作，我们在每次查找的过程中实现，即查找某一个点的根结点，然后再他包括他经过的所有结点放到根结点下方。

• 在这个过程中，修改途径结点的存储值，一步到位直接存储根结点的下标。

3.二叉排序树

3.1 二叉排序树的定义

二叉排序树，又称二叉查找树(BST)
一颗二叉树或者空二叉树，或者具有如下性质的二叉树：

• 左子树上所有结点的关键字均小于根结点的关键字
• 右子树上所有结点的关键字均大于根结点的关键字
• 左子树和右子树又各是一颗二叉排序树

3.2 二叉排序树的查找

从根结点出发，比根结点小走左子树，比根结点大走右子树，每次对比根结点，数值相等则查找成功，找到空子树则查找失败

3.3 二叉排序树的插入

若原二叉排序树为空，则直接插入结点，否则根据关键字先找插入位置，再进行插入操作，小的插在左边，大的插到右边

3.4 二叉排序树的构造

多次使用二叉排序树插入操作

注意：

• 不同的关键字可能得到同款二叉排序树
• 也可能得到不同款二叉排序树

3.5 二叉排序树的删除(重点)

二叉排序树根据删除结点的情况可分为三种情况：

先搜索找到目标结点：
1️⃣若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
2️⃣若被删除的结点只有左子树或右子树，直接让它的那个子树代替它的位置即可
3️⃣被删除的结点既有左子树又有右子树

• 从左子树找到最大的结点，代替它的位置(即左子树最右下的结点）
• 从右子树找到最小的结点，代替它的位置(即右子树最左下的结点）

3.6 查找效率分析(ASL)

查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间的复杂度。

具体实例求查找成功的平均查找长度ASL

查找成功：
(查询次数✖️同等查询次数结点数)➗结点总数
ASL=（1*1+2*2+3*4+4*1）/8=2.625

具体实例求查找失败的平均查找长度ASL

查找失败
(判断出是空子树需要的查找次数*这种情况的数量)/情况数
ASL=（3*7+4*2）/9=3.22

总结：
查找效率分析
最好情况：
n个结点的二叉树最小高度为⌊log₂n⌋+1，平均查找长度=O(log₂n）
最坏情况：
每个结点只有一个分支，树高h=结点n。平均查找长度O（n）

4.平衡二叉树

4.1 平衡二叉树的定义

平衡二叉树：简称AVL树，树上任一结点的左子树和右子树的高度之差不超过1

4.2 插入操作

在二叉排序树的插入操作中，不难得知，插入一个结点后，平衡二叉树可能就不平衡了，所以在每次插入完之后，我们就需要检查平衡二叉树，找出最小不平衡子树，然后调整最小不平衡子树。

4.3 插入新结点如何调整不平衡问题

根据插入位置不同，分为四种类型

• LL(插入在左孩子的左子树）
• RR(插入在右孩子的右子树）
• LR(插入在左孩子的右子树）
• RL(插入在右孩子的左子树）

为什么假定所有子树的高度都是H

如何调整最小不平衡子树？
记法：孩子反向旋转，左旋右旋指的是往上旋转
LL：左孩子右旋成为根结点，多出来的右子树，移动到原先根结点的左子树
RR：右孩子左旋成为根结点，多出来的左子树，移动到原先根结点的右子树
LR：右子树先左旋，再右旋
RL：左子树先右旋，再左旋

4.4 查找效率分析

我们以n_h表示深度为h的平衡树中含有的最少结点数
不难推出：
n₀=0
n₁=1
n₂=2
n₃=4
总结归纳出，n_h=n_h-1+n_h-2+1
可以证明n个结点的平衡二叉树的最大深度是O(log₂n)，平衡二叉树的平均查找长度为O(log₂n)

4.5 删除操作

1️⃣删除结点
若删除的结点是叶子，直接删
若删除的结点只有一个子树，用子树顶替删除位置
若删除的结点有两颗子树，用前驱（或后继结点)顶替，并转换为对前驱或后继结点的删除

2️⃣ 一路向上找到最小不平衡子树，若无则直接结束
3️⃣找最小不平衡子树下，"个头"最高的儿子和孙子
4️⃣根据孙子的位置，调整平衡(LL/RR/LR/RL)

5️⃣ 如果不平衡向上传导，继续2️⃣