Editing Rope (data structure) (section)

=== Rebalance ===
: ''Definition:'' Collect the set of leaves ''L'' and rebuild the tree from the bottom-up.

<syntaxhighlight lang="java">
static boolean isBalanced(RopeLike r) {
    val depth = r.depth();
    if (depth >= FIBONACCI_SEQUENCE.length - 2) {
        return false;
    }
    return FIBONACCI_SEQUENCE[depth + 2] <= r.weight();
}

static RopeLike rebalance(RopeLike r) {
    if (!isBalanced(r)) {
        val leaves = Ropes.collectLeaves(r);
        return merge(leaves, 0, leaves.size());
    }
    return r;
}

static RopeLike merge(List<RopeLike> leaves) {
    return merge(leaves, 0, leaves.size());
}

static RopeLike merge(List<RopeLike> leaves, int start, int end) {
    int range = end - start;
    if (range == 1) {
        return leaves.get(start);
    }
    if (range == 2) {
        return new RopeLikeTree(leaves.get(start), leaves.get(start + 1));
    }
    int mid = start + (range / 2);
    return new RopeLikeTree(merge(leaves, start, mid), merge(leaves, mid, end));
}
</syntaxhighlight>