Rope(绳索结构)

定义

Rope(绳索)是一种表示长字符串的二叉树结构,由 Boehm、Atkinson 和 Plass 于 1995 年的论文系统阐述:叶子节点存放短字符串片段,内部节点记录左子树的总长度(权值),整串是所有叶子的从左到右拼接。

原理

按位置索引字符时,与节点权值比较决定走左或右子树,O(log n) 定位;两串拼接只需新建一个根节点,O(1) 完成;切分沿定位路径拆开子树;插入等于切分加两次拼接。配合不可变节点可实现持久化,天然支持撤销与多版本。树失衡时按类似斐波那契的高度约束重平衡。

应用

Rope 适合频繁在中部编辑的超长文本:部分文本编辑器与 IDE 的缓冲区(如 Xi Editor 的 xi-rope、Zed 编辑器的 rope 变体)采用该结构;SGI STL 曾提供 rope 容器;某些字符串拼接密集的解释器运行时也使用类似结构。

优缺点

优点是长串拼接切分极快、易持久化;缺点是随机访问和顺序遍历慢于连续数组,短字符串场景得不偿失。