红黑树编辑文本

我被华金昆卡阿贝拉阅读this great article。他谈到使用红黑树实现一张表，而不是一个双向链表。红黑树编辑文本

我有一些麻烦，理解如何，这可能涉及到发生着变化的缓冲区。例如，拿这两个缓冲器（原件，附加）：

Hello!\0 Original 
y   Append

而且我们说这块表看起来像这样：

Hey!\0

：

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

我们应该结束了使用双向链表，实现这一点的一种像这样：

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

我没有看到一个明确的方式编辑后重新喷涂文档的其余部分。当然，插入/删除/查找将会更快地将部分添加到树中。但我错过了如何构建编辑缓冲区以供查看。

我错过了什么？如果我有一个编辑器，并且我删除/插入了一段文本，我将如何遍历该树来重新绘制缓冲区并正确反映该编辑？而且，这将如何比链表提供的O（n）时间复杂度更快？

来源

2017-10-10 avery_laird

@rici我想我主要理解树的工作原理，我只是不明白，在这个特定的上下文中（重新绘制缓冲区以反映变化），它具有优势。维基百科确实有一个很好的解释，但它不包括这个话题。我找不到任何其他资源来回答我的问题，所以我在这里问了他 –

我明白这一点;我不明白的是如何通过遍历树来反映所做的更改。使用双向链表，这是非常清楚的;每个节点指向原始位置和追加缓冲区，并且通过保持每个条目长度的运行总和，对节点所做的任何更改都可以通过遍历列表来反映：即通过选择打印来自原始缓冲区或附加缓冲区的某个位置和长度。对树来说，这是如何实现的对我而言并不清楚。但是，我确实理解轮换/必须“修复”树。 –

我认为我最大的问题是努力想通过一个例子。考虑到存储在树中的信息（在上面的例子中，或者其他例子中），我将会看到如何构建一个新的缓冲区。从概念上讲，在我看来，使用链表来构建一个缓冲区将花费O（N）。但是，对于树的等价操作不会采用O（NlogN）吗？因为，对于N件，它需要O（logN）来检索它的信息？ –

我真的不明白你所提供的树，因为（不像链表图），他们似乎都没有关系，实际存储的数据图。实际上，它们将具有基本相同的数据字段（缓冲区，开始和长度），再加上一个大小，这是由该节点开始的子树中的块的总大小。而不是Previous和Next指针，它们将具有Left和Right（子）指针。

当然，他们会有一些额外的数据需要，以保持树平衡（在红/黑树的情况下红/黑位，但我不认为维持平衡的机制是在这里很重要;例如，你可以使用AVL树代替红色/黑色树，所以我将忽略这个节点的部分

Size字段对于查找给定数据是必需的偏移量（因此，如果从来没有任何需要做这样的查找，可能会被忽略）。我认为链接的文章测量大小的块，而我倾向于测量大小的字符（甚至字节），这是我将在这里进行说明，正如链接文章所指出的那样，尺寸字段可以很容易地在对数时间内保持，因为它是可靠的rs设置为子树的大小，而不是其在数据流中的位置。

您使用大小字段来查找由缓冲区偏移一个节点。如果偏移量小于左侧子项的大小，则递归到左侧子项中;如果它至少是当前长度加上左侧孩子的大小，则从该偏移量中减去该总和并递归到正确的孩子中。否则，当前节点包含所需的偏移量。如果树合理平衡，这不会超过最大树深度，即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也不是从中返回的子节点。
移到正确的孩子。
虽然左子指针不为NULL，移到左子

该算法能明显采取的O给定应用（对数N）的步骤1和/或3的迭代然而，因为任何给定的链接（父节点⇆子节点）将被遍历两次，每个方向都会遍历一次，所以重复应用程序（如通过多个节点遍历缓冲区的情况下）将总计为线性。因此，如果遍历整个树，遍历的链接总数是树中链接数的两倍。（和树比节点少一个环节，因为它是一棵树。）

如果你衡量字符大小，那么就可以避免的“长度”字段的需要，因为长度由节点直接引用的数据仅仅是节点的子树大小与子树子树大小之和之间的差异。这可以（几乎）将节点的大小减小到链表节点的大小，假设你可以找到某种方法来编码红/黑比特（或其他平衡信息），否则将是填充比特。

另一方面，看到带有父指针的二叉树实现以及两个子指针有点常见。（通过查看上面的遍历算法，这是很明显的。）但是，没有必要存储父指针，因为它们可以在任何给定的遍历父指针数组中的树的遍历期间被维护，深入树中。这个数组显然不大于最大树深度，因此可以使用一个小的（〜50）固定长度的数组。

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

来源

2017-10-10 20:08:29 rici

谢谢，这有助于很多。我绝对搞砸了链表的顺序。我想，尺寸属性是我完全不能理解的。现在这似乎更清楚了。最后，如果需要线性时间遍历整个树，那么在大多数情况下（查找/插入/删除），树是否比链表更快？在这种情况下，他们都需要线性时间？ –

我认为，最大的好处就是查找。 AIUI，你通常会从几个大块创建缓冲区;有一个线性算法用于从预先排序的序列构建RB树，但我不认为这很重要。一旦找到端点，插入和删除将具有非常相似的时间。所以查找是至关重要的。 – rici

如果我有一个编辑器，并且我删除/插入了一段文本，我将如何遍历该树来重新绘制缓冲区并正确地反映该编辑？而且，这将如何比链表提供的O（n）时间复杂度更快？

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

使用双向链表时，您可能需要遍历起始表中的许多节点才能到达编辑的开始位置。那是O（n）。从那里，你走过接下来的几个节点去做绘画。

使用平衡树，您可以在O（log_2 n）中找到第一个节点。从那里，你可以按顺序遍历来访问下一个需要绘制的节点。

在添加，删除或修改一个片段之后更新树中的位置只需要从祖先的位置开始添加/减去从新/已修改节点的父节点开始的值。那也是O（log_2 n）。

来源

2017-10-10 22:51:59

红黑树编辑文本

回答

相关问题