江小南
2023/03/25阅读：42主题：萌绿
【数据结构】平衡二叉树
1. 定义
平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树）——树上任一结点的左子树和右子树的高度之差不超过1。
结点的平衡因子=左子树高-右子树高。
// 平衡二叉树结点
typedef struct AVLNode{
int key; // 数据域
int balance; // 平衡因子
struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;
2. 如何调整“不平衡”问题
1. 插入
在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡。
每次调整的都是最小不平衡子树。
调整方法：
LL平衡旋转(右单旋转)。由于在结点A的左孩子(L)的左子树(L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。
RR平衡旋转(左单旋转)。由于在结点A的右孩子(R)的右子树(R)上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。
LR平衡旋转(先左后右双旋转)。由于在A的左孩子(L)的右子树(R)上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置。
RL平衡旋转(先右后左双旋转)。由于在A的右孩子(R)的左子树(L)上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。
示例： 
插入了90。 
插入了57。
说明：对LL或RR的操作，从不平衡子树结点开始，是对儿子结点的旋转。对LR或RL的操作，从不平衡子树结点开始，是对孙子结点的旋转。
2. 删除
平衡二叉树的删除具体操作步骤：
-
删除结点（方法同“二叉排序树”）。
-
若删除的结点是叶子，直接删。 -
若删除的结点只有一个子树，用子树顶替删除位置。 -
若删除的结点有两颗子树，用直接前驱（或直接后继）结点顶替，并转换为对前驱（或后继）结点的删除。
-
一路向北找到最小不平衡子树，找不到就结束算法。 -
找到最小不平衡子树下，“个头” 最高的儿子、孙子。 -
**根据孙子的位置，调整平衡(LU/RR/LR/RL)**。
-
孙子在LL:儿子右单旋 -
孙子在RR:儿子左单旋 -
孙子在LR:孙子先左旋，再右旋 -
孙子在RL:孙子先右旋，再左旋
-
如果不平衡向上传导，继续第2步。
-
对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡(不平衡向上传递)。
示例：
根据最大的孙子的位置判定是RL还是LR。
3. 查找效率分析
若树高为h，则最坏情况下，查找一个关键字最多需要对比h次，即查找操作的时间复杂度不可能超过O(h)。
平衡二叉树——树上任一结点的左子树和右子树的高度之差不超过1。 
作者介绍