AVL树是一种特殊的二叉搜索树

二叉搜索树的局限

我们已经知道，一般情况二叉搜索树的查找效率为log(n)，已经足够好了。但是这里为什么强调是一般情况呢？是因为，对于同样的节点，插入的顺序不同，最后得到的二叉搜索树的结构也不一样，对于（2，3，4，5，6，7，8）序列，可以构成下面这样的一颗二叉搜索树：

还是（2，3，4，5，6，7，8）序列，它也能构成下面这样的二叉搜索树，准确的说它应该是一个单链表了，对于单链表，我们很清楚，它的查找操作时间复杂度为n。

n和log(n)的时间复杂度意味什么？从下面的图可以看到，随着元素的增加，log(n)的时间复杂度的增长要远小于n。因此我们自然希望二叉搜索树能尽可能保持log(n)的深度。因此，本文的主人公AVL树横空出世了。

什么是AVL树

AVL树，是一种平衡(balanced)的二叉搜索树。由两位科学家在1962年发表的论文《An algorithm for the organization of information》当中提出，作者是发明者G.M. Adelson-Velsky和E.M. Landis。

相比于"二叉查找树"，AVL树的特点是：AVL树中任何节点的两个子树的高度最大差别为1。https://mp.weixin.qq.com/s?__biz=MzIwNTc4NTEwOQ==&mid=2247483869&idx=1&sn=7d4f2bb00731ac65612e1a237530ea11&chksm=972ad0a7a05d59b1e8a8123ceefa6b7cf7b53b921388aa5a89dfead7b60b1605d5530b74251c&mpshare=1&scene=21&srcid=1007EoZcZKBcJTH8kTwGXv2j#wechat_redirect)

上面图中，左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3，而以8为根节点的树的高度是1)。

关于AVL树的操作，大部分都能复用平衡二叉树树的操作，但是对于插入和删除操作来说，很可能由于节点的插入和删除导致AVL树的平衡状态就被破坏，所以我们需要一种机制来检测这棵树是否平衡，以及当它不平衡的时候，我们应该通过某些操作使它重新平衡(rebalanced)。

旋转

前面讲到如果在AVL树中进行插入一个新的节点或删除某个节点后，可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态：LL(左左)，LR(左右)，RR(右右)和RL(右左)。下面给出它们的示意图：

上图中的4棵树都是"失去平衡的AVL树"，从左往右的情况依次是：LL、LR、RL、RR。除了上面的情况之外，还有其它的失去平衡的AVL树，如下图：

上面的两张图都是为了便于理解，而列举的关于"失去平衡的AVL树"的例子。总的来说，AVL树失去平衡时的情况一定是LL、LR、RL、RR这4种之一，它们都由各自的定义：

LL：称为"左左"。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。

示例：上面LL情况中，由于"根节点(8)的左子树(4)的左子树(2)还有非空子节点"，而"根节点(8)的右子树(12)没有子节点"；导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

LR：称为"左右"。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。

示例：上面LR情况中，由于"根节点(8)的左子树(4)的左子树(6)还有非空子节点"，而"根节点(8)的右子树(12)没有子节点"；导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

RL：称为"右左"。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。

示例：上面RL情况中，由于"根节点(8)的右子树(12)的左子树(10)还有非空子节点"，而"根节点(8)的左子树(4)没有子节点"；导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

RR：称为"右右"。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。

示例：上面RR情况中，由于"根节点(8)的右子树(12)的右子树(14)还有非空子节点"，而"根节点(8)的左子树(4)没有子节点"；导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

14)还有非空子节点"，而"根节点(8)的左子树(4)没有子节点"；导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

前面讲过在AVL树不平衡的时候，我们应该通过某些操作使它重新平衡，后面将会单独用一篇文章总结"LL(左左)，LR(左右)，RR(右右)和RL(右左)"这4种情况对应的旋转方法。