AVL树是最早发明的平衡二叉搜索树之一，名字来源于两位发明者的名字G.M.Adelson-Velsky 和 E.M.Landis(来自苏联的科学家)

AVL树的一些相关知识点

AVL树里面有一个平衡因子的Balance Factor的概念：代表这某节点的左右子树的高度差，而且每个节点的平衡因子只有在1，0，-1（绝对值小于等于1）的情况下，树才不会失衡，否则就会失衡，那这个就意味这每个节点的左右子树的高度差不超过1；下面给出两张图，分别观察一下失衡和平衡的情况:

失衡的二叉树 平衡二叉树

前面已经说到出现平衡二叉树是为了提高算法效率哈，因为前面可以知道节点的插入和高度是有一定关系的，插入节点的时候需要遍历整颗树，高度越小，自然就会越快！下面来说说有可能导致失衡的原因

添加导致的失衡

添加失衡

注意：添加导致的失衡会导致所有祖先节点都失衡，父节点是，非祖先节点都不可能失衡

你说如果我们可以将这个失去平衡的树重新平衡一下，那都好呀，答案是肯定可以的，恢复平衡之后将变成如下图：

恢复平衡图

删除导致的失衡

父节点失衡 祖先节点失衡

注意：删除元素会导致父节点或祖先节点失衡（只有一个节点会失衡）其他节点都不可能失衡

在学习怎么恢复平衡的过程之后，我们需要了解到几个概念，分别是LL(右旋转)，RR(左旋转)，LR(RR左旋转，LL右旋转),RL(LL右旋转，RR左旋转)

添加元素的旋转-恢复平衡

LL - 右旋转（单旋）

g.left = p.right;

p.right = g;

让p成为这颗子树的跟节点

仍然是一颗二叉搜索树：T0 < n < T1<p<T2<g<T3

更改T2,p,g的parent属性，并先后更新根g,p高度

LL

之所以成为LL，是因为是在p的left（n）的left添加的元素，经过右旋转之后发现树恢复了平衡；

代码图如下：

方法中涉及到的高度方法图会在后面给出来

RR - 左旋转（单旋）

g.right  = p.left;

p.left = g;

让p成为这颗子树的跟节点

仍然是一棵二叉搜索树：T0<g<T1<p<T2<n<T3

T1,p,g的parent属性重新设置，还有g,p的高度设置

RR

代码图如下：

左旋转代码图

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

LR

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

RL

双旋要不就是先左后右，要不然就是先右后左，所以代码实现就是将上面两个方法合起来用就可以啦，下面我们再看看一个恢复平衡的方法

恢复平衡代码

rebalance2

添加之后的修复

afterAdd

删除元素的旋转-恢复平衡

LL-右旋转（单旋）

LL

RR-左旋转（单旋）

RL

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

LR

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

RL

旋转的处理方式和添加元素的步骤相差不多，不同的就是失衡的情况，删除节点的一次恢复平衡操作有可能会导致祖先节点失衡，需要再次恢复平衡，然后又可能导致更高层的祖先节点失衡，也是因为这个原因，所以在处理AVL删除元素的代码方法里面，调用了恢复平衡之后不能马上调用break，这个和AVL添加元素方法稍微有点不一样（图中的绿色代表就是如果绿色节点不存在的情况下，会导致很多祖先节点有可能失衡，极端情况下，所有祖先节点都需要进行恢复平衡的操作，共O(logn)次调整）

下面展现元素移除之后的的平衡修复代码：

rebalance2 afterRemove

可以看到无论是添加恢复还是删除恢复里面都有一个更新高度的方法，实现大概如下：

updateHeight

下面再新增加一个方法，就是旋转操作的统一方法：先上图再上代码图

LL RR LR RL

有没有发现，因为是AVL是基于二叉搜索树的情况下，所以可以发现最后恢复平衡的结果都是一样的，所以我们可以采取用下面的代码进行统一旋转

rotate balance

总结

添加

可能会导致所有祖先节点都失衡，只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡仅需O(1)次调整

删除

可能会导致父节点或祖先节点失衡（只有1个节点会失衡）恢复平衡后，可能会导致更高层的祖先节点失衡（最多需要O(logn)次调整）

平均时间复杂度

搜索：O(logn)

添加：O(logn),仅需O(1)次的旋转操作

删除：O(logn),最多需要O(logn)次旋转操作