STL关联式容器之平衡二叉搜索树

平衡二叉搜索树

在STL关联式容器介绍-CSDN博客中对二叉搜索树做了简要的描述；但是因为没有对二叉搜索树对数的深度及插入后树的结构进行调整，二叉搜索树可能失去平衡，造成搜寻效率低落的情况。如下所示：

所谓树形平衡与否，并没有一个绝对的测量标准。“平衡”的大致意义是：没有任何一个节点过深（深度过大）。不同的平衡条件，造就不同的效率表现，以及不同的实现复杂度。有数种特殊结构如AVL-tree、RB-tree、AA-tree，均可实现出平衡二叉搜索树，它们都比一般的（无法绝对维持平衡的）二叉搜索树复杂，因此，插入节点和删除节点的平均时间也比较长，但是它们可以避免极难应付的最坏（高度不平衡）的情况，而且由于它们总是保持某种程度的平衡，所以元素的访问(搜寻)时间平均而言也就比较少。

AVL tree(Adelson-Velskii-Landis tree)

Adelson-Velskii-Landis树（AVL树）是由苏联数学家乔治·阿德尔森-维尔斯基（Georgy Adelson-Velskii）和叶夫根尼·兰迪斯（Evgenii Landis）于1962年提出的。它们首次在一篇论文《An algorithm for the organization of information》中介绍了这一数据结构，目的是为了提高二叉搜索树的效率。

AVL tree是一个"加上了额外平衡条件"的二叉搜索树。其平衡条件的建立是为了确保整棵树的深度为O(logN)。直观上的最佳平衡条件是每个节点的左右子树有着相同的高度，但未免太过严苛，我们很难插入新元素而又保持这样的平衡条件。AVL tree于是退而求其次，要求任何节点的左右子树高度相差最多为1.这是一个较弱的条件，但仍能够保证“对数深度”平衡状态。

下面来看一个满足AVL条件的二叉搜索树；

该树的任意节点的左右子树的高度差都没超过1。

不过此时如果插入节点11，如下图所示

插入节点11后，22节点对应左右子树的高度分别为4和2,18节点左右子树高度分别为2和1，所以该树已经不再满足AVL的特性；需要对其进行调整以满足AVL特性；

前面说过，只要调整“插入节点到根节点”路径上，平衡状态被破坏之各节点中最深的那一个，便可使整棵树重新获得平衡。假设该最深节点为X；

现在根据插入节点与不满足条件的X节点的位置关系不同分成四种情况，而后根据这四种情况采用不同的调整方法：

1.插入点位于X的左子节点的左子树--左左

2.插入点位于X的左子节点的右子树--左右

3.插入点位于X的右子节点的左子树--右左

4.插入点为于X的右子节点的右子树--右右

情况1,4彼此对称，称为外侧插入，可以采用单旋转操作调整解决。情况2,3彼此对称，可以采用双旋转操作调整解决。

下图为外侧示例：

下图为内侧示例：

单旋转

在外侧状态下，如下图所示：

在外侧插入情况下，k2“插入前平衡，插入后不平衡”的唯一情况如上图所示。A子树成长了一层，致使它比C子树深度多2.B子树不可能和A子树位于同一层，否则k2在插入前就处于不平衡状态了。B子树也不可能和C子树位于同一层，否则第一个违反平衡条件的将是k1而不是k2.

为了调整平衡状态，我们希望将A子树提高一层，并将C子树下降一层，调整后如下图所示：

这么做是因为，二叉所搜树的规则使我们知道，k2>k1,所以k2必须成为新树形k1的右子节点。二叉树的规则也告诉我们B子树的所有节点的键值是在k1和k2之间，所以新树形中的B子树必须落在k2的左侧。

以上所有调整都只需要将指针稍作搬移，即可高效完成。完成后的新树形符合AVL的平衡条件，不需要再调整。

对于右右的外侧插入，可以采用类似的方法完成。

双旋转

上图所示，左侧为内侧插入所造成的不平衡状态。单旋转无法解决这种情况。第一，我们不能再以k3为根节点，其次，我们不能将k3和k1做一次单旋转，因为旋转之后，还是不平衡。（以此方式旋转，k1，成为父节点，其左节点高度为1，右节点高度将是3）。唯一的可能是以k2为新的根节点。这使得k1，必须成为k2的左子节点，k3必须成为k2的右子节点。这么一来也就决定了四个子树的位置。新的树形满足AVL-tree的平衡条件，并且像单旋转的情况一样，恢复了节点插入之前的高度，因此保证不需要再做调整。

其旋转过程经历了两次单旋转；如下所示；首先对k1,k2做一次单旋转得到如下所示树形：