前置知识：

[1] 二叉搜索树

什么是平衡二叉搜索树？

当结点数量固定的时候，左右子树的高度越接近就越平衡。完全二叉树和满二叉树，就是理想的平衡。下面的4棵树，从左到右，是越来越平衡的。
image.png

在二叉树的基础上，在结点添加删除操作后，想办法让二叉树恢复平衡(减小树的高度)。但是每次都将二叉树调整到理想二叉树的话，就会增加很多调节的步骤，所以平衡二叉树是用尽量少的调整次数达到适度的平衡。

AVL树，红黑树都是平衡二叉树的经典代表。

平衡因子

某结点的左子树的高度减去右子树的高度的差，称为平衡因子。
image.png

叶子结点 5 、10、14 , 没有左右子树，所以平衡因子为0。 结点4的左子树高度为0，右子树高度为1，所以平衡因子=0-1=-1； 结点13的左子树高度=2，右子树的高度=1，平衡因子=2-1=1 ； 结点9的左子树高度=0，右子树的高度=3 ，平衡因子=0-3=-3。

AVL树特性

  • 每个结点的平衡因子只可能是1、0、-1(绝对值<=1 ,如果超过1，则称为失衡)。
  • 每个结点的左右子树高度差不超过1。
  • 搜索、添加、删除的时间复杂度是O(logn)

添加结点导致的失衡

LL 添加结点导致失衡

例如下图的情况，g 结点的左子节点的左子节点n下的T0或者T1添加一个新的结点，导致g的平衡因子变成了2，失衡。这种情况成为 LL (left-left)。

image.png image.png

对于这种情况，采用右旋转1次来调整平衡。将g结点进行旋转来调整。image.png image.png
整个旋转的过程是，将 g.left = p.right , p.right = g。 只需要这样交换，就可以让二叉树恢复平衡。进行旋转的同时还要注意维护 p , T2 , g 的 parent 属性； 还要先后更新 g 和 p 的高度，先更新高度较小的 g 的高度，然后 p 的高度 = g 的高度 + 1。

RR 添加结点导致失衡

image.png image.png
相对应的，对 g 采取左旋的操作即可恢复平衡。
image.png image.png
左旋的过程和右旋的过程类似。

LR 添加结点导致失衡

例如下图的情况，g 结点的左子节点的右子节点n下的T0或者T1添加一个新的结点，导致g的平衡因子变成了2，失衡。这种情况成为 LR (left-right)。
image.png image.png
对于这种情况，需要旋转2次来调整。先对p结点左旋，然后对g结点进行右旋。
image.png image.png
然后对g进行右旋来恢复平衡。
image.png image.png

RL 添加结点导致失衡

RL的情况和LR情况类似，所以处理，也是采取双旋转 ，先右旋再左旋。
image.pngimage.png
image.png image.png image.png