CS61B学习笔记(十四)-Rd11-树

Reading: 11. 平衡树 ·拥抱61B — 11. Balanced Trees · Hug61B (gitbooks.io)

当我们随机插入 BST 时，平均深度和高度预计为Θ(*logN*) .

但是，我们并不总是能够以随机顺序插入 BST。如果我们的数据是实时的呢？然后，我们将被迫按照数据到达我们的顺序进行插入。

下面我们将了解一棵始终保持平衡的树！

B-trees / 2-3 trees / 2-3-4 trees

cs61b 2019 lec17 ds3 2-3 trees, 2-3-4 trees - Google 幻灯片

BST 的问题在于我们总是插入叶节点。这就是导致高度增加的原因。

当我们开始插入节点时，我们可能会破坏平衡结构。所以，让我们想出一种方法，在添加新节点时保持树的平衡！

疯狂的想法：我们永远不要添加叶子节点！当我们插入时，让我们只添加到当前的叶节点。这样，高度永远不会增加。

但是，您能看到这种插入方案的潜在问题吗？如果我们搜索 19，那么我们将向下遍历到包含它的节点，我们仍然必须像查看数组一样查看该节点才能到达 19 元素。这将导致 N 的运行时！

解决方案：设置单个节点中元素数量的限制。比方说 4.如果我们需要在节点已经有 4 个元素的情况下向节点添加一个新元素，我们会将节点分成两半。通过向上凸起左中间的节点。

通过在中间拆分节点，我们保持了完美的平衡！这些树被称为 B 树或 2-3-4/2-3 树。2-3-4 和 2-3 是指每个节点可以拥有的子节点数。因此，一棵 2-3-4 棵树可以有 2、3 或 4 个孩子，而一棵 2-3 棵树可以有 2 或 3 个孩子。这意味着当 2-3-4 棵树有 3 个节点时，它们会拆分节点，并且需要再添加一个节点。2-3 棵树在有 2 个节点后分裂，需要再添加一个。

Insertion Process 插入过程

The process of adding a node to a 2-3-4 tree is:
将节点添加到 2-3-4 树的过程是：

1. 我们仍然总是插入到叶子节点中，所以拿你要插入的节点，用它沿着树向下遍历，根据要插入的节点是大于还是小于每个节点中的项目来左右移动。
2. 将节点添加到叶节点后，如果新节点有 4 个节点，则弹出左侧中间的节点并相应地重新排列子节点。
3. 如果这导致父节点有 4 个节点，则再次弹出左中间节点，相应地重新排列子节点。
4. 重复此过程，直到父节点可以容纳或您到达根节点。

B树不变量

练习 11.3.1：按此顺序将 1-7 插入到 B 树中。树的高度是多少？我们可以改变插入的顺序，以便降低高度吗？这里有一个 很酷的 B 树可视化工具 可能会有所帮助！

根据您插入节点的顺序，B 树的高度可能会发生变化。然而，这棵树将永远是浓密的。

高度为1的B-Tree需要先添加2-6，最后添加1和7实现。

B 树具有以下有用的不变量：

• 所有叶子与源的距离必须相同。
• 包含 k 项的非叶节点必须具有k+1 的子节点。

同时，这些不变量导致树总是浓密的。

B-Tree运行时分析

在 B 树中搜索的最坏情况是，如果每个节点中都有最大数量的元素，我们必须一直遍历到底部。我们将用于 L 表示每个节点中的元素数量。这意味着需要探索节点（因为最大高度是 logN 由于灌木丛不变），并且在每个节点上，我们需要探索 LlogN 元素。总的来说，我们需要运行 LlogN 操作。但是，我们知道 L 是一个常数，因此我们的总运行时间是 O*(log*N) 。

B-Tree 删除 （Extra）

如果您好奇，请看 these extra slides 。我们不会在这里讨论它们。

总结

BST 有最佳情况高度 Θ(logN) 和最坏情况高度 Θ(N) 。

• 大O与最坏的情况不是一回事！

B 树是对二叉搜索树的修改，可避免 Θ(N) 最坏的情况。

• 节点可以包含从1 到 L个 项目。
• 包含的工作原理几乎与普通 BST 完全相同。
• 通过向现有叶节点添加项目来添加工作。
  • 如果节点太满，它们就会分裂。
