string - 如何为绳索构建底层的二叉树结构？

Question

我正在阅读维基百科上的绳索。在那里，对于字符串“Hello_my_name_is_Simon”，给出了二叉树。那棵二叉树是怎么形成的？逐步表示将有所帮助！

Answer 1

平衡二叉搜索树（红/黑树、splay 树等）的最常见实现支持称为join的操作，其工作方式如下：给定两棵树 T ₁和 T _{2 ，其中 T 1}中的所有键都小于相应的键在 T ₂中，并给定一个大于 T ₁中的所有值且小于 T ₂中的所有值的键 x ，将 T ₁、x 和 T ₂组合成一棵树。此操作的运行时间通常为 O(log n)，这比最初看起来可能的要快。

尽管这些操作被设计为在二叉搜索树上运行，但它们同样适用于通用二叉树。例如，如果您构建的绳索的底层二叉树是红/黑树或 splay 树，那么您可以使用join通过创建新的内部节点将文本连接到树的末端，然后使用join操作将两个现有的树（和新的内部节点）组合成一棵树。

这种方法的好消息是它运行得非常快（每个连接的 O(log n) 时间）并且它保持树的平衡。坏消息是join可能很难实现。加入两棵红/黑树的逻辑非常棘手。幸运的是，展开树的join逻辑非常简单，因此获得快速绳索的一个简单选择是使用展开树作为底层树结构。