概念
AVL(Adelson-Velskii和Landis)树是带有平衡条件的二叉查找树。
平衡条件
一颗AVL树是其每个节点的左子树和右子树的高度最多相差1的二叉查找树。
破坏平衡
当进行插入操作时,那些从插入点到根节点的路径上的节点的平衡可能被改变。当我们沿着这条路径上行到根并平衡信息时,我们找到一个节点,它的新平衡破坏了AVL条件。我们把必须重新平衡的节点叫做α。由于任意节点最多有两个儿子,因此高度不平衡时,α点的两棵子树的高度差2。这种不平衡可能出现在下面四种情况中:
- 对α的左儿子的左子树进行一次插入。
- 对α的左儿子的右子树进行一次插入。
- 对α的右儿子的左子树进行一次插入。
- 对α的右儿子的右子树进行一次插入。
情形1和4是关于α点的镜像对称,而2和3是关于α点的镜像对称。因此,理论上只有两种情况,但从编程的角度来看还是四种情形。
第一种情况是插入发生在“外边”的情况(即左-左的情况或右-右的情况),该情况通过对树的一次单旋转(single rotation)而完成调整。
第二种情况是插入发生在“内部”的情形(即左-右的情况或右-左的情况),该情况通过稍微复杂些的双旋转(double rotation)来处理。