自平衡二叉搜索树

数据结构是计算机中用于组织和存储数据的一种指定方式，以便我们能够更有效、更高效地对存储的数据执行操作。二叉搜索树 (BST) 在可用的不同数据结构中执行高效操作至关重要。

在接下来的教程中，我们将学习自平衡二叉搜索树，这是一种通过限制其高度来规避标准二叉搜索树一些缺点的数据结构。

那么，让我们开始吧。

理解二叉搜索树

二叉搜索树 (缩写为 BST) 是一种特殊的二叉树，其中每个节点的数值数据元素都大于或等于其左子树中的所有节点值，并小于或等于其右子树中的所有节点值。

图 1. 二叉搜索树基本术语可视化

现在让我们来看看与二叉搜索树相关的一些关键术语

1. 叶节点是没有子节点的节点。
2. 从根节点到特定节点（包括该节点）的路径上的节点数称为节点的深度。
3. 二叉树的最大深度指的是其最左边节点的深度。因此，我们也可以将其视为树的高度。
4. 一棵树如果对于树中的每个节点，其左右子树的高度差不超过 1，则称为平衡树。

二叉搜索树的操作

二叉搜索树通常支持插入、删除和搜索等操作。每个操作的时间复杂度取决于树的高度，这意味着在最坏的情况下，操作将不得不遍历从根到最深叶节点的路径上的所有节点。

让我们以一个例子来说明一个树严重倾斜的问题。下图显示了这种情况

图 2. 一棵严重倾斜的树

尽管上图中显示的树是一棵有效的二叉搜索树，但它效率低下。如果我们想从上述树中插入、搜索或删除节点，我们可能需要遍历每个存在的节点。

因此，在上述树上每个操作的最坏情况时间复杂度为O(n)，其中n是树中的节点数。

但是，我们的目标是构建一棵平衡树。

平衡树是指对于每个节点，其左右子树的高度最多相差1。因此，平衡二叉树的高度受O(log₂?n)的限制，这意味着每个操作在最坏情况下的时间复杂度将为O(log₂?n)。我们可以认为这是一个相对于O(n)的重要改进。

理解自平衡二叉搜索树

确保树始终保持平衡的一种方法是实现自平衡二叉搜索树。自平衡二叉搜索树是一种二叉搜索树 (BST)，它始终努力将高度保持在最低水平，从而确保其操作保持O(log₂?n)的最坏情况时间复杂度。

让我们在数学上理解上述陈述，以获得更好的知识。

高度为 h 的二叉树最多可以有2⁰ + 2¹ + 2² + ... + 2^h = 2^(h+1) - 1 个节点。

n ≤ 2^h+1 -1

h ≥ ⌈log_2?(n + 1) - 1 ⌉ ≥ ⌊log_2? n ⌋

因此，对于自平衡二叉搜索树，最小高度必须等于 log_2? n 的向下取整值。此外，当一棵二叉树的每个节点的左右子树的高度差为-1、0或+1时，该二叉树就被认为是平衡的。这个值称为平衡因子。

平衡因子

= 左子树高度 - 右子树高度

自平衡二叉搜索树如何实现平衡？

关于自平衡，二叉搜索树在执行插入和删除操作后会进行旋转。以下是可以在不破坏二叉搜索树属性的情况下平衡二叉搜索树的两种旋转操作类型

1. 左旋
2. 右旋

现在让我们简要地理解上述两种操作。

左旋

左旋转是二叉搜索树的一种操作，我们将节点 N 向左推以平衡树。此旋转假定节点 N 有一个右子节点（或子树）。节点 N 的右子节点 R 成为 N 的父节点，R 的左子节点成为节点 N 的新右子节点。当节点 N 的右子树的高度明显（取决于树的类型）大于其左子树时，特别会使用此旋转。

现在让我们来看下面的图来说明这一点。

图 3. 节点 A 的左旋转