• 由此产生的树具有完美的平衡。操作的运行时为: O*(logN) 。
• 没有讨论删除。如果您好奇，请参阅其他幻灯片。
• 没有讨论过拆分是如何工作的 L>3 （参见其他类）。
• B 树更复杂，但它们可以有效地处理任何插入顺序。

目前问题:

• 分裂的实现过于复杂
• 删除的操作必须保证包含 k 项的非叶节点必须具有k+1 的子节点，因此删除会变得更加困难，可能需要添加额外的节点。

旋转树

cs61b 2020 lec18 ds4 balanced search trees - Google 幻灯片

rotation balancing demo - Google 幻灯片

BST 结构

对于任何 BST，有多种方式可以构建它以保持 BST 不变性。在第 11.1 章中，我们讨论了如何以不同顺序插入元素将导致不同的 BST。以下 BST 都包含元素 1、2 和 3，但结构各异。

然而，插入并不是产生相同 BST 不同结构的唯一方法。我们可以通过一种称为旋转的过程改变已经放置节点的树。

树的旋转

旋转的形式定义为：

• rotateLeft(G): 令 x 为 G 的右子节点。将 G 设为 x 的新左子节点。
• rotateRight(G): 令 x 为 G 的左子节点。将 G 设为 x 的新右子节点。

在接下来的几段文字中，我们将慢慢揭示这个过程。下面是对节点 G 进行左旋转时所发生的情况的图形描述。

G 的右子节点 P 与 G 合并，带着它的子节点一起。然后 P 将其左子节点传递给 G，并且 G 向左下移动成为 P 的左子节点。您可以看到树的结构以及级别数量发生了变化。我们也可以在非根节点上旋转。我们只需暂时断开节点与父节点的连接，旋转节点处的子树，然后重新连接新的根。

以下是 rotateRight 和 rotateLeft 的实现，由 普林斯顿文档 提供，为简单起见省略了一些代码行。

private Node rotateRight(Node h) {
    // assert (h != null) && isRed(h.left);
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    return x;
}

// make a right-leaning link lean to the left
private Node rotateLeft(Node h) {
    // assert (h != null) && isRed(h.right);
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    return x;
}

通过旋转，我们实际上可以完全平衡一棵树。在这些幻灯片中查看演示：点击这里

在下一章中，我们将学习一种特定的树数据结构，通过使用旋转保持平衡。

黑白树

cs61b 2020 lec18 ds4 balanced search trees - Google 幻灯片

在前一节中，我们说我们真的很喜欢 2-3 树，因为它们始终保持平衡，但我们也不喜欢它们，因为它们很难实现。但为什么不两者兼得呢？为什么不创建一棵使用 BST 实现的树，但在结构上与 2-3 树相同，因此保持平衡？（请注意，在本章中，我们将专注于 2-3 树，而不是 2-3-4 树）

红黑树的介绍

我们将通过查看 2-3 树来创建这棵树，并问自己我们可以进行什么样的修改来将其转换为 BST。

对于仅具有 2 个子节点（具有 2 个子节点的节点）的 2-3 树，我们已经有了一个 BST，因此我们不需要进行任何修改！

然而，当我们遇到 3 个节点时会发生什么呢？

我们可以创建一个“粘合”节点，该节点不包含任何信息，只用于显示其 2 个子节点实际上是一个节点的一部分。

然而，这是一个非常不优雅的解决方案，因为我们占用了更多的空间，并且代码会变得丑陋。因此，我们不使用粘合节点，而是使用粘合链接！

我们任意选择将左侧元素设为右侧元素的子节点。这导致了左倾树。我们通过将其标记为红色来显示链接为粘合链接。正常的链接是黑色的。由于这一点，我们将这些结构称为左倾红黑树（LLRB）。我们将在 61B 中使用左倾树。

左倾红黑树与 2-3 树具有一一对应的关系。每个 2-3 树都有与之关联的唯一 LLRB 红黑树。至于 2-3-4 树，它们与标准红黑树保持对应关系。

LLRB 的属性

LLRB(Left-Leaning Red Black Binary Search Tree)左倾黑白搜索树

