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

简介: 本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。

树与二叉树的应用

文章目录:

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

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

1.1 带权路径长度

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

image.png

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

1.2 哈夫曼树

1.2.1 哈夫曼树的构造

构造步骤:
:one: 找到当前权值最小的两个结点(包括两个结点构造出的新结点)
:two: 将这两个结点通过一个构造出的父结点联系起来,父结点的权值是他俩权值之和。
:three:重复上面的步骤,直到没有结点可以添加

哈夫曼树特点:

  • 每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越大
  • 哈夫曼树的结点总数为2n-1
  • 哈夫曼树中不存在度为1的结点
  • 哈夫曼树并不唯一,但WPL必然相同且为最优。
    image.png

引入1.3 :哈夫曼树的应用->哈夫曼编码,简单理解成,把英文字母用最少的比特表达出来。常用的字母,访问的频率高,权值就高,尽可能的放在树层次低的位置,好进行查找。而构造哈夫曼树,就是用编码的字母配上上他们的权值,构造出一个哈夫曼树,然后做分支算0,右分支算1,将字母编码,不重不漏,且最优,访问时间最快。

1.3 哈夫曼编码

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

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

2.并查集

2.1 并查集的三要素

2.1.1 并查集的逻辑结构

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

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

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

2.1.2 并查集的存储结构

image.png

解释说明:

  • 存储结构是静态数组,数组下标代表元素是哪个,数组中存储的值,代表它的父结点的下标是哪个,如果是-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:被删除的结点既有左子树又有右子树

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

image.png

3.6 查找效率分析(ASL)

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

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

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

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

查找失败
(判断出是空子树需要的查找次数这种情况的数量)/情况数
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:

image.png

相关文章
|
11天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
|
19天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
14 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
16天前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
21 0
|
19天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
16 0
|
21天前
05(数据结构考研)树相关操作代码
05(数据结构考研)树相关操作代码
26 0
|
19天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
19天前
初步认识栈和队列
初步认识栈和队列
45 10
|
13天前
数据结构(栈与列队)
数据结构(栈与列队)
15 1
|
19天前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
34 3