如何在 C++ 中实现 Rope 并维护节点的 weight 和 size？

2026-11-04技术老齐

Rope 可以显式存储 `size`

从零实现 Rope 时，建议让每个节点缓存其子树的总长度 size。内部节点的字段关系是：

weight = left->size
size   = left->size + right->size

创建父节点时，读取两个孩子的 size 就能计算长度，不必重新遍历子树。SGI 的 Rope 实现也在每个节点中存储了 size 字段，记录对应片段的长度。Rope Implementation Overview

你的例子中，NB1 的 weight 应为 20，总长度应为 40。

节点的 `weight` 和总长度有什么区别

concat(F1, F2) 会创建一个内部节点 NA1，同时引用 F1 和 F2：

                 NB1
               /     \
             NA1     NA2
            /   \   /   \
           F1   F2 F3   F4
           10   10 10   10

NA1 表示 F1 + F2，总长度为 20。它的 weight = 10，记录的是左子树 F1 的长度。

节点	表示的内容	`weight`：左子树长度	`size`：子树总长度
`NA1`	`F1 + F2`	10	20
`NA2`	`F3 + F4`	10	20
`NB1`	`F1 + F2 + F3 + F4`	20	40

计算父节点的 weight 时，要读取左孩子的 size：

NB1->weight = NA1->size;  // 20

不能写成：

NB1->weight = NA1->weight;  // 10，只代表 F1 的长度

weight 用来判断应进入哪个分支。对于从零开始的下标 i：

i < weight：进入左子树，下标仍为 i
i >= weight：进入右子树，下标改为 i - weight

长度信息如何向上传递

整个实现可以统一采用以下规则：

空 Rope：
    size = 0

叶节点：
    size = data.size()

内部节点：
    weight = size(left)
    size   = size(left) + size(right)

叶节点从实际字符串取得长度，父节点再读取孩子已经计算好的长度。每创建一个内部节点，只需常数次读取和一次加法。

如果采用原地修改，就在修改完成后，沿受影响路径从下往上更新这些字段。树发生旋转时，也要先更新位置较低的节点，再更新它的父节点。

也可以让所有节点只存 size，内部节点需要左子树长度时直接读取 left->size。这样能省去一个字段，weight 作为计算属性即可，无须重复存储。学习阶段同时保留两个字段，会更容易对照检查。

不存 `size`，能否计算总长度？

可以。最直接的方法是递归访问所有叶节点，累加它们的长度，耗时与访问到的叶节点数量成正比。反复这样计算，会拖慢构建和编辑操作。

如果内部节点已经维护了正确的 weight，还可以使用：

length(node) = node.weight + length(node.right)

weight 已经包含整个左子树的长度，因此只需沿最右路径继续计算：

std::size_t length_without_size(const Node* node) {
    if (!node) return 0;
    if (node->is_leaf()) return node->data.size();
    return node->weight + length_without_size(node->right.get());
}

这种方法需要 O(h) 时间，其中 h 是树高。新建连接节点时，为了确定它的 weight，仍可能需要遍历左侧 Rope 的最右路径。split 重建节点时，也可能重复进行这类计算。

不存 size 也能实现 Rope，但仅靠 weight，无法直接保证任意子树的长度查询都是 O(1)。显式缓存 size，更容易控制操作成本。

C++ 最小示例：连接、分割与长度维护

示例使用 C++17，以 nullptr 表示空 Rope，内部节点总有两个非空孩子。叶节点的 weight 约定为自身长度，分支判断只在内部节点上使用。

std::shared_ptr<const Node> 用于共享不可变子树。连接操作只创建父节点；分割操作只重建分割路径，原有 Rope 仍然保留。

#include <cassert>
#include <cstddef>
#include <limits>
#include <memory>
#include <stdexcept>
#include <string>
#include <utility>

struct Node;
using Rope = std::shared_ptr<const Node>;

struct Node {
    std::string data;  // 仅叶节点存放文本
    Rope left;
    Rope right;
    std::size_t weight = 0;
    std::size_t size = 0;

