AVL树

AVL树是一种平衡搜索二叉树，二叉搜索树的平均时间复杂度为Olog(n)，也就是树的高度，最差的时间复杂度为O(n)，n为节点的个数，当二叉搜索树为最差时间复杂度时，二叉搜索树退化为链表。

最差时间复杂度

添加和删除二叉搜索树节点时都有可能会导致二叉搜索树退化为链表

平衡搜索二叉树

当节点数量固定是，左右子树的高度越接近，这颗二叉树就越平衡，如何改进二叉搜索树
节点的添加、删除顺序是随机的无法限制的，所以，改进方案是在节点添加、删除之后，想办法让二叉搜索树恢复平衡（减小树的高度）。

AVL树

AVL树是最早的自平衡二叉搜索树之一，AVL取自两位发明者的名字。

• 平衡因子
  某节点的左右子树的高度差。
• AVL树的特点
  AVL树每个节点的平衡因子只可能是1、0、-1，绝对值小于等于1，如果超过1，称之为失衡。
  每个节点的左右子树高度差不超过1
  搜索、添加、删除的时间复杂度时O(logn)。

平衡调整

LL-右旋转（单旋）

g失去平衡

调整过程

g.left = p.right;
p.right = g;

RR-左旋转（单旋）

g失去平衡

调整过程

g.right = p.left;
p.left = g;

LR-RR左旋转，LL右旋转（双旋）

g失去平衡

调整过程

p.right = n.left;
n.left = p;
g.left = n.right;
n.right = g;

RL-LL右旋转，RR左旋转（双旋）

g失去平衡

调整过程

p.left = n.right;
n.right = p;
g.right = n.left;
n.left = g;