以下是 LLRB 的属性：

• 与 2-3 树具有一一对应的关系。
• 没有节点有 2 条红色链接。
• 没有红色右链接。
• 从根到叶的每条路径具有相同数量的黑色链接（因为 2-3 树到每个叶子的链接数相同）。
• 高度不超过相应 2-3 树的高度的 2 倍 + 1。

注意，当我们对应到2-3树的时候需要考虑2-3树的两个不变量:

• 所有叶子与源的距离必须相同。
• 包含 k 项的非叶节点必须具有k+1 的子节点。

LLRB 的插入

我们可以通过向 2-3 树插入并使用上述方案转换来随时插入到 LLRB 树。但是，这与我们最初创建 LLRB 的目的相违背，即避免复杂的 2-3 树代码！相反，我们将像对待普通 BST 一样插入到 LLRB 中。然而，这可能会破坏它与 2-3 树的一一映射，因此我们将使用旋转将树调整回正确的结构。

在插入 LLRB 时，我们需要解决的不同任务如下。

任务 1：插入颜色：因为在 2-3 树中，我们总是通过向叶节点添加来插入，所以我们添加的链接的颜色应始终为红色。

任务 2：右侧插入： 回想一下，我们使用左倾红黑树，这意味着我们永远不能有右侧的红色链接。如果我们在右侧插入，我们将需要使用旋转来维护 LLRB 不变式。

但是，如果我们在右侧插入时有一个红色链接，且左子节点也是红色链接，则出于在任务 3 中将会更清楚的目的，我们将暂时允许它。

任务 3：左侧双重插入： 如果存在 2 个连续的左链接，则我们有一个非法的 4 节点。首先，我们将旋转以创建在任务 2 中看到的相同树。然后，在这两种情况下，我们将翻转所有接触 S 的边的颜色。这相当于在 2-3 树中推动中间节点上升。

您可能需要经过一系列旋转才能完成转换。过程是：在 LLRB 树不满足与 2-3 树的一一对应或破坏 LLRB 不变式时，执行任务 1、2 或 3，具体取决于树的条件，直到您获得合法的 LLRB。

任务4：分离临时的4节点

如果存在具有两个红色子节点的任何节点，反转颜色。

以下是所有操作的摘要：

• 插入时：使用红色链接。
• 如果存在右倾的“3 节点”，我们有一个左倾违例
  • 旋转适当的节点向左以修复。
• 如果有两个连续的左链接，我们有一个不正确的 4 节点违例！
  • 旋转适当的节点向右以修复。
• 如果存在具有两个红色子节点的任何节点，我们有一个临时的 4 节点。
  • 颜色翻转节点以模拟拆分操作。

运行时

由于左倾红黑树与 2-3 树具有一一对应的关系，并且始终保持在其 2-3 树的 2 倍高度之内，操作的运行时将花费 logN 时间。

以下是插入 LLRB 的抽象代码：

private Node put(Node h, Key key, Value val) {
    if (h == null) { return new Node(key, val, RED); }

    int cmp = key.compareTo(h.key);
    if (cmp < 0)      { h.left  = put(h.left,  key, val); }
    else if (cmp > 0) { h.right = put(h.right, key, val); }
    else              { h.val   = val;                    }

    if (isRed(h.right) && !isRed(h.left))      { h = rotateLeft(h);  }
    if (isRed(h.left)  &&  isRed(h.left.left)) { h = rotateRight(h); }
    if (isRed(h.left)  &&  isRed(h.right))     { flipColors(h);      } 

    return h;
}

总结

• 二叉搜索树很简单，但易受不平衡的影响，导致糟糕的运行时。
• 2-3 树（B 树）是平衡的，但实现起来痛苦，而且相对较慢。
• LLRB 的插入简单易行（但删除困难）。
• 通过与 2-3 树保持数学双射来工作。
• Java 的 TreeMap 是一棵红黑树（但不是左倾的）。
• LLRB 与 2-3 树保持一致，标准红黑树与 2-3-4 树保持一致。
• 允许在任一侧使用粘合链接（请参阅Red-Black Tree）。
• 实现更复杂，但速度明显更快。

删除过于复杂，暂不讨论