我发现了一个绳子树作为字符串的替代数据结构。
http://en.wikipedia.org/wiki/Rope_(data_structure)
去康卡特很容易，但我被困在分拆行动上。维基百科的文章说：
例如，要将图2.3中所示的22个字符的rope拆分为两个长度为11的等长组件rope，请查询第12个字符以将节点k定位在底层。移除k和g的右子节点之间的链接。转到父g并从g的权重中减去k的权重。向上移动树并移除任何右链接，从这些节点中减去k的权重（在这种情况下，仅节点d）。最后，将新孤立的节点K和H连接在一起，并创建一个新的父P，其权重等于左节点K的长度。
定位角色和重组孤儿是没有问题的。但我不明白“沿着树走，去掉任何右链接，从这些节点中减去k的权重”。示例在D处停止，但是如果您一字不差地遵循这些说明，那么您将继续转到B并删除D此算法中正确的停止要求是什么？如何避免只有一个子节点（左或右）的节点？
解释这一部分的伪代码算法将大有帮助。
最佳答案
维基百科的文章不是很明确如果当前节点是X且其父节点是Y则只有当X是Y的左子节点时，才会向上移动。从视觉上看，你是在向上和向右转，尽你所能。