用于编辑文本的红黑树

Question

我正在阅读 Joaquin Cuenca Abela 的 this great article。他谈到用红黑树来实现一个片段table，而不是双向链表。

我无法理解这可能与正在更改的缓冲区有何关系。例如，拿这两个缓冲区（原始的，追加的）：

Hello![=10=]    Original
y           Append

假设 table 看起来像这样：

buffer    start    length
original  0        2
original  5        2
append    0        1

我们最终应该得到：

Hey![=12=]

使用双向链表，可以这样实现：

------------------   -------------------   ----------------
Buffer = ORIGINAL|   |Buffer = ORIGINAL|   |Buffer = APPEND
Start  = 0       |<--|Start  = 5       |<--|Start  = 0
Length = 2       |   |Length = 2       |   |Length = 1
Next   = 0x01    |-->|Next   = 0x02    |-->|Next   = NULL
Previous = NULL  |   |Previous = 0x01  |   |Previous = 0x01
------------------   -------------------   ----------------

如果文件最初是作为 char 数组或其他内容加载的，那么在编辑后运行这看起来真的很简单而且很快。另一方面，据我了解，红黑树看起来像这样：

                       ------------------
                       size       = 2
                       size_left  = 1
                       size_right = 2
                       colour     = black
                       ------------------
                        /              \
                       /                \
                      /                  \
             ----------------      ---------------- 
             size       = 1        size       = 2
             size_left  = 0        size_left  = 0
             size_right = 0        size_right = 0
             colour     = red      colour     = red
             ----------------      ----------------
             /          \              /           \
            /            \            /             \
         NULL            NULL       NULL           NULL

我没有看到在编辑后重新绘制文档其余部分的明确方法。当然，insert/delete/lookup 将片段添加到树中会更快。但是我不知道如何构建用于查看的已编辑缓冲区。

我错过了什么？如果我有一个编辑器，并且我 deleted/inserted 一大块文本，我将如何遍历树以重新绘制缓冲区并正确反映此编辑？而且，这比链表提供的 O(n) 时间复杂度快多少？

Answer 1

我不太理解您提供的树图，因为（与 linked 列表图不同）它们似乎与实际存储的数据无关。实际上，它们将具有基本相同的数据字段（Buffer、Start 和 Length）外加一个 Size，它是该节点为首的子树中片段的总大小。而不是 Previous 和 Next 指针，它们将有 Left 和 Right (child) 指针。

而且，当然，他们将需要一些额外的数据来保持树的平衡（在 red/black 树的情况下需要 red/black 位，但我不认为保持平衡的机制在这里很重要；例如，您可以使用 AVL 树而不是 red/black 树。所以我将在这里忽略节点的那一部分。

为了找到给定偏移量的数据，Size 字段是必需的（因此，如果从来不需要进行此类查找，则可以省略。）我认为 linked文章以块为单位衡量大小，而我倾向于以字符（甚至字节）为单位衡量大小，这就是我将在此处说明的内容。正如 linked 文章指出的那样，Size 字段可以很容易地以对数时间精确地维护，因为它指的是子树的大小，而不是它在数据流中的位置。

您使用“大小”字段通过缓冲区偏移查找节点。如果偏移量小于左边的Sizechild，则递归到左边child；如果它至少是当前长度加上左侧的大小 child，则从偏移量中减去该总和并递归到右侧 child。否则，当前节点包含所需的偏移量。这不能超过最大树深度，如果树合理平衡，最大树深度为 O(log N)。

我也对你的 linked 列表图感到有点困惑，在我看来它代表缓冲区 He|![=12=]|y，而我希望它是 He|y|![=13=]：

------------------   -------------------   -------------------
Buffer = ORIGINAL|   |Buffer = APPEND  |   |Buffer = ORIGINAL|
Start  = 0       |<--|Start  = 0       |<--|Start  = 5       |
Length = 2       |   |Length = 1       |   |Length = 2       |
Next   = 0x01    |-->|Next   = 0x02    |-->|Next   = NULL    |
Previous = NULL  |   |Previous = 0x01  |   |Previous = 0x01  |
------------------   -------------------   -------------------

等价的平衡树是：

                       -------------------
                       | Size   = 5      |
                       | Buffer = APPEND |
                       | Start  = 0      |
                       | Length = 1      |
                       -------------------
                        /              \
                       /                \
                      /                  \
             -------------------   ------------------- 
             |Size   = 2       |   |Size   = 2       |
             |Buffer = ORIGINAL|   |Buffer = ORIGINAL|
             |Start  = 0       |   |Start  = 5       |
             |Length = 2       |   |Length = 2       |
             -------------------   -------------------
               /          \            /           \
              /            \          /             \
            NULL            NULL    NULL           NULL

从给定节点开始按顺序查找下一个节点的算法如下：

而右child指针为NULL，return指向parent。继续移动到 parent，直到找到一个节点，其右 child 指针既不是 NULL 也不是 child 被 return 编辑的节点。
向右移动child.
当左child指针不为NULL时，向左移动child

此算法的给定应用显然可以对步骤 1 and/or 3 进行 O(log N) 次迭代。但是，重复应用（如您按顺序遍历缓冲区时的情况）节点的）将是线性的总共因为任何给定的 link (parent ⇆ child) 将被恰好遍历两次，每个方向一次.因此，如果遍历整棵树，遍历的 link 总数是树中 link 数量的两倍。（并且树比节点少 link，因为它是树。）

如果你用字符来衡量大小，那么你可以避免"Length"字段的需要，因为一个节点直接引用的数据的长度只是节点的子树大小和它的 children 子树大小的总和。这可以（几乎）将节点的大小减小到 linked-list 节点的大小，假设您可以找到某种方法来编码 red/black 位（或其他平衡信息），否则将被填充位。

另一方面，使用 parent 指针以及两个 child 指针的二叉树实现有些常见。（通过查看上面的遍历算法可以清楚地知道这有何帮助。）但是，没有必要存储 parent 指针，因为它们可以，例如，在树的任何给定遍历期间维护在数组中parent 树中按深度索引的指针。这个数组显然不大于最大树深度，所以可以使用一个小的 (~50) fixed-length 数组。

这些优化也远远超出了这个答案。

Answer 2

If I had an editor, and I deleted/inserted a chunk of text, how would I traverse the tree to repaint the buffer and correctly reflect this edit? And, how would this be faster than the O(n) time complexity offered by the linked list?

假设片段 table 很大，并且重新绘制屏幕上可见的缓冲区部分通常只需要访问几个连续的节点。假设您在特定编辑后需要访问的节点位于文档的中间或接近末尾。

使用双向链表，您可能需要从头开始遍历许多节点table才能到达编辑的开头。那是 O(n)。从那里开始，您将通过接下来的几个节点来进行绘画。

对于平衡树，您可以在 O(log_2 n) 中找到第一个节点。从那里开始，您进行顺序遍历以访问绘画所需的下几个节点。

在添加、删除或修改一个片段后更新树中的位置是一个简单的问题 adding/subtracting 从 new/modified 节点的父节点开始的祖先位置的值.那也是 O(log_2 n).

用于编辑文本的红黑树

Red-black tree for editing text

algorithm

binary-tree

text-editor

red-black-tree