AVL（Adelson-Velskii和Landis）树是带有平衡条件的二叉查找树。
一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。（空子树的高度定义为-1）
AVL树的每一个节点（在其节点结构中）保留高度信息。
在高度为h的AVL树中，最少节点数S（h）由S（h）=S（h-1）+S（h-2）+1给出。对于h=0，S（h）=1；h=1，S（h）=2。可以看出函数S（h）与斐波那契数密切相关。
向一个AVL树种插入一个节点可能破坏AVL树的特性，如果发生这种情况，那么就要把性质恢复以后才认为这一步插入完成。事实上，这总可以通过对树进行简单的修正来做到，我们称其为旋转（rotation）。
在插入以后，只有那些从插入点到根节点的路径上的节点的平衡可能被改变，因为只有这些节点的子树可能发生变化。当我们沿着这条路径上行到根并更新平衡信息时，我们可以找到一个节点，它的新平衡破坏了AVL条件（沿着此路径上行遇到的第一个不平衡的节点，也就是距离插入节点最近的那个不平衡节点，或者说是最深的那个不平衡节点）。
我们把必须重新平衡的节点叫做A。高度不平衡时，A节点的两棵子树的高度必定差2。容易看出，这种不平衡可能出现在下面四种情况中：
1. 对A的左儿子的左子树进行一次插入。（左-左）——外部
2. 对A的左儿子的右子树进行一次插入。（左-右）——内部
3. 对A的右儿子的左子树进行一次插入。（右-左）——内部
4. 对A的右儿子的右子树进行一次插入。（右-右）——外部
情形1和4是关于A节点的镜像对称，而2和3也是关于A节点的镜像对称。因此，理论上只有两种情况，当然从编程的角度来看还是四种情形。
第一种情况是插入发生在“外部”的情况（左-左或右-右），该情况通过对树的一次单旋转（single rotation）而完成调整。
第二种情况是插入发生在“内部”的情况（左-右或右-左），该情况通过稍微复杂的双旋转（double rotation）来处理。
针对“左-左”、“右-右”式插入新节点而导致的不平衡使用单旋转即可恢复平衡，具体操作如下（我们依然假设插入后必须重新平衡的节点为A，并假设树的所有节点处都是灵活可动的）：
如果是“左-左”式插入导致不平衡（如图1所示），（我们假设节点A的左儿子节点是B）我们只需用两个手指捏住节点B，就这么往上一提（提到原来A的高度就可以了），想象一下这时是不是已经平衡了不过可能出现这样的问题：如果旋转之前节点B有右儿子，那么旋转后节点B岂不是会有两个右儿子了，因为旋转后节点A也会成为B的右儿子，这时只需将B原来的右儿子送给节点A就行了，并且让它做节点A的左儿子（如图2所示）。
图 1
图 2
如果理解了“左-左”式插入不平衡的单旋转调整，那么“右-右”式自然也就掌握了：不同之处只是现在我们需要两个手指捏住A的右儿子往上一提就可以了，并且如果旋转前A的右儿子有左儿子，只需在旋转后将此左儿子送给A做A的右儿子即可。
针对“左-右”、“右-左”式插入新节点而导致的不平衡需要使用双旋转才可恢复平衡。
如果是“左-右”式插入导致的不平衡（如图3所示），能看懂“左-右”，那么“右-左”也自然明白了，不再赘述。理论上讲，双旋转相当于做了两次单旋转；实际上就记做直接将孙子替换到我的位置上，然后妥善安排父亲和我，这样更简单些。
同单旋转中一样，也有可能孙子本身还有它自己的儿子，只需按照二叉查找树的特性将孙子的儿子安排给父亲和爷爷照料（做它们的儿子）就行了。
最后强调一点：我、儿子、孙子都是在从插入点上行到根节点这条路径上。
转载于:https://www.cnblogs.com/nufangrensheng/p/3627485.html
相关资源：各显卡算力对照表！