二叉平衡树之 AVL 树

最近折腾了一下 AVL 树，留点笔记给未来的自己看看 :)

二叉树是基本的树结构，有左右两个孩子。一般情况下，查找可以做到 O(log n) 的时间复杂度。但是对于极端情况，可能恶化成 O(n)，这相当不妙。当输入的数据是线性的，新增的子节点就会都在左子树（递减情况）或者右子树（递增情况）。如下图：


为了让查找继续维持在 O(logn) 的复杂度，我们需要让树长得更平平衡一点。我们先来看看，为了达到不平衡，最少需要几个节点。如果只有两个节点，那无论怎么折腾都一样，谁做根节点都没有区别。所以至少得有 3 个节点，才会出现不平衡的情况。如下图：


z 的左子树和右子树最大高度差大于 1，视为不平衡。这三个节点里，x 和 y 各有左右两种情况，所以一共是 4 种情况。下面分情况讨论一下。

情况 1：


这种情况相当简单，只要向右顺时针方向旋转一下 y 节点，就能达到一个平衡状态：


注意，旋转完以后，w2 节点还是在 y 节点的右子树，z 节点的左子树，没有破坏二叉搜索树的结构。上述的顺时针操作记为 right rotation

情况 2：


这种情况稍微复杂一点，需要经过两次转换才能变成平衡状态。我们先对 x 做一个 left rotation:


现在看起来跟情况 1 就非常像了，只要再来一次 right rotation 就行了：


情况 3：


是不是和上一种有点镜像的感觉呢？所以也是需要两次旋转操作的，这次反过来，先对 x 做 right rotation:


然后再对 x 做一次 left rotate 就完事了：


情况 4：


最后一种情况其实是情况 1 的镜像，所以只需要一次旋转操作就行了 :


要定位到 z 节点，可以比较插入新节点后，左右子树的高度差，当高度差大于1的时候，说明当前节点就是z。然后根据左右子树的高度，就可以分出来是上述4种情况的哪一种了。还需要注意的，是做旋转操作后，需要更新原来父节点的高度，否则后续的操作会出错