我一直在研究此链接中描述的树数据结构（靠近底部）：
http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/
提到这个数据结构可以是一个手指树。然而，在对手指树进行更多研究后，我发现这缺少使手指树成为手指树的“手指”。相反，这似乎只是一个带注释的二叉树（用子树大小注释）。
您是否知道该数据结构的现有实现（任何语言），我可以将其用作我自己实现的参考（尽管，最好不是函数式编程语言的实现）？
或者，将子树大小注释改造成现有树数据结构的最佳方法是什么？
谢谢！
Simon Tatham 的计数 B 树是相似的。如果节点计数被替换为像调整中那样的缓冲区宽度，则这些提供像绳索一样的操作。
事实上，通过阅读您引用的页面，我看到它被用作编辑器的片断表或线表
在论文中，Positional Delta Trees to reconcile updates with read-optimized data storage中，作者提出了一棵树，它在树中的节点之间保持的不变量的行为与 Xanadu的enfilades有着惊人的相似之处树也类似。
我在 github 上有一个名为Boost.Intrusive Annotated Trees的项目，旨在为 Boost.Intrusive 中的子树计数等注释提供通用支持。子树计数是我最初的用例。
目前它需要 C++11 可变参数模板并且只支持 rbtree，但它可以工作，我希望及时消除这两个限制
更新：现在使用 C++03 构建。仍然只支持rbtree。
当与子树计数注释一起使用时，它类似于 jordan 在上面的答案中描述的 - 它在每个节点处计算 (left+right+1)。实现是完全不同的——它适用于任何节点和/或值特征；注释更新被集成到 rbtree 算法中，这使得重新计算的次数最少。
根据我前几天提出的问题，我已经实现了类似的东西。我为 boost::intrusive::rbtree/avltree 节点添加了注释来计算每个子树的大小（foreach 节点计数 = node->left->count + node->right->count + 1）。我通过使用 set_parent、set_left 和 set_right 的 boost value_traits 挂钩对树的插入/删除/重新平衡执行此更新。正如您引用的站点中所述，在每个节点更新后，更新当前节点的大小，然后遍历树直到找到根，并随时更新每个节点的大小。
当您想在特定位置插入树时，问题就来了。几乎在您执行此操作的那一刻，您将使树结构的键顺序不变量无效。这意味着您将无法通过键执行有效的 O(log n) 查找。但是，如果您想要这样，您可能无论如何都不需要尺寸注释。