使用二进制搜索树(splay树)实现Rope数据结构

Question

在使用展开树的Rope data structure的标准实现中，节点将根据从字符串开始测量每个节点的位置的排名统计来排序，所以通常在二进制搜索树中找到的关键字将是不相关的，不是吗？

我之所以这样问，是因为下图所示的密钥(感谢维基百科！)是字母，一旦节点的数量超过所选字母表的长度，这些字母可能就不是唯一的了。使用整数或者完全避免使用键不是更好吗？

​

另外，谁能给我一个好的逻辑实现，以便在每次操作后重新计算排名统计？

假设，如果拆分的索引落在附加到特定节点的子字符串中，例如，在上面的节点E上的"Hel“和"llo_”之间，您将从E中删除该子字符串，将其拆分并重新附加为E的两个子节点，对吗？

最后，经过一定数量的这样的操作后，我想，这棵树最终可能会有和字母一样多的叶子。如果有必要的话，最好的方法是跟踪并修剪树(通过组合子字符串)吗？

谢谢!

Answer 1

无论如何，您可以使用Splay树实现一个Rope，方法是将一个子字符串附加到二进制搜索树的每个节点(而不仅仅是上面所示的叶子节点)。

每个节点的排名是它的大小加上它的左子树的大小。但是，在展开操作期间重新计算等级时，您还需要记住沿着node.left.right分支进行遍历。

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

如上所述，每个节点记录(除了它的左、右和父属性等)它的等级、大小(以字符为单位)以及它所表示的第一个字符在您试图修改的字符串中的位置。这样，您实际上就不会修改初始字符串:您只需对树的某些部分执行操作，并在准备好按顺序遍历最后一个字符串时重新生成它。