    explicit Node(std::string text)
        : data(std::move(text)),
          weight(data.size()),
          size(data.size()) {}

    // 由 concat 调用，保证 l、r 均非空
    Node(Rope l, Rope r)
        : left(std::move(l)),
          right(std::move(r)),
          weight(left->size) {
        if (right->size >
            std::numeric_limits<std::size_t>::max() - weight) {
            throw std::length_error("Rope size overflow");
        }
        size = weight + right->size;
    }

    bool is_leaf() const {
        return !left && !right;
    }
};

std::size_t length(const Rope& rope) {
    return rope ? rope->size : 0;
}

Rope make_leaf(std::string text) {
    if (text.empty()) return nullptr;
    return std::make_shared<Node>(std::move(text));
}

Rope concat(Rope left, Rope right) {
    if (!left) return right;
    if (!right) return left;
    return std::make_shared<Node>(
        std::move(left), std::move(right));
}

// 在位置 k 分割，返回 [0, k) 和 [k, size)
std::pair<Rope, Rope> split(const Rope& rope, std::size_t k) {
    if (k > length(rope)) {
        throw std::out_of_range("Invalid split position");
    }

    if (!rope) return {nullptr, nullptr};
    if (k == 0) return {nullptr, rope};
    if (k == rope->size) return {rope, nullptr};

    if (rope->is_leaf()) {
        return {
            make_leaf(rope->data.substr(0, k)),
            make_leaf(rope->data.substr(k))
        };
    }

    if (k < rope->weight) {
        auto [a, b] = split(rope->left, k);
        return {a, concat(b, rope->right)};
    }

    if (k == rope->weight) {
        return {rope->left, rope->right};
    }

    auto [a, b] = split(rope->right, k - rope->weight);
    return {concat(rope->left, a), b};
}

int main() {
    auto f1 = make_leaf(std::string(10, 'A'));
    auto f2 = make_leaf(std::string(10, 'B'));
    auto f3 = make_leaf(std::string(10, 'C'));
    auto f4 = make_leaf(std::string(10, 'D'));

    auto na1 = concat(f1, f2);
    auto na2 = concat(f3, f4);
    auto nb1 = concat(na1, na2);

    assert(na1->weight == 10);
    assert(na1->size == 20);
    assert(nb1->weight == 20);
    assert(nb1->size == 40);

    auto [prefix, suffix] = split(nb1, 15);

    assert(length(prefix) == 15);
    assert(length(suffix) == 25);
    assert(length(nb1) == 40);  // 原 Rope 仍然有效
}

split(nb1, 15) 会进入左子树，再把 F2 分成两段。返回的前半部分表示 F1 + F2[0, 5)，后半部分表示 F2[5, 10) + NA2。

所有新内部节点都通过 concat 创建，构造时会重新计算 weight 和 size，原节点无须更新。

效率还取决于树高和叶节点大小

对于这个实现，设树高为 h，分割点所在叶节点的长度为 b：

操作	时间复杂度	条件或原因
查询总长度	`O(1)`	读取缓存的 `size`
`concat`	`O(1)`	仅创建父节点，不做平衡或文本合并
按下标定位叶节点	`O(h)`	每层通过 `weight` 选择分支
`split`	`O(h + b)`	遍历并重建路径，必要时复制叶节点文本

示例没有实现平衡。如果持续执行：

rope = concat(rope, make_leaf("x"));

树会逐渐形成长链，树高可能与叶节点数量成正比。要让路径操作稳定地保持对数级复杂度，需要加入平衡策略。缓存 size 本身不会让树自动平衡。

叶节点的大小也要控制。这里的 substr 会复制文本，如果一个叶节点保存了整个大文件，即使树很浅，分割这个叶节点的成本仍可能很高。

长度单位也要统一。示例中的 std::string::size() 统计 char 元素数，保存 UTF-8 文本时，通常对应字节数。如果希望按 Unicode 码点或用户感知字符定位，就需要维护相应计数，并处理编码边界。

如何在 C++ 中实现 Rope 并维护节点的 weight 和 size？

Rope 可以显式存储 size

节点的 weight 和总长度有什么区别