algorithm - 用于编辑文本的红黑树

Question

我正在阅读 this great article华金昆卡阿贝拉。他谈到使用红黑树来实现一 block 表，而不是双向链表。

我在理解这可能与正在发生变化的缓冲区有什么关系时遇到了一些麻烦。例如，取这两个缓冲区(原始，附加):

Hello!\0    Original
y           Append

假设工件表如下所示:

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

我们应该最终得到:

Hey!\0

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

------------------   -------------------   ----------------
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

我看不到在编辑后重新绘制文档其余部分的明确方法。当然，插入/删除/查找将 block 添加到树中会更快。但我错过了如何构建已编辑的缓冲区以供查看。

我错过了什么？如果我有一个编辑器，并且我删除/插入了一大 block 文本，我将如何遍历树以重新绘制缓冲区并正确反射(reflect)此编辑？而且，这会比链表提供的 O(n) 时间复杂度更快吗？

Answer 1

我不太了解您提供的树图，因为(与链表图不同)它们似乎与实际存储的数据无关。实际上，它们将具有基本相同的数据字段(缓冲区、开始和长度)加上一个大小，即以节点为首的子树中片段的总大小。它们将具有 Left 和 Right(子)指针，而不是 Previous 和 Next 指针。

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

为了在给定的偏移量处找到数据，Size 字段是必需的(因此，如果从不需要进行此类查找，则可能会被忽略。)我认为链接的文章以片段为单位测量大小，而我倾向于以字符(甚至字节)为单位测量大小，这就是我将在此处说明的内容。正如链接文章所指出的，Size 字段可以很容易地以对数时间进行维护，因为它指的是子树的大小，而不是它在数据流中的位置。

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

你的链表图也让我有点困惑，在我看来它代表的是缓冲区 He|!\0|y ，而我希望它是 He|y|!\0 :

------------------   -------------------   -------------------
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

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

当右子指针为 NULL 时，返回父。继续移动到父节点，直到找到其右子指针既不是 NULL 也不是从其返回的子节点的节点。

移动到正确的 child 。

当左子指针不为 NULL 时，移动到左子

该算法的给定应用程序显然可能需要步骤 1 和/或 3 的 O(log N) 次迭代。但是，重复的应用程序(例如，当您按顺序遍历多个节点的缓冲区时)将是线性的总计，因为任何给定的链接(父 ⇆ 子)将被准确地遍历两次，每个方向一次。因此，如果遍历整棵树，遍历的链接总数是树中链接数的两倍。 (并且树的链接比节点少一个，因为它是一棵树。)

如果以字符为单位测量大小，则可以避免使用“长度”字段，因为节点直接引用的数据长度只是节点的子树大小与其子子树大小之和之间的差异。这可以(几乎)将节点的大小减小到链表节点的大小，假设您可以找到某种方法将红/黑位(或其他平衡信息)编码为填充位。

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

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