data-structures - 使用二叉搜索树(拉伸(stretch)树)实现 Rope 数据结构

Question

在 Rope data structure 的标准实现中使用拉伸(stretch)树，节点将根据从字符串开头测量每个节点位置的排名统计来排序，因此通常在二叉搜索树中找到的键是无关紧要的，不是吗？

我问是因为下图中显示的键(感谢维基百科!)是字母，一旦节点数超过所选字母表的长度，这些字母可能会变得不唯一。使用整数或完全避免使用键不是更好吗？

另外，任何人都可以指出在每次操作后重新计算排名统计的逻辑的良好实现吗？

据推测，如果拆分的索引落在附加到特定节点的子字符串中，例如，在上面节点 E 上的“Hel”和“llo_”之间，您将从 E 中删除子字符串，拆分它并重新附加它作为 E 的两个 child 。对吗？

最后，经过一定次数的此类操作，我想这棵树最终可能会得到与字母一样多的叶子。跟踪它并根据需要修剪树(通过组合子字符串)的最佳方法是什么？

谢谢!

Answer 1

就其值(value)而言，您可以通过将子字符串附加到二叉搜索树的每个节点(而不仅仅是如上所示的叶节点)来使用 Splay 树实现 Rope。

每个节点的等级是它的大小加上它的左子树的大小。但是在 splay 操作期间重新计算排名时，您需要记住也要沿着 node.left.right 分支走下去。

如果每个节点都记录了对它所代表的子字符串的引用(参见实际子字符串本身)，那么一切都会运行得更快。这样，当拆分操作落在现有节点内时，您只需修改节点的属性以反射(reflect)要拆分的子字符串的右侧部分，然后添加另一个节点来表示左侧部分并将其与左侧子树合并。

如上所述，每个节点记录(除了它的左、右和父属性等)它的等级、大小(以字符为单位)和它代表的第一个字符在你试图修改的字符串中的位置。这样，您就永远不会真正修改初始字符串:您只需对树的位进行操作，并在准备好时通过按顺序遍历它来重现最终字符串。