language-agnostic - 是否有一个用子树大小注释的二叉搜索树的实现

Question

我一直在研究这个链接(靠近底部)描述的树数据结构:

http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/

提到这个数据结构可以是一棵手指树。然而，在对手指树进行更多研究之后，我发现这缺少使手指树成为手指树的“手指”。相反，这似乎只是一个带注释的二叉树(用子树大小注释)。

您是否知道此数据结构的现有实现(以任何语言)，我可以将其用作我自己的实现的引用(不过，最好不是函数式编程语言中的实现)?

或者，将子树大小注释改造为现有树数据结构的最佳方式是什么？

谢谢!

Answer 1

Simon Tatham's Counted B-Trees是相似的。如果节点数被缓冲区宽度替换，如 tweak , 这些提供类似 ropes 的操作.

事实上，通过阅读您引用的页面，我发现它被用作编辑器的 block 表或线表

在论文中，Positional Delta Trees to reconcile updates with read-optimized data storage , 作者提出了一棵树，其行为与它在树中节点之间的不变量有关，与 xanadu 的 enfilades 惊人相似，Counted B 树也与之相似。