平衡二叉搜索树的实现原理

ゝ一世哀愁。 2022-06-02 02:49 160阅读 0赞

### 二叉搜索树的树高与性能 ###

前面笔者介绍了[二叉搜索树的实现和性能分析][Link 1],查询，插入和删除等操作均线性正比于二叉树的高度。在最坏的情况下,线性表退化为列表，二叉搜索树的性能会降低至O(n)。因此，如果能控制树高，则二叉搜索树的性能会明显提升

### 理想平衡与适度平衡 ###

#### 理想平衡 ####

既然二叉搜索树的性能主要影响与树高，则应该在节点数目固定的前提下，尽可能降低树高。也意味着，应尽可能地使兄弟子树的高度彼此接近，即全树尽可能的平衡。当然根据二叉树的特性，规模为n的二叉树，高度不可能小于log以2为底n的对数。如果高度为log以2为底n的对数的平衡二叉树，则称为理想平衡树。完全二叉树，满二叉树均属于理想平衡树。

#### 适度平衡 ####

理想平衡的条件过于严格，在实际中意义不大，因为出现的概率实现太小了。因此有必要定制一种规则，限制两个兄弟子树的高度差在一定的范围内。满足这个限制条件则为平衡二叉树。例如：AVL树，伸展树，红黑树，kd-树都属于适度平衡树。因此均属于平衡二叉搜索树

### 二叉搜索树到平衡二叉搜索树的等价变化 ###

如果两个二叉搜索树的中序遍历是一致的，则他们彼此等价。如下图所示：  
![这里写图片描述][SouthEast]

可以看出，虽然二叉搜索树中各节点的垂直高度有所不同，但水平次序完全一致。这一特点可概括为“上下可变，左右不乱“。

**平衡二叉搜索树的规则：**

平衡二叉搜索树的适度平衡如前文所述，都是通过对树添加了某一限制来保证的。比如，在红黑树，从树根到叶子节点的通路中，总是包含一样多的黑节点。而在AVL树中，兄弟节点的高度差不能超过1。这些限制条件除了保证了适度平衡外，还有如下局限性：

>  *  经过单次动态修改之后，最多只有O(logn)处局部不再满足限制条件
>  *  可在O(logn)时间内，O(logn)处局部重新满足平衡二叉搜索树的条件  
>     这意味这，因为添加节点或者删除节点而失衡的节点，可经过等价交换重新恢复平衡。

这里的树的局部非常重要。比如：任何二叉搜索树，都可以转换为指定规则的二叉搜索树，但是你不得不花费O(n)的时间。而对于上图的二叉搜索树，仅仅需要转换阴影部分即可。

### 旋转调整 ###

最基本的修复手段，就是通过围绕特定节点的旋转，实现等价前提下的局部拓扑调整。

#### zig ####

![这里写图片描述][SouthEast 1]

如图所示，如果X，Y是C的孩子，C和Z是V的孩子，则经过以V为轴进行顺时针zig的一次旋转。结果会使节点C和C的左子树升一级，V和V的右子树降一级。并且V的左子树为原C的右子树

#### zag ####

![这里写图片描述][SouthEast 2]

如图所示，如果X，Y是C的孩子，C和Z是V的孩子，则经过以V为轴进行逆时针zag的一次旋转。结果会使节点C和C的右子树升一级，V和V的左子树降一级。并且V的右子树为原C的左子树

#### 效率与效果 ####

zig和zag旋转均属局部操作，仅涉及常数个节点及其之间的联接关系，故均可在常数时间内完成。正因如此，在后面实现各种二叉搜索树平衡化算法时，它们都是支撑性的基本操作。

就与树相关的指标而言，经一次zig或zag旋转之后，节点v的深度加一，节点c的深度减一; 这一局部子树(乃至全树)的高度可能发生变化，但上、下幅度均不超过一层。

[Link 1]: http://blog.csdn.net/canot/article/details/78942809
[SouthEast]: /images/20220602/18bf4dba41694e32aa7bc7681862a144.png
[SouthEast 1]: /images/20220602/9169c741a3a2484ab7d26f7950b64db2.png
[SouthEast 2]: /images/20220602/b016f4c73f714089ab37162ccc7e23d6.png