在上图中，当我们围绕节点 A 进行左旋转时，节点 B 成为子树的新根。节点 A 成为节点 B 的左子节点，子树 y 成为节点 A 的右子树。

右旋

右旋转是二叉搜索树的另一种操作，我们将节点 N 向右推以平衡树。此旋转假定节点 N 有一个左子节点（或子树）。节点 N 的左子节点 L 成为 N 的父节点，L 的右子节点成为 N 的新左子节点。当节点 N 的左子树的高度明显（取决于树的类型）大于其右子树时，特别会使用此旋转。

现在让我们来看下面的图来说明这一点。

图 4. 节点 B 的右旋转

在上图中，当我们围绕节点 B 进行右旋转时，节点 A 成为子树的新根。节点 B 成为节点 A 的左子节点，子树 y 成为节点 A 的左子树。

注意

旋转完成后，先前和最终树中节点的按中序遍历将是相同的，并且二叉搜索树的属性将得以保留。

理解自平衡二叉搜索树的类型

以下是一些实现此类型树的数据结构

1. 2-3 树
2. 红黑树
3. AA 树
4. AVL 树
5. B 树
6. Scapegoat Tree (替罪羊树)
7. 伸展树
8. Tango Tree
9. Treap (随机二叉搜索树)
10. 加权平衡树

现在让我们简要讨论这些树。

2-3 树

2-3 树是一种自平衡二叉搜索树，其中树中的每个节点要么具有

1. 两个子节点和一个数据元素，或者
2. 三个子节点和两个数据元素，或者
3. 叶节点位于同一层，没有子节点，但有一个或两个数据元素。

让我们看一个 2-3 树的例子

图 5. 一棵 2-3 树

从上图可以看出，这棵树满足前面提到的所有规则。

2-3 树在 Big-O 表示法中的平均和最坏情况下的时间复杂度相同，即：

1. 空间 - O(?n)
2. 搜索 - O(log₂?n)
3. 插入 - O(log₂?n)
4. 删除 - O(log₂?n)

红黑树

红黑树是一种自平衡二叉搜索树，其中每个节点存储一个额外的位，表示用于在插入和删除操作期间确保树平衡的颜色。此树的每个节点都必须遵循以下规则，包括二叉搜索树施加的规则：

1. 每个节点都染成黑色或红色。
2. 树的根节点始终是黑色的。
3. 树的所有 NIL 叶节点都必须是黑色的。
4. 不允许有两个相邻的红色节点，这意味着红色节点既不能有红色子节点，也不能有红色父节点。
5. 从一个节点到其后代 NIL 节点的每条路径都具有相同数量的黑色节点。

下面是红黑树的一个例子

图 6. 一棵红黑树

红黑树在 Big-O 表示法中的平均和最坏情况下的时间复杂度相同，即：

1. 空间 - O(?n)
2. 搜索 - O(log₂?n)
3. 插入 - O(log₂?n)
4. 删除 - O(log₂?n)

AA 树

AA 树是红黑树的变体，它使用层级概念来平衡二叉树。然而，与红黑树不同的是，AA 树上的红色节点只能作为右子节点添加，这也意味着红色节点不能作为左子节点出现。AA 树遵循以下五个规则：

1. AA 树中每个叶节点的层级都是一。
2. 每个左子节点的层级比其父节点精确少一。
3. 每个右子节点的层级小于或等于其父节点。
4. 每个右孙节点的层级严格小于其祖父节点。
5. 层级大于一的每个节点都有两个子节点。

下面是一个 AA 树的例子

图 7. 一棵 AA 树

AA 树保证了快速的操作，时间复杂度为 ? (log₂?n)，并且其实现代码是所有平衡树中最短的。

AVL 树

AVL 树是另一种自平衡二叉搜索树的例子，其中对于树中的所有节点，左子树和右子树的高度差不能超过一。这个差值也称为平衡因子，定义为

平衡因子

= 左子树高度 - 右子树高度

AVL 树的平衡因子是一个介于 -1 到 1 之间的整数。

下面是一个 AVL 树的例子

