平衡二叉查找树-数据结构(c语言)

平衡二叉查找树

如果元素从小到大顺次插入到二叉查找树中，最终的形态会变成这样：

此时这棵二叉查找树的高度为5。如果每次要在二叉查找树中查找元素 5，则需要每次将整棵树遍历。也就是说，二叉查找树退化成了一个有序链表，效率大大降低。
为了避免退化成一条链的情况，就有了一类改进的“更平衡”的二叉查找树，这种二叉查找树被称为自平衡二叉查找树（balanced binary search tree，简称平衡二叉查找树） 。通过各种对树的形态的限制，和对应的调整方法，使得树的深度不会过大，查询的时间复杂度不至于退化到

(

)

\mathcal{O}(n)

$O (n)$ 。
比如刚才的二叉查找树，如果将这棵树“调整”一下，可以得到下面这棵树：

此时二叉查找树的高度减少为 3 了。在查询元素时，效率比之前要高不少。
计算机科学发展至今，已经出现了若干种平衡二叉查找树，其中最先发明的是 AVL 树，这种“元老级”的平衡二叉查找树会在后面的课程里介绍给你。

所有平衡二叉查找树基本由以下三个特征组成：

自平衡条件
旋转操作
旋转的触发

平衡二叉查找树通过设置合理的自平衡条件，使得二叉查找树的查找、插入等操作的性能不至于退化到 O(n)，并且在进行二叉查找树的查找、插入等操作时进行判断，如果满足其中某个旋转的触发条件，则进行对应的旋转操作。

在本章里，会为你介绍 AVL 树和 SBTree 这两种平衡二叉查找树，并带你实现 SBTree 的旋转和调整操作，以及用 SBTree 求解二叉查找树中第 k 大元素。最后需要你用平衡二叉查找树解决一道难题。

AVL 树

AVL 树提出了一个概念： 平衡因子（balance factor） 。每个结点的平衡因子是指它左子树最大高度和右子树最大高度的差。在 AVL 树中，平衡因子为 −1、 0、 1 的结点都被认为是平衡的，而平衡因子为 −2、 2 等其他值的结点被认为是不平衡的，需要对这个结点所在子树进行调整。
比如下面这棵树

对结点 4 来说，平衡因子为

∣

−

∣

|height_{left} – height_{right}|

$∣ h e i g h t_{l e f t} - h e i g h t_{r i g h t} ∣$ =|3-1|=2>1，所以不平衡。
而下面这棵树：

树上的所有结点都满足 AVL 的平衡条件，你如果有兴趣可以自己算一下。

旋转操作

单旋

在 AVL 树中，一共有两种单旋操作：左旋和右旋。AVL 树通过一系列左旋和右旋操作，将不平衡的树调整为平衡二叉查找树。
左旋操作的演示如下：

通过进行左旋操作，使得原先的根 2 变成了其右孩子 4 的左孩子，而 4 原先的左孩子 3 变成了 2 的右孩子。“左旋”这个名字是不是很形象呀。
对应的，右旋操作的演示如下：

通过右旋操作，使得原先的根 5 变成了其左孩子 3 的右孩子，而 3 原先的右孩子变成了 5 的左孩子。

多旋

AVL 树中还有两种复合旋转操作（即“多旋”），由两次单旋操作组合而成。
第一种是左旋加右旋：

第二种是右旋加左旋：

旋转的触发

插入操作
在插入一个元素后不断回溯的过程中，如果因此导致结点不平衡，则根据不平衡情况（一定是一边子树比另一边子树的高度大 \ 2 2）进行对应的旋转：

左子树比右子树的高度大 2：

如果新增元素插入到左儿子的左子树中，则进行右旋操作。( LL 型调整 )
如果新增元素插入到左儿子的右子树中，则进行左旋加右旋操作。（ LR 型调整）

右子树比左子树的高度大 2：

如果新增元素插入到右儿子的右子树中，则进行左旋操作。（ RR 型调整）
如果新增元素插入到右儿子的左子树中，则进行右旋加左旋操作。（ RL 型调整）

删除操作

类似的，在删除一个元素后不断回溯的过程中，如果因此导致结点不平衡，则和插入操作采用相同的调整操作，确保在删除以后整棵树依然是平衡的。
你可以思考下，AVL 在删除过程中如果不进行调整操作，是否能接受呢？
好了，现在我们已经了解 AVL 树的平衡策略及一系列维护平衡的操作。在后面的课程中，我们会继续巩固 AVL 树的相关内容，之后会为你介绍另外一种平衡二叉查找树——SBTree。

