数据结构与算法分析笔记——AVL树

数据结构与算法分析笔记——AVL树

什么是AVL树？

二叉树这种数据结构，提高了查询的效率，但是，在某些极端情况下，二叉树的这种优势可能会被破坏，于是，我们可能需要在插入或删除时做更多的工作，以使得二叉树能持续保持较高的查询效率。也就是说，我们需要在二叉树原来的结构特征上，再额外增加一些条件，使得它能保持一定的平衡。

AVL树就是带有平衡条件的一种二叉树：每个节点的左子树和右子树的高度最多差1。注意是每个节点，而不单单是根节点。

旋转

AVL树相较于一般二叉树来说，由于携带了额外的平衡条件，所以，当向树中的元素插入或删除时，为了保持平衡，可能需要进行一些额外的操作，比如说旋转。

那么，该如何旋转呢？我们不妨先对可能破坏平衡的情况进行一下整理。

对于节点root来说，由于每个节点最多只能有两个儿子，所以，插入的情况只有四种：

对root的左子的左子树进行一次插入。

对root的左子的右子树进行一次插入。

对root的右子的左子树进行一次插入。

对root的右子的右子树进行一次插入。

又由于1和4，2和3事实上是两对镜像操作，所以，我们只分析两种情况即可，比如1和2。

又因为root本身就是一个AVL树，本身的左右子树高度差为0或1，所以，插入后，如果平衡被破坏，那么高度差只能是2。

先来考虑情形1。如下：

由于在k1的左子k2的左子树中，进行了一次插入，导致了k1的左子树比右子树的高度大了2。

那么，这种情况该如何处理呢？我们可以通过一次右旋来处理，过程如下：

另k2成为新的根节点。

另k1为k2的右子。

另k2的右子树为k1的左子树。

得到如下：

经过旋转之后，树又恢复到了AVL的形态。那么，这种旋转是否合理呢？即是否会破坏二叉树本身的基本特征：每个节点的值都大于其左子树中任意节点的值，都小于其右子树中任意节点的值呢？

我们来作一个简单分析：

k2原为k1的左子，所以k1 > k2，所以，k1作k2的右子，也是合理的。

k2右子树上的任意节点必大于k2，又因为k2原为k1的左子，所以，对于k2右子树上的任意节点n，均有 k2

综上，我们通过一次合理的右旋操作，重新得到了一棵AVL树。

再来考虑情形2。如下：

我们看看右旋能不能解决问题。右旋结果如下：

我们发现，右旋之后，变成了一个右子树比左子树高2的情形。

那么，该如何操作呢？我们多画出一个k3节点帮助操作，如下：

这次，我们先把k3确定为新的根节点，看看其它节点该整理。

k3原为k2的右子，所以 k2

k2原为k1的左子，所以有k2

对于k3的左子树任意节点n，均有 k2

对于k3的右子树任意节点n，均有 n > k3，又因为k3

结果如下：

我们看到，结果达到了平衡。

这种操作，我们称之为左右双旋。

至此，我们得到结论，即对于一棵由于插入而失去平衡的原AVL树，我们总可以通过左旋、右旋、左右双旋或右左双旋来重新得到平衡。

下一篇，我们将具体讨论AVL树相关代码的实现。