6.15.平衡二叉搜索树

在上一节中，我们考虑构建一个二叉搜索树。正如我们所学到的，二叉搜索树的性能可以降级到 $$O(n)$$ 的操作，如 get 和 put ，如果树变得不平衡。在本节中，我们将讨论一种特殊类型的二叉搜索树，它自动确保树始终保持平衡。这棵树被称为 AVL树，以其发明人命名：G.M. Adelson-Velskii 和E.M.Landis。

AVL树实现 Map 抽象数据类型就像一个常规的二叉搜索树，唯一的区别是树的执行方式。为了实现我们的 AVL树，我们需要跟踪树中每个节点的平衡因子。我们通过查看每个节点的左右子树的高度来做到这一点。更正式地，我们将节点的平衡因子定义为左子树的高度和右子树的高度之间的差。

$$
balanceFactor = height(leftSubTree) - height(rightSubTree)
$$

使用上面给出的平衡因子的定义，我们说如果平衡因子大于零，则子树是左重的。如果平衡因子小于零，则子树是右重的。如果平衡因子是零，那么树是完美的平衡。为了实现AVL树，并且获得具有平衡树的好处，如果平衡因子是 -1,0 或 1，我们将定义树平衡。一旦树中的节点的平衡因子是在这个范围之外，我们将需要一个程序来使树恢复平衡。Figure 1展示了不平衡，右重树和每个节点的平衡因子的示例。

Figure 1