AVL 性质

高度为n的AVL树，若每个结点的平衡因子都为0，则树中结点总数为2^n-1.
如果一棵二叉查找树同时是一棵完全二叉树，则该树符合AVL 树的平衡条件。

Size Balanced Tree

自平衡条件

还记得 AVL 树的自平衡条件么？在 AVL 树中，任何结点的两个子树的高度最大差别为1。而对于 SBT，它的自平衡条件会显得稍微复杂一些：对于每个结点 t，同时满足

[

]

≥

(

[

]

[

]

)

\displaystyle size[right[t]] \geq max(size[left[left[t]]],size[right[left[t]]])

$s i z e [r i g h t [t]] \geq m a x (s i z e [l e f t [l e f t [t]]], s i z e [r i g h t [l e f t [t]]])$

[

]

≥

(

[

]

[

]

)

\displaystyle size[left[t]] \geq max(size[left[right[t]]],size[right[right[t]]])

$s i z e [l e f t [t]] \geq m a x (s i z e [l e f t [r i g h t [t]]], s i z e [r i g h t [r i g h t [t]]])$

其中

[

]

size[t]

$s i z e [t]$ 表示 t 结点所在子树的结点个数。
公式看起来很复杂，形象一点来说，就是每个结点所在子树的结点个数不小于其兄弟的两个孩子所在子树的结点个数。
比如对于这棵二叉查找树

对于结点 39 来说，就不满足 SBTree 的自平衡条件。

旋转操作

旋转操作和 AVL 树的左旋右旋是完全一样的。我们再来复习一遍这两种非常通用的旋转操作。
对于下面这棵树：

我们对 10 进行右旋操作后的结果为：

那么左旋呢？我们换一棵树：

我们对39 进行左旋操作后的结果为：

旋转的触发

在调整过程中，一共有 4 种会触发旋转的情况：

LL 型（

[

]

[

]

size[left[left[t]]] > size[right[t]]

$s i z e [l e f t [l e f t [t]]] > s i z e [r i g h t [t]]$ ) ：首先对子树 t 执行右旋操作，旋转以后对 t 的右子树进行调整，之后再对子树 t 进行调整。
LR 型（

[

]

[

]

size[right[left[t]]] > size[right[t]]

$s i z e [r i g h t [l e f t [t]]] > s i z e [r i g h t [t]]$ ）：首先对 t 的左子树执行左旋操作，再对 t 进行右旋操作。之后分别调整结点 t 的左右子树，最终对结点 t进行调整。
RR 型（

[

]

[

]

size[right[right[t]]] > size[left[t]]

$s i z e [r i g h t [r i g h t [t]]] > s i z e [l e f t [t]]$ ）：首先对 t 执行左旋操作，旋转以后对 t 的左子树进行调整，之后再对 t 进行调整。
RL 型（

[

]

[

]

size[left[right[t]]] > size[left[t]]

$s i z e [l e f t [r i g h t [t]]] > s i z e [l e f t [t]]$ ）：首先对结点 t 的右子树执行右旋操作，再对 t 进行左旋操作。之后分别调整 t 的左右子树，最终对 t 进行调整。
通过递归的进行调整，我们可以最终让不平衡的 SBTree 恢复平衡状态。可以证明，调整操作的均摊时间复杂度为

(

)

\mathcal{O}(1)

$O (1)$ 。
和 AVL 不太一样的是，SBTree 只有在插入时才可能触发调整，而不需要在删除结点以后进行调整。

从理论上说，SBTree 和 AVL 树相比在均摊时间复杂度上没有区别，每次查询、插入和删除的时间复杂度都为

(

log

⁡

)

\mathcal{O}(\log n)

$O (lo g n)$ 。在实际运用中，SBTree 在查询操作较多的情况下会有效率上的优势。加之为了维护平衡性记录了每个结点所在子树大小（即子树内结点个数），相比其他平衡二叉查找树而言，更便于求解第 k 大元素、或求解元素的秩（rank）等类似问题。
后面的课程中，我们会实现 SBTree 的左旋、右旋、调整操作，并使用 SBTree 求解第 k 大元素。在最后使用平衡二叉查找树解决一道难题。