数据结构与算法通俗易懂讲解AV [复制链接]

AVL树是一种特殊的二叉搜索树，因此如果你对二叉搜索树不熟悉，建议看完下面几篇二叉搜索树的文章再来学习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树，是一种平衡(balanced)的二叉搜索树。由两位科学家在年发表的论文《Analgorithmfortheorganizationofinformation》当中提出，作者是发明者G.M.Adelson-Velsky和E.M.Landis。

相比于"二叉查找树"，AVL树的特点是：AVL树中任何节点的两个子树的高度最大差别为1。关于树的高度等基本概念，请参考前面文章通俗易懂讲解二叉搜索树（请戳我）

上面图中，左边的是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。

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

推荐阅读：

精心整理

历史干货文章目录

自己搜集的网上精品课程视频分享（上）

通俗易懂讲解二叉树遍历

通俗易懂讲解二叉搜索树

专注服务器后台技术栈知识总结分享

欢迎