导图社区 数据结构_5_2树的应用
参考王道计算机考研《数据结构》,自主归纳总结知识点,必备复习资料分享,方便大家备考时翻阅查看,提高复习效率,希望对大家备考有所帮助。
参考王道计算机考研《数据结构》课程,自主进行知识点归纳总结!总结详细,高分必拿!
武忠祥课程学习笔记,参考老师课程讲解的笔记;在期末复习的时候非常好用~适用于考试复习!
社区模板帮助中心,点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
马克思主义原理
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
树的应用
平衡二叉树(AVL树)
概念
平衡因子
最小不平衡子树
从插入点往回找到第一个不平衡结点,调整以该结点为根的子树(最小不平衡树)
实现f向右下旋转(其左孩子右上旋)
实现f向左下旋转(其右孩子左上旋)
定义
树上任一结点的左子树和右子树高度之差(结点的平衡因子)不超过1
注意
平衡二叉树结点的平衡因子值只可能是-1,0,1
只要有任一结点的平衡因子绝对值大于1-->该树不是平衡二叉树
插入操作
同二叉排序树一样,找合适的位置插入
新插入的结点可能导致其祖先们平衡因子改变,导致失衡
调整不平衡PPT5.5_2
找到最小不平衡子树进行调整,即最小不平衡子树的根为A
LL
在A的左孩子的左子树插入导致A不平衡
将A的左孩子右上旋
RR
在A的右孩子的右子树插入导致A不平衡
将A的右孩子左上旋
LR
在A的左孩子的右子树插入导致A不平衡
将A的左孩子的右孩子先左上旋,再右上旋
RL
在A的右孩子的左子树插入导致A不平衡
将A的右孩子的左孩子先右上旋,再左上旋
查找效率分析
深度为h的平衡树中含有的最少结点数nh——递推求解
n0=0;n1=1;n2=2 并且有nh = nh-1 + nh-2 +1(递推公式)
平衡二叉树最大深度为O(log n) 平均查找长度/查找的时间复杂度为O(log n)
哈夫曼树
结点的权
某种特定含义的数值(如表示该结点的重要程度)
带权的结点都是叶子结点
结点的带权路径长度 = 根到结点路径长度*结点的权值
树的带权路径长度(WPL)= 树中所有叶子结点的带权路径之和
哈夫曼树(最优二叉树)
在含有给定的n个带权叶结点的二叉树中,WPL最小的树
哈夫曼树不唯一,值WPL必然都是最小值
构造哈夫曼树
每次选两个根结点权值最小的树合并, 并将二者权值之和作为新的根结点的权值
性质
每个初始结点(新合并结点)最终都成为叶子结点, 且权值越小的结点到根结点的路径长度越大
哈夫曼树的结点总数为2n-1
n个结点每次两两合并,需要合并n-1次,每一次合并产生一个新的根结点————n-1+n
哈夫曼树不存在度为1的结点
哈夫曼树不唯一,但WPL必然相同且为最优
合并均为树的合并(树的根结点合并而不是分支结点OR叶子结点)
两棵树合并,左右顺序任意
 d可以是左孩子也可以是右孩子
哈夫曼编码
将字符频次作为字符结点权值,构造哈夫曼树, 即可得到哈夫曼编码,可用于数据压缩
前缀编码——没有一个编码是另一个编码的前缀
固定长度编码——每个字符用相等长度的二进制表示(如ASCII编码)
可变长度编码——允许对不同字符用不等长的二进制表示
非前缀解码有歧义(路径有重叠)—改进—>每个带权值的结点都为叶子结点(前缀编码无歧义——路径不和其他结点重叠)

二叉排序树(BST,Binary Search Tree)
左子树结点值<根结点值<右子树结点值
默认不允许两个结点的关键字相同
进行中序遍历,可以得到一个递增的有序序列
查找操作
从根结点开始,目标值更小往左找,目标值更大往右找
算法思路
若树非空,目标值与根结点值比较
若相等,则查找成功
若小于根结点,则在左子树上查找,否则在右子树上查找
查找成功,返回结点指针;查找失败,返回NULL
代码实现
递归实现

非递归实现
若原二叉排序树为空,则直接插入结点
循环
若关键字k小于根结点,则插入到左子树
若关键字k大于根结点,则插入到右子树
插入结点
遇到空指针,插入结点(一定是叶子结点的左/右孩子指针)
树中存在相同关键字的结点,插入失败 (BST不允许存在两个相同的结点)
传入指针为引用,需要修改指向插入位置的指针(其父结点指针)
BST的构造
BST的构造<--->BST插入操作
不同的关键字序列可以得到同样BST,也可以得到不同BST
删除操作(最难)
先搜索找到目标结点
目标结点
叶子结点
直接删除
分支结点
只有一棵左子树或右子树,则z的子树成为z父结点的子树
代替z位置
有左子树和右子树
分析思路
则令z的直接后继(或直接前驱)代替z
从BST中删除这个直接后继(或直接前驱)(转为①或②)
z的直接后继
z的右子树中最左下结点(该结点一定没有左子树)
z的直接前驱
z的左子树中最右下结点(该结点一定没有右子树)
删除结点后,仍需保持BST性质 (左子树结点值<根结点值<右子树结点值)
在查找运算中,需要对比关键字的次数称为查找长度
ASL
Average Search Length
查找成功
总的查找长度/结点数
查找失败
总的查找长度/空结点数
查找空结点不需要对比关键字 (查找函数遇到空指针就已经退出循环,返回空指针)
取决于树的高度,最好为O(log n),最坏为O(n)