数据结构_5_2树的应用

参考王道计算机考研《数据结构》，自主归纳总结知识点，必备复习资料分享，方便大家备考时翻阅查看，提高复习效率，希望对大家备考有所帮助。

树的应用

• 平衡二叉树（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)