叶子 · 子树长度和 · split/concat

rope：把字符串挂上平衡树

piece table 的定位问题最后靠一棵平衡树解决。rope 把这条路走到底：不再区分「原始」与「新增」，直接把文本本身切成小段挂到树上。

1 · 叶子与内部结点

定义 1.1（rope） 一棵二叉树。叶子各存一小段文本，中序遍历取出各叶子的文本并拼接即是文档。每个结点额外记录子树的字符总数与换行总数。

本系列的实现把这两个字段记在每个结点上（size 与 nls），而不是只记左子树的。两种写法等价：左子树的值可以从子结点的字段读出来，记在自己身上则少一次判空。经典论文按前者叙述，是因为它把「左子树长度」当作 BST 的键来理解。

叶子的长度有一个上限。1 MB 的文档在上限 64 下切成 16384 个叶子，树深 34。这个 16384 不是估计值，是精确的： $1048576 / 64$ 。

2 · 按下标定位

要取第 $i$ 个字符：从根开始，若 $i$ 小于左子树的字符数，往左走；否则减去左子树的字符数，看是否落在本结点的叶子里；再否则减去叶子长度，往右走。整条路径的长度就是树深。

图 2-1 · rope 的树形与一次按下标定位的下降路径。可改下标与操作，观察高亮的路径长度以及每个结点上的子树字符数与换行数。

插入是同一套动作的组合：在 $p$ 处把树劈成两棵，把新文本建成的小树接在中间，再拼回去。若 $p$ 落在某个叶子内部，劈开时要把那个叶子切成两半，这是 rope 唯一会真正复制字符的地方，复制量至多是一个叶子。

1 MB 文档上随机位置插入 1000 次，rope 的搬移量是 62346，平均每次 62.3 个字符，正好是叶子上限的量级；同一串编辑下两版 piece table 都是 0。rope 不是「零搬移」的结构，它是「搬移量与文档长度无关」的结构。

访问的结点数随规模的增长是这样的：

文档长度	$\log_2 n$	单次插入访问的结点数
1000	10.0	10.8
10000	13.3	22.6
100000	16.6	32.6
1000000	19.9	44.6

文档涨 1000 倍，访问结点数涨 4.1 倍。

3 · split 与 concat

rope 的另一半价值在于两个整树操作。

split(p) 把一条 rope 劈成前 $p$ 个字符与其余，两半各自仍是合法的 rope。concat(a, b) 把两条接成一条。经典论文里 concat 只需要新建一个根结点，两棵子树原样挂上去，代价 $O(1)$ ；带平衡维护的实现要多做一次自底向上的合并，代价 $O(\log n)$ ，但仍与文本长度无关。

实测 5 万字符加 5 万字符的两条 rope 做一次 concat，搬移字符数为 0。这一点是 rope 区别于前两种结构的地方：gap buffer 与 piece table 都没有便宜的整树拼接，前者要复制一整块内存，后者要把两串 piece 列表接起来（数组版是 $O(p)$ ）。

编辑器里用得上 concat 的场合比想象中多：粘贴一大段、撤销一次大范围替换、把一个文件的内容整体插入另一个文件。

4 · 叶子上限

叶子上限是 rope 唯一的调参旋钮，它同时决定三件事：结点数、树深、以及每次切分的复制量。

图 4-1 · 叶子上限对结点数、树深、访问结点数与搬移量的影响。可拖动上限，观察结点数与搬移量朝相反方向变化。

1 MB 文档上的实测：

叶子上限	结点数	深度	单次插入访问结点	单次插入搬移字符
16	65536	36	50.2	14.9
32	32768	34	45.8	30.9
64	16384	34	45.4	63.0
128	8192	29	40.2	127.2
512	2048	23	33.2	496.1

搬移量与上限严格成正比，访问结点数只随上限的对数缓慢下降。所以取舍的实质是「每个字符摊多少结点开销」对「每次切分复制多少字符」。上限取 512 时每次插入要复制近 500 个字符，已经接近小文档上朴素字符串的量级；取 16 时每 16 个字符就要挂一个结点，指针与计数字段的内存超过文本本身。生产实现（ropey、xi-editor）取的都是几百字节到 1 KB，理由是让一个叶子恰好落进一两条 cache line。

5 · 平衡从哪来

本系列用 treap 维持平衡：每个结点带一个随机优先级，树同时是按位置的二叉搜索树与按优先级的堆。split 与 merge 各十几行，不用讨论旋转的情形。

实现里踩过一个坑，值得写下来。切开一个叶子会造出两个新结点，最初的写法是给它们各发一个新的随机优先级。堆性质随即被破坏，而且不是偶发：不变量测试直接抓到一个优先级 0.5212 的结点挂着优先级 0.5320 的孩子。原因是 split 返回的子树要被上一层挂到某个结点下面，而那个结点的优先级只保证不小于被切的那个结点，管不住新发的随机数。

改法是让两个半叶子沿用被切结点的优先级。堆性质随之成立，代价是优先级不再两两不同，树的随机性变差。实测的退化幅度是这样的：新建的 1 MB rope 深度 34（20 个随机种子落在 30 到 36，中位 33，理论期望约 $3\log_2 n = 42$ ，比理论还好）；而 10 万字符文档跑 5 万次随机编辑之后，62303 个结点、深度 79，是 $\log_2 n$ 的 4.96 倍，超过了 3 倍这个常用的经验界。

79 层的树在实践中仍然完全够用，单次插入访问 57.8 个结点。但这个数字说明：论文里 treap 的期望深度分析假设优先级独立同分布，而叶子切分打破了这个假设。要恢复真正的随机性，得把叶子切分挪到 split 递归之外单独做一遍，代价是每次插入多两次 split 与两次 merge。本系列没有这么做，选择了更简单的实现与如实标注的退化幅度。

6 · 参考文献

Boehm, H.-J., Atkinson, R., & Plass, M. (1995). Ropes: an alternative to strings. Software: Practice and Experience, 25(12), 1315–1330.
Aragon, C. R., & Seidel, R. G. (1989). Randomized search trees. 30th Annual Symposium on Foundations of Computer Science, 540–545.
Levien, R. Rope science. xi-editor documentation. xi-editor.io/docs/rope_science_00.html.
Nielsen, N. (2023). ropey: a utf-8 text rope for manipulating and editing large texts. github.com/cessen/ropey.