树与二叉树的应用
文章目录:
1.哈夫曼树与哈夫曼曼编码
引入1.1:在学习哈夫曼树和哈夫曼编码之前预备知识
1.1 带权路径长度
结点的权:理解为权重,重要性。
结点的带权路径长度:树根到该结点的路径长度(经过的边数✖️该结点的权值)
树的带权路径长度(WPL):树中所有叶结点的带权路径长度之和。
引入1.2 :在含有n个带权叶结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树。
1.2 哈夫曼树
1.2.1 哈夫曼树的构造
构造步骤:
:one: 找到当前权值最小的两个结点(包括两个结点构造出的新结点)
:two: 将这两个结点通过一个构造出的父结点联系起来,父结点的权值是他俩权值之和。
:three:重复上面的步骤,直到没有结点可以添加
哈夫曼树特点:
- 每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越大
- 哈夫曼树的结点总数为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 二叉排序树的删除(重点)
二叉排序树根据删除结点的情况可分为三种情况:
先搜索找到目标结点:
:one:若被删除结点z是叶结点,则直接删除,不会破坏二叉排序树的性质。
:two:若被删除的结点只有左子树或右子树,直接让它的那个子树代替它的位置即可
:three:被删除的结点既有左子树又有右子树
- 从左子树找到最大的结点,代替它的位置(即左子树最右下的结点)
- 从右子树找到最小的结点,代替它的位置(即右子树最左下的结点)
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~2~n⌋+1,平均查找长度=O(log~2~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~=0
n~1~=1
n~2~=2
n~3~=4
总结归纳出,n~h~=n~h-1~+n~h-2~+1
可以证明n个结点的平衡二叉树的最大深度是O(log~2~n),平衡二叉树的平均查找长度为O(log~2~n)
4.5 删除操作
:one:删除结点
若删除的结点是叶子,直接删
若删除的结点只有一个子树,用子树顶替删除位置
若删除的结点有两颗子树,用前驱(或后继结点)顶替,并转换为对前驱或后继结点的删除
:two: 一路向上找到最小不平衡子树,若无则直接结束
:three:找最小不平衡子树下,"个头"最高的儿子和孙子
:four:根据孙子的位置,调整平衡(LL/RR/LR/RL)
:five: 如果不平衡向上传导,继续:two: