【数据结构 | 平衡二叉树】失衡时如何调整

平衡二叉树（AVL树）

• 前提：二叉搜索树
• 所有结点的 (左子树高度 - 右子树高度）的绝对值 <= 1
  左子树高度 - 右子树高度 —— 平衡因子
• 插入、查找、构建、删除过程与二叉搜索树一致，但是失衡的时候需要调整。

平衡二叉树的调整？

1. 左旋

• 将失衡结点左旋（逆时针旋转），发生冲突时 —— 冲突的左孩变成右孩
  
  

2. 右旋

• 将失衡结点右旋（顺时针旋转），发生冲突时 ——冲突的右孩变左孩
  
  

四种失衡情况

1. LL型

• 失衡结点平衡因子 = 2，失衡结点的左孩子的平衡因子 = 1
• 失衡结点右旋。
  

2. LR型

• 失衡结点平衡因子 = 2，失衡结点的左孩子的平衡因子 = -1
• 失衡节点左孩子先左旋，然后失衡结点再右旋。
  

3. RR型

• 失衡结点平衡因子= -2，失衡结点的右孩子的平衡因子 = -1
• 失衡节点左旋。
  

4. RL型

• 失衡结点平衡因子= -2，失衡结点的右孩子的平衡因子 = 1
• 失衡结点的右孩子先右旋，失衡结点再左旋。
  

插入节点后，若多个祖先结点失衡？

• 只需要调整距离插入结点最近的失衡结点，其他失衡结点会自然平衡。
  

删除节点后，调整？

• 需要依次对每个祖先进行检查并调整

可以看这个视频来容易理解：平衡二叉树(AVL树)