在绳索数据结构上拆分操作
我正在为完全抽象的对象在C ++中实现Rope数据结构。 我遇到的问题是我无法弄清楚关键“拆分”操作的实施情况。 维基百科页面是有帮助的，但含糊不清，高度理论化，附在图片上的图片无助于我对算法的理解。 是否有一个很好的实现，或提供示例代码的论文？ 我曾尝试阅读原始论文，但他们也没有真正帮助。
假设我们有一个绳索结构
struct Rope {
Rope *left;
union {
Rope *right;
const char *string;
};
size_t length;
};
如果left为空，则字符为string[0], ..., string[length - 1] 。 否则，字符是left后面是right 。 撇开存储管理的问题，子串操作是
Rope *substring(const Rope *r, size_t start, size_t length) {
if (!r->left) {
Rope *s = new Rope;
s->left = 0;
s->string = r->string + start;
s->length = length;
return s;
} else if (start + length <= r->left->length) {
return substring(r->left, start, length);
} else if (r->left->length <= start) {
return substring(r->right, start - r->left->length, length - r->left->length);
} else {
Rope *s = new Rope;
s->left = substring(r->left, start, r->left->length - start);
s->right = substring(r->right, 0, length - (r->left->length - start));
s->length = length;
return s;
}
}