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种情况对应的旋转方法。