【考研】数据结构之平衡二叉树考点_平衡树叶子结点深度之差不超过1

前言

以下有关平衡二叉树的考点内容，源于对《数据结构（C语言版）第2版》及王道讲解的整理笔记和总结。建议同红黑树的考点结合一起 “食用”。

平衡二叉树重要考点：插入新结点后，如何调整 “不平衡” 问题。

【考研】数据结构：红黑树（2022新增考点）_住在阳光的心里的博客-CSDN博客_考研红黑树

一、平衡二叉树的基本概念

1、定义：平衡二叉树，又称AVL树，是一种特殊类型的二叉排序树。具有以下特征：

（1）左子树和右子树的深度之差的绝对值不超过1。

（2）左子树和右子树也是平衡二叉树。

（二叉排序树的特性：结点值：左子树 < 根 < 右子树）

//平衡二叉树结点
typedef struct AVLNode{
    int key;   // 数据域
    int balance;   // 平衡因子
    struct AVLNode *lchild, *rchild;
}AVLNode, *AVLTree;

2、若将二叉树上结点的平衡因子（BF）定义为该结点左子树和右子树的深度之差，则平衡二叉树上所有结点的 BF 只可能是 -1，0 和 1 。如下图。

因为AVL树上任何结点的左右子树的深度之差都不超过1，则可证其深度和  是同数量级的（其中 n 为结点个数）。由此，其查找的时间复杂度为  。

 （可以看到，叶子结点的平衡因子都为0。）

3、只要二叉树上有一个结点的平衡因子的绝对值大于1，该树就是不平衡的，需要进行调整。

调整方法：找到离插入结点最近且平衡因子绝对值超过1的祖先结点，以该结点为根的子树称为最小不平衡子树，可将重新平衡的范围局限于这棵子树。可归纳成四种情况：LL型、LR型、RL型和RR型。

插入新结点后，调整步骤：

（1）标出所给二叉树的平衡因子，找到最小不平衡子树。

（2）根据最小不平衡子树，判断是四种类型的哪一种。

（3）根据 “ LL右，RR左，LR先左再右，RL先右再左 ”调整二叉树。

（4）检查是否符合 “ 结点值：左子树 < 根 < 右子树 ”

（第三步最好再根据“七、练习”熟悉一下。）

二、LL型（右旋）

三、RR型（左旋）

四、LR型（先左再右）

 

五、RL型（先右再左）

 

六、调整最小不平衡子树的总结

 

 

 七、练习