图 8. 一棵 AVL 树

AVL 树在 Big-O 表示法中的最坏情况时间复杂度如下：

1. 空间 - O(?n)
2. 搜索 - O(log₂?n)
3. 插入 - O(log₂?n)
4. 删除 - O(log₂?n)

B 树

B 树是自平衡二叉搜索树的另一个例子，它简化了二叉搜索树，允许节点拥有两个以上的子节点。

根据 Knuth 的定义，m 阶 B 树是满足以下某些属性的树：

1. B 树的每个节点最多有 n 个子节点。
2. 每个非叶节点（根除外）至少有 [n/2] 个子节点。
3. 如果根不是叶节点，则它至少有两个子节点。
4. 具有 m 个子节点的非叶节点包含 m - 1 个键。
5. 所有叶子都存在于同一层，并且不包含任何信息。

让我们看一个 B 树的例子

图 9. 一棵 B 树

B 树非常适合读取和写入相当大块数据的存储系统。这些树也用于数据库和文件系统中。

重要提示：3 阶 B 树被视为 2-3 树。

B 树在 Big-O 表示法中的平均和最坏情况下的时间复杂度相同，即：

1. 空间 - O(?n)
2. 搜索 - O(log₂?n)
3. 插入 - O(log₂?n)
4. 删除 - O(log₂?n)

Scapegoat Tree (替罪羊树)

替罪羊树 (Scapegoat Tree) 是一种自平衡二叉搜索树，它不需要为树的每个节点进行任何额外的存储。由于其较低的开销和易于实现，替罪羊树成为一种有吸引力的自平衡二叉搜索树选择。

平衡的概念是确保节点具有 α (alpha) 大小的平衡，这意味着左右子树的大小最多是节点大小的 α 倍，即 α * (节点大小)。这个想法基于这样的事实：如果一个节点是 α 重量平衡的，那么它也是高度平衡的，高度小于或等于 log_(1/α) size + 1。

替罪羊树在 Big-O 表示法中的平均情况时间复杂度如下：

1. 空间 - O(?n)
2. 搜索 - O(log₂?n)
3. 插入 - O(log₂?n)
4. 删除 - O(log₂?n)

替罪羊树在 Big-O 表示法中的最坏情况时间复杂度如下：

1. 空间 - O(?n)
2. 搜索 - O(log n)
3. 插入 - 摊销 O(log n)
4. 删除 - 摊销 O(log n)

伸展树

伸展树 (Splay Tree) 是另一种自平衡二叉搜索树的例子，它增加了一个属性，可以快速地再次访问最近访问过的元素。该树包含二叉搜索树的所有操作，如插入、删除和搜索，并增加了一个称为伸展的操作。伸展是伸展树中与在树根执行的每个操作相关的常见操作。特定数据元素的伸展会重新排列树，使该数据元素位于其根部。

例如，每当我们对特定数据元素执行标准二叉搜索时，随后以特定顺序对树进行旋转，使得该数据元素成为根。我们还可以使用自顶向下的算法将搜索和重新组织操作合并为单个阶段。

伸展在访问数据元素（例如 x）时依赖于三个因素：

1. 数据元素 x 是其父节点 p 的左子节点还是右子节点。
2. 父节点 p 是否为根节点，如果不是，则：
3. 父节点 p 是其父节点 q（x 的祖父）的左子节点还是右子节点。

根据上述因素，我们将旋转分为不同类型：

1. Zig 旋转 [右旋转]
2. Zig Zig 旋转 [两次右旋转]
3. Zag 旋转 [左旋转]
4. Zag Zag 旋转 [两次左旋转]
5. Zig Zag 旋转 [先 Zig 后 Zag]
6. Zag Zig 旋转 [先 Zag 后 Zig]

伸展树在 Big-O 表示法中的平均情况时间复杂度如下：

1. 空间 - O(?n)
2. 搜索 - O(log n)
3. 插入 - O(log n)
4. 删除 - O(log n)

