最近学习了二叉搜索树中的AVL树,特在此写一篇博客小结。

1.引言

对于二叉搜索树而言,其插入查找删除等性能直接和树的高度有关,因此我们发明了平衡二叉搜索树。在计算机科学中,AVL树是最先发明的自平衡二叉搜索树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。对于N个节点的AVL树,由于树高被限制为lgN,因此其插入查找删除操作耗时为O(lgN)。

2.旋转

在讲解关键步骤插入与删除以前,首先我们先定义一些辅助用的操作:旋转。旋转分为左旋和右旋,其示意图如下:
 
算法二叉搜索树之AVL树-LMLPHP
相信上图已经表示的非常明确,这里就不再细说,值得注意的是:在旋转操作中只有指针的改变,其他属性都保持不变。对旋转前后的树使用中序遍历将得到相同的结果。
 
 

3.插入

对于AVL树而言一个关键的操作就是插入操作。往AVL树中插入新的节点可能会引起AVL树的性质被破坏,我们分为以下两种情况来讨论(我们只讨论左子树的情况,右子树的情况只需镜像处理即可):

1.左左情况(LL)

这种情况如下:
算法二叉搜索树之AVL树-LMLPHP
A是失去平衡的节点,其失去平衡的原因在于其左节点B中加入了新左节点C,此时我们对A节点进行右旋操作即可恢复AVL树的平衡。
 

2.左右情况(LR)

这种情况需要进行两次旋转,如下图所示:
算法二叉搜索树之AVL树-LMLPHP
A是失去平衡的节点,其失去平衡的原因在于其左节点B中加入了新右节点C,此时我们需要两次旋转来解决问题,我们先对B节点进行左旋,再对A节点进行右旋即可。
 
对于RR(右子节点加入新右节点)和RL(右子节点加入新左节点)的情况,只要针对上面的情况进行镜像处理即可。
 

4.删除

对AVL树的某个节点进行删除后,我们需要判断其父节点是否还符合AVL树的性质,如果否则进行与插入情况类似的旋转处理即可,在此不再赘述。
05-11 09:29