如何实现基于 AVL 算法的平衡二叉树？

本文共计3177个文字，预计阅读时间需要13分钟。

“上一篇[因为一句话，秒懂二叉树旋转]把树旋转了解清楚，是为了这一篇平衡二叉树准备的。平衡二叉树，就是在二叉树的基础上加一个条件：对于任意节点，其左右子树的树高‘“

上一篇把树旋转了解清楚，是为这一篇平衡二叉树准备的。

平衡二叉树，就是在二叉树的基础上加上一个条件：对于任意节点，左子树和右子树的树高之差不超过 1。

从实现的角度看，就是在已具备旋转功能的 Node 上增加一个 height 字段，并且在原先的代码上增加对 height 的操作。关键操作是判断左右子树的树高之差，根据树高之差选择需要执行的旋转。

示例

如图所示，这是一颗高为 3 的树。根节点左右两边的高度差为 1，满足平衡条件。

此时插入一个值为 1 的节点来破坏这个平衡。当节点 1 插入后，需要逐级往上更新节点的高度。

在高度更新后，发现根节点左右两边的高度差为 2，因此需要通过右旋调整平衡。节点 3 是转轴，按照旋转的规则执行。得到以下结果：

基本思路很简单。剩下的问题放到后面的内容处理。

以下内容会以可旋转的二叉排序树的代码（前篇文章的内容）为基础，添加 Height 这一属性。并根据树高的要求调整代码。

可旋转的二叉排序树

以下是原始代码，不难。与上一篇文章不同的是把 PutChild 改为 Insert，还有简化了旋转的代码。