伸展树在 Big-O 表示法中的最坏情况时间复杂度如下：

1. 空间 - O(?n)
2. 搜索 - 摊销 O(log n)
3. 插入 - 摊销 O(log n)
4. 删除 - 摊销 O(log n)

Treap (随机二叉搜索树)

Treap (随机二叉搜索树) 数据结构是一种自平衡二叉搜索树，它是二叉树和二叉树的组合；然而，它不能保证高度为 O(log₂ n)。其思想是利用随机化和二叉堆属性来维护高概率的平衡。

Treap 的每个节点包含两个值：

1. 键 (KEY): 键是一个遵循标准二叉搜索树排序的值。
2. 优先级 (PRIORITY): 优先级是随机分配的值，遵循最大堆属性。

让我们看一个 Treap 的例子

图 10. 一棵 Treap

上图展示了一个带有字母键和数字最大堆顺序的 Treap。

Treap 在 Big-O 表示法中的平均情况时间复杂度如下：

1. 空间 - O(?n)
2. 搜索 - O(log₂?n)
3. 插入 - O(log₂?n)
4. 删除 - O(log₂?n)

Treap 在 Big-O 表示法中的最坏情况时间复杂度如下：

1. 空间 - O(?n)
2. 搜索 - O(?n)
3. 插入 - O(?n)
4. 删除 - O(?n)

加权平衡树

加权平衡树 (Weight Balanced Trees) 是用于实现有限集和有限映射的二叉搜索树。尽管像红黑树和 AVL 树这样的其他平衡二叉搜索树使用子树的高度来进行平衡，但加权平衡树的平衡是基于每个节点下方子树的大小。树的大小是它包含的连接数。加权平衡树通过保持每个节点子树的大小在彼此的常数因子范围内来保持平衡，从而确保单路径操作（例如查找和插入）的对数周期。加权平衡树占用与树中连接数成比例的空间。

加权平衡树的节点具有以下字段：

1. 任何有序类型的键
2. 值（可选字段），用于映射
3. 指向节点的左指针和右指针
4. 整数类型的计数

自平衡二叉搜索树的应用

我们可以以通常的方式使用自平衡二叉搜索树来构建和维护有序列表，如优先队列。我们还可以将这些树用于关联数组；键值对根据键单独按顺序插入。在这种容量下，自平衡二叉搜索树与其主要竞争对手哈希表相比具有多个优缺点。自平衡二叉搜索树的一个优点是它们允许以（实际上是渐近最优的）键顺序快速枚举数据元素，这在哈希表中是不可能的。这些树的一个缺点是，当可能存在许多具有相同键的数据元素时，它们的查找算法会变得更加复杂。这些树具有比哈希表更好的最坏情况查找实现（O(log n) 对比 O(?n)）；然而，它们的平均情况实现较差（O(log n) 对比 O(?1)）。

我们可以使用自平衡二叉搜索树来实现任何需要可变有序列表以获得最佳最坏情况渐近执行的算法。例如，如果我们尝试使用自平衡二叉搜索树实现二叉树的排序操作。在这种情况下，我们有一个易于定义但渐近最优的（O(n log n) 排序算法。同样，计算几何中有许多算法通过操纵自平衡二叉搜索树中的区分来有效地解决线段交点问题和点定位问题。（然而，对于平均情况的实现，自平衡二叉搜索树可能不如其他解决方案有效。特别是二叉树排序由于树平衡的开销和缓存访问模式，比归并排序、快速排序或堆排序慢。）

自平衡二叉搜索树是灵活的数据结构。可以轻松地扩展它们以记录额外数据或高效地执行新操作。例如，我们可以记录每个子树中具有特定属性的节点数，从而能够以 (O(log n) 时间计算具有该属性的特定键范围内的节点数。例如，我们可以使用这些扩展来优化数据库查询或其他列表处理算法。

结论

在本教程中，我们详细学习了自平衡二叉搜索树。我们还讨论了不同类型的自平衡二叉搜索树。