Chapter 53: Mini Red-Black Tree

Mini red-black tree 要解决的问题，是把有序关联容器背后的平衡搜索树压缩成一组可实现、可验证的不变量。读完本章后，读者应能定位一个节点修改会破坏哪条红黑性质，追踪旋转、变色、插入修复、删除修复和迭代器移动之间的因果关系，并判断 lower_bound 为何可以在对数复杂度内返回第一个不小于给定 key 的位置。

本章的贯穿材料是一棵简化的唯一键树 mini_rb_tree<Key, Value, Compare>。它模拟 std::map / std::set 常见实现中的核心形状：节点保存 key/value、父子指针和颜色，容器保存一个 header 哨兵，header 同时记录 root、leftmost 和 rightmost。C++ 标准只规定 ordered associative containers 的接口语义和复杂度承诺，并未要求实现一定使用红黑树；这里讨论的是常见实现形状和教学简化代码。

贯穿操作序列是插入 10, 5, 15, 7, 6，随后删除 5，并查询 lower_bound(8)。这组操作覆盖普通二叉搜索树插入、红色父节点冲突、旋转、删除替换、黑高修复、端点迭代器和候选节点搜索。Mini 版本关注源码阅读所需的结构主干，省略 allocator traits、透明比较、节点句柄、merge 和多键容器等扩展接口。

判断一棵 mini red-black tree 是否正确，顺序应固定：先看二叉搜索树顺序，再看 parent / child 双向链接，再看 header 的 root / leftmost / rightmost，再看颜色与黑高，再看 iterator 端点行为，最后看异常安全与复杂度承诺。这个顺序贯穿本章所有小节。

53.1 node 结构

node 结构先定义树能表达的状态边界。一个红黑树节点需要保存元素本身、父节点、左右子节点和颜色；容器还需要一个哨兵节点把空树、根节点、最小节点、最大节点和 end() 统一到同一个状态对象中。

教学实现通常把节点分成 base 和 value 两层。base 只保存拓扑信息，value node 再保存 key/value。这样 iterator 可以只持有 base 指针，在需要解引用时再转回 value node；header 哨兵也可以复用 base 结构，无需构造一个假的 Value。

#include <cassert>
#include <functional>
#include <utility>

namespace mini {

enum class rb_color { red, black };

struct rb_node_base {
    rb_color color = rb_color::red;
    rb_node_base* parent = nullptr;
    rb_node_base* left = nullptr;
    rb_node_base* right = nullptr;
};

template <class Key, class Value>
struct rb_node : rb_node_base {
    Key key;
    Value value;

    template <class K, class V>
    rb_node(K&& k, V&& v)
        : key(std::forward<K>(k)), value(std::forward<V>(v)) {}
};

} // namespace mini

这一层代码只表达对象形状，还没有表达所有权。容器负责申请节点、构造 key/value、把节点接入树、在删除时析构并释放节点。节点之间的指针只表达链接关系；它们没有独立所有权语义。这个判断对后续 erase 很关键，因为删除一个节点时，先要把它从树结构中摘出，再销毁它承载的对象。

header 哨兵的常见布局可以写成以下不变量：header.parent 指向 root，header.left 指向最小节点，header.right 指向最大节点；空树时三者都回到 header。这个设计让 begin() 可以直接返回 header.left，end() 可以直接返回 header，--end() 可以直接走到 header.right。

template <class Key, class Value, class Compare = std::less<Key>>
class mini_rb_tree {
    using base = mini::rb_node_base;
    using node = mini::rb_node<Key, Value>;

    base header_{};
    std::size_t size_ = 0;
    Compare comp_{};

    base* root() noexcept { return header_.parent; }
    const base* root() const noexcept { return header_.parent; }
    base*& root_ref() noexcept { return header_.parent; }

    static node* as_node(base* p) noexcept {
        return static_cast<node*>(p);
    }

    void reset_header() noexcept {
        header_.color = mini::rb_color::black;
        header_.parent = &header_;
        header_.left = &header_;
        header_.right = &header_;
    }

public:
    mini_rb_tree() { reset_header(); }
};

空树也有完整状态：root、leftmost、rightmost 都指向 header，size 为 0，header 是黑色。选择 header 作为端点节点后，很多边界分支会变成普通指针判断。代价是所有旋转、插入、删除和 iterator 都必须维护 header，否则树内部仍然有序，外部接口却会返回错误端点。

node 结构的工程检查点有四个。第一，key 的顺序由 Compare 决定，节点指针顺序必须和 comparator 一致。第二，parent 指针必须和 left / right 指针双向一致。第三，颜色只参与平衡修复，不参与 key 比较。第四，header 属于容器状态，普通算法把它当作端点，解引用 header 属于调用错误。

53.2 rotate_left

左旋解决的是右子树局部过高或红色冲突向左侧转移的问题。它只改变一个局部三角关系：x、x->right 和 x->right->left。左旋完成后，中序遍历顺序保持不变，因为所有小于 y 且大于 x 的节点仍然落在二者之间。

左旋的输入前提是 x 存在右孩子 y。旋转前局部顺序是 x < y，y 的左子树所有 key 位于二者之间。旋转后 y 顶替 x 的位置，x 成为 y 的左孩子，原来的 y->left 成为 x->right。

void rotate_left(base* x) noexcept {
    base* y = x->right;
    assert(y != &header_);

    x->right = y->left;
    if (y->left != &header_) {
        y->left->parent = x;
    }

    y->parent = x->parent;
    if (x == root()) {
        root_ref() = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }

    y->left = x;
    x->parent = y;
}

这段代码的提交顺序围绕“先接管中间子树，再替换父链接，再落下旧根”展开。x->right = y->left 先处理夹在 x 和 y 之间的子树；随后让 y 接到 x 的原父节点位置；最后把 x 挂成 y->left。如果顺序反过来，短时间内可能丢失 y->left，调试时表现为 parent 链断裂或遍历跳过节点。

左旋本身不分配内存，不比较 key，也不构造元素。它的异常安全边界很清楚：旋转函数应当是 noexcept，因为它只改指针。红黑树插入和删除修复依赖这个性质；一旦修复阶段可能抛异常，容器就很难维持“节点已经接入树，但平衡修复未完成”的中间状态。

左旋后 header 的 root 可能变化，leftmost 和 rightmost 通常无需变化。根节点变化由 x == root() 分支维护。最小节点和最大节点仍然是同一批端点，因为旋转保持中序顺序。这个结论是源码阅读中的重要信号：旋转函数只维护 root，插入和删除函数负责维护 leftmost / rightmost。

53.3 rotate_right

右旋与左旋使用同一组不变量，只是方向镜像。它的输入前提是 x 存在左孩子 y。旋转后 y 顶替 x，x 成为 y 的右孩子，原来的 y->right 成为 x->left。

void rotate_right(base* x) noexcept {
    base* y = x->left;
    assert(y != &header_);

    x->left = y->right;
    if (y->right != &header_) {
        y->right->parent = x;
    }

    y->parent = x->parent;
    if (x == root()) {
        root_ref() = y;
    } else if (x == x->parent->right) {
        x->parent->right = y;
    } else {
        x->parent->left = y;
    }

    y->right = x;
    x->parent = y;
}

右旋同样保持中序顺序。旋转前局部顺序是 y < x，y->right 的所有 key 位于二者之间；旋转后这批节点成为 x->left。因此 rotate 的正确性判断应先检查二叉搜索树顺序，再检查 parent 指针，最后检查颜色修复能否继续进行。

下图只表达旋转影响的局部关系。图中 A、B、C 是子树，不代表单个节点；旋转后它们相对 key 顺序保持稳定。

旋转函数的最小验收标准是可逆性：对同一个局部结构执行一次右旋，再在新的父节点上执行一次左旋，应回到原始链接；执行一次左旋，再执行一次右旋，也应回到原始链接。这个测试不需要颜色参与，因为颜色修复属于 insert_fixup 和 erase_fixup 的责任。

53.4 insert

insert 的第一阶段仍然是普通二叉搜索树插入。它沿 root 向下比较 key，记录最后一个非 header 节点作为 parent，找到空子位置后构造新节点并接入树。红黑树的额外动作发生在接入之后：新节点初始设为红色，再交给 insert_fixup 修复颜色和局部形状。

下面的简化代码实现唯一键插入。它的异常边界分成两段：比较和节点构造发生在修改树之前；节点接入树之后，后续修复只做指针和颜色操作。这样可以让插入失败时树保持原状态，插入成功进入修复阶段后无需处理元素构造失败。

template <class K, class V>
std::pair<base*, bool> insert_unique(K&& key, V&& value) {
    base* parent = &header_;
    base* current = root();
    bool insert_left = true;

    while (current != &header_) {
        parent = current;
        node* current_node = as_node(current);
        if (comp_(key, current_node->key)) {
            current = current->left;
            insert_left = true;
        } else if (comp_(current_node->key, key)) {
            current = current->right;
            insert_left = false;
        } else {
            return {current, false};
        }
    }

    node* fresh = new node(std::forward<K>(key), std::forward<V>(value));
    fresh->color = mini::rb_color::red;
    fresh->left = &header_;
    fresh->right = &header_;
    fresh->parent = parent;

    if (parent == &header_) {
        root_ref() = fresh;
        header_.left = fresh;
        header_.right = fresh;
    } else if (insert_left) {
        parent->left = fresh;
        if (parent == header_.left) {
            header_.left = fresh;
        }
    } else {
        parent->right = fresh;
        if (parent == header_.right) {
            header_.right = fresh;
        }
    }

    ++size_;
    insert_fixup(fresh);
    return {fresh, true};
}

新节点选择红色，是为了减少对黑高的扰动。黑高指从某个节点到所有叶端点路径上的黑色节点数量。插入红节点时，所有路径的黑高先保持不变；如果父节点是黑色，插入直接完成；如果父节点也是红色，就违反“红节点的孩子为黑色”这条性质，需要修复。

贯穿序列插入 10, 5, 15 时，根 10 最终为黑色，5 和 15 可以保持红色。继续插入 7 时，7 的父节点 5 是红色，叔叔 15 也是红色，此时用变色把 5 和 15 改黑，把祖父 10 改红，最后再把根改黑。插入 6 时，冲突会落入旋转分支，因为它形成了局部折线形状。

insert 的复杂度来自搜索路径和修复路径。红黑树高度受颜色性质约束，搜索、接入和修复都沿祖先链移动，因此复杂度是对数级。std::map::lower_bound 这类接口也承诺对数复杂度，可参考 cppreference 的 map::lower_bound 页面 对返回语义和复杂度的描述。

53.5 insert_fixup

insert_fixup 只修复一个问题：新红节点接入后，父节点也为红色。它循环向上处理，直到父节点为黑色，或者冲突被推到根节点。修复动作只有两类：叔叔为红色时变色并上移检查点；叔叔为黑色时通过一次或两次旋转把局部形状调整成可变色的直线。

void insert_fixup(base* z) noexcept {
    while (z != root() && z->parent->color == mini::rb_color::red) {
        base* parent = z->parent;
        base* grand = parent->parent;

        if (parent == grand->left) {
            base* uncle = grand->right;
            if (uncle->color == mini::rb_color::red) {
                parent->color = mini::rb_color::black;
                uncle->color = mini::rb_color::black;
                grand->color = mini::rb_color::red;
                z = grand;
            } else {
                if (z == parent->right) {
                    z = parent;
                    rotate_left(z);
                    parent = z->parent;
                    grand = parent->parent;
                }
                parent->color = mini::rb_color::black;
                grand->color = mini::rb_color::red;
                rotate_right(grand);
            }
        } else {
            base* uncle = grand->left;
            if (uncle->color == mini::rb_color::red) {
                parent->color = mini::rb_color::black;
                uncle->color = mini::rb_color::black;
                grand->color = mini::rb_color::red;
                z = grand;
            } else {
                if (z == parent->left) {
                    z = parent;
                    rotate_right(z);
                    parent = z->parent;
                    grand = parent->parent;
                }
                parent->color = mini::rb_color::black;
                grand->color = mini::rb_color::red;
                rotate_left(grand);
            }
        }
    }

    root()->color = mini::rb_color::black;
}

这段代码依赖 header 作为黑色叶端点。uncle 可能是 header，此时它的颜色是黑色，可以自然进入旋转分支。使用 header 后，修复代码中的空指针分支减少，但所有叶端点都必须能安全读取颜色。

insert_fixup 的核心判断是“红色叔叔变色，黑色叔叔旋转”。红色叔叔说明祖父的两侧红孩子同时存在，局部黑高可以通过把父与叔改黑、祖父改红来恢复；新的红色祖父可能继续和它的父节点冲突，所以检查点上移。黑色叔叔说明另一侧没有可一起变色的红节点，需要通过旋转把红色父子关系移到祖父位置，再用变色恢复性质。

贯穿序列插入 6 时，局部关系是 5 -> 7 -> 6。6 是父节点 7 的左孩子，父节点 7 是祖父 5 的右孩子，形成右左折线。修复先对 7 右旋，把折线变成 5 -> 6 -> 7 的直线，再对 5 左旋，让 6 到达局部根位置。最后 6 变黑，5 变红，局部红色冲突消失。

insert_fixup 不改变 key 顺序，它只改变颜色和局部链接。阅读 STL 源码时，看到插入修复函数内大量左右镜像分支，应按同一套问题压缩理解：父节点在祖父哪一侧，叔叔是什么颜色，当前节点与父节点是直线还是折线，最终旋转围绕哪个祖父节点提交。

53.6 erase

erase 的难点来自黑色节点删除。删除红色叶节点不会改变任何路径的黑高；删除黑色节点会让经过该位置的路径少一个黑节点，修复函数必须把这份黑高缺口沿树向上移动、吸收或通过旋转重新分配。

删除分成两个动作：先按二叉搜索树规则确定实际移出树结构的节点，再按被移出节点的原颜色决定是否修复。目标节点 z 有零个或一个真实孩子时，直接用孩子替换它；目标节点有两个真实孩子时，选择中序后继 y，把 y 的 key/value 位置移到 z 的位置，并把 y 原位置的单孩子接上去。Mini 实现通常直接移动节点链接，正式容器还要保留 iterator 和引用语义。

void transplant(base* old_node, base* replacement) noexcept {
    base* parent = old_node->parent;

    if (old_node == root()) {
        root_ref() = replacement;
    } else if (old_node == parent->left) {
        parent->left = replacement;
    } else {
        parent->right = replacement;
    }

    if (replacement != &header_) {
        replacement->parent = parent;
    }
}

base* minimum(base* x) const noexcept {
    while (x->left != &header_) {
        x = x->left;
    }
    return x;
}

transplant 只替换父子链接，它不维护颜色，也不维护 leftmost / rightmost。把责任拆开后，erase 主体可以清楚记录三个对象：用户要删的 z，实际移出原位置的 y，顶上来的孩子 x。修复函数关心的是 y 的原颜色、x 当前所在位置和 x_parent。当 x 是 header 时，header 的 parent 仍然保存 root，修复所需的父节点必须通过单独参数传入。

void erase_node(base* z) {
    base* y = z;
    base* x = &header_;
    base* x_parent = z->parent;
    mini::rb_color y_original_color = y->color;

    if (z->left == &header_) {
        x = z->right;
        x_parent = z->parent;
        transplant(z, z->right);
    } else if (z->right == &header_) {
        x = z->left;
        x_parent = z->parent;
        transplant(z, z->left);
    } else {
        y = minimum(z->right);
        y_original_color = y->color;
        x = y->right;

        if (y->parent == z) {
            x_parent = y;
        } else {
            x_parent = y->parent;
            transplant(y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }

        transplant(z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }

    if (header_.left == z) {
        header_.left = (z->right == &header_) ? z->parent : minimum(z->right);
    }
    if (header_.right == z) {
        header_.right = (z->left == &header_) ? z->parent : maximum(z->left);
    }

    if (y_original_color == mini::rb_color::black && root() != &header_) {
        erase_fixup(x, x_parent);
    }

    delete as_node(z);
    --size_;
    if (size_ == 0) {
        reset_header();
    }
}

上面代码为了突出删除主线，假定 maximum 与 minimum 对称实现，并使用 header 作为叶端点。实际工程实现还要处理 allocator、异常规范、const iterator 重载和删除范围。删除修复阶段不应比较 key，也不应构造或析构元素；它只处理颜色和链接。erase_fixup(x, x_parent) 使用显式父节点参数，是为了让 header 既能继续表达 end()，又能作为叶端点参与颜色判断。

erase_fixup 的四类局部形状可按兄弟节点分类。x 表示承载黑高缺口的位置，sibling 表示它的兄弟。兄弟为红色时，先旋转把红兄弟变成黑父节点的外层形状；兄弟为黑且两个孩子都黑时，兄弟改红，缺口上移到父节点；兄弟为黑且近侧孩子红时，先小旋转转成远侧孩子红；兄弟为黑且远侧孩子红时，旋转父节点并重新着色，缺口被吸收。

std::map::erase 的接口现象是被删除元素的引用和迭代器失效，其它元素的引用和迭代器不受影响；这个现象可参考 cppreference 的 map::erase 页面。红黑树能支撑这个现象，是因为 erase 只重连节点指针并销毁目标节点，保留节点对象的地址稳定性。旋转会改变节点之间的父子关系，但不会移动节点内部的 key/value 对象。

删除的工程判断顺序应固定。先确认被删节点是否存在；再确认实际移出原位置的节点是谁；再记录它的原颜色；再确认替代孩子 x 和它的 parent；再维护 header 端点；最后在原颜色为黑时执行修复。很多删除 bug 来自 x 是 header 时父节点信息丢失，因为修复函数仍然需要通过 x_parent 找兄弟节点。

53.7 iterator

红黑树 iterator 的核心是中序后继和中序前驱。节点式 ordered container 的迭代顺序由 key 顺序决定，iterator 只保存当前节点指针；++it 找下一个 key，--it 找上一个 key。header 哨兵负责表达 past-the-end 位置。

static base* successor(base* x, base* header) noexcept {
    if (x->right != header) {
        x = x->right;
        while (x->left != header) {
            x = x->left;
        }
        return x;
    }

    base* y = x->parent;
    while (y != header && x == y->right) {
        x = y;
        y = y->parent;
    }
    return y;
}

static base* predecessor(base* x, base* header) noexcept {
    if (x == header) {
        return header->right;
    }

    if (x->left != header) {
        x = x->left;
        while (x->right != header) {
            x = x->right;
        }
        return x;
    }

    base* y = x->parent;
    while (y != header && x == y->left) {
        x = y;
        y = y->parent;
    }
    return y;
}

successor 的判断顺序来自二叉搜索树顺序。当前节点有右子树时，下一个节点是右子树中的最小节点；当前节点没有右子树时，沿 parent 向上，找到第一个把当前路径放在左侧的祖先。predecessor 对称处理左子树和右侧祖先。--end() 是特殊入口，它直接返回 header 记录的最大节点。

class iterator {
    base* current_ = nullptr;
    base* header_ = nullptr;

public:
    using difference_type = std::ptrdiff_t;
    using value_type = std::pair<const Key, Value>;
    using iterator_category = std::bidirectional_iterator_tag;

    iterator& operator++() noexcept {
        current_ = successor(current_, header_);
        return *this;
    }

    iterator& operator--() noexcept {
        current_ = predecessor(current_, header_);
        return *this;
    }

    bool operator==(const iterator& other) const noexcept {
        return current_ == other.current_;
    }
};

这个 iterator 是 bidirectional iterator，因为它能向前和向后移动一步，但无法常数时间跳过任意距离。它的复杂度按单次移动看可能沿祖先链走多步，按完整遍历看每条边只被有限次经过，因此从 begin() 到 end() 的总成本是线性的。

iterator 稳定性来自节点地址稳定。插入新节点只添加一个节点并做旋转，已有节点对象地址不变；删除一个节点会销毁该节点，指向它的 iterator 失效，指向其它节点的 iterator 仍然能通过 parent / child 链找到后继或前驱。这个结论依赖 erase 结束后整棵树的 parent 链和 header 端点已经修复完成。

53.8 lower_bound

lower_bound(key) 返回第一个不小于 key 的位置。对二叉搜索树来说，搜索过程中每次遇到一个不小于目标的节点，它都可能是答案；随后向左继续找更小但仍合格的候选。遇到小于目标的节点时，当前节点及其左子树都无法成为答案，搜索转向右子树。

base* lower_bound_node(const Key& key) const {
    base* current = const_cast<base*>(root());
    base* candidate = const_cast<base*>(&header_);

    while (current != &header_) {
        const node* current_node = static_cast<const node*>(current);
        if (!comp_(current_node->key, key)) {
            candidate = current;
            current = current->left;
        } else {
            current = current->right;
        }
    }

    return candidate;
}

这里使用 !comp_(current_key, key) 表达“current_key 不小于 key”。在严格弱序比较器下，它覆盖等价和大于两种情况。candidate 初始为 header，表示还没有找到合格节点；如果搜索结束仍为 header，返回值就是 end()。

贯穿序列插入 10, 5, 15, 7, 6 后查询 lower_bound(8)。搜索从 root 出发，遇到小于 8 的节点就右转，遇到不小于 8 的节点就记录候选并左转。最终候选会停在 10，因为 7 和 6 都小于 8，10 是第一个不小于 8 的节点。

lower_bound 的正确性依赖两条前提。第一，树满足二叉搜索树顺序，任意节点左侧都小于该节点，右侧都大于该节点。第二，比较器在树生命周期内保持同一套顺序关系；如果 key 被外部修改，或 comparator 的判断依赖可变外部状态，树中已有节点的位置就可能和当前比较结果失配。

这个接口的工程判断顺序很短：先确认 comparator 是否形成稳定严格弱序；再确认树链接是否满足中序有序；再确认 candidate 在每次左转前被更新；最后确认没有候选时返回 header。阅读 std::map / std::set 实现时，看到 lower_bound 通常就是这个候选节点搜索模型，差异主要在类型封装、const 重载、透明比较和 debug iterator。

最小自检任务

下面的代码片段来自本章的 mini red-black tree 思路。假设 header 作为黑色叶端点，空孩子都指向 header，comp_ 是稳定严格弱序比较器。

mini_rb_tree<int, int> tree;
tree.insert_unique(10, 100);
tree.insert_unique(5, 50);
tree.insert_unique(15, 150);
tree.insert_unique(7, 70);
tree.insert_unique(6, 60);

auto first = tree.lower_bound_node(8);
tree.erase_node(tree.lower_bound_node(5));
auto second = tree.lower_bound_node(8);

判断以下问题：插入 6 时为什么可能需要先局部旋转再围绕祖父旋转？lower_bound(8) 为什么会返回 key 为 10 的节点？删除 key 为 5 的节点后，为什么指向 key 为 10 的 iterator 仍然可以保持有效？

答案要点

插入 6 后，新节点、父节点和祖父节点可能形成折线结构，例如父节点在祖父右侧，而新节点在父节点左侧。insert_fixup 在黑色叔叔分支中先用一次局部旋转把折线转成直线，再围绕祖父旋转并重新着色。这样可以同时恢复红色父子约束和局部黑高。

lower_bound(8) 的候选搜索规则是：当前 key 不小于 8 时记录候选并左转，当前 key 小于 8 时右转。6、7 都小于 8，无法成为答案；10 不小于 8，并且没有更小的合格节点，所以返回 key 为 10 的节点。如果没有任何合格节点，candidate 会保持 header，返回 end()。

删除 key 为 5 的节点只销毁被删除节点本身。红黑树删除修复会重连父子指针、调整颜色并可能旋转，但不会搬移 key 为 10 的节点对象。节点地址稳定时，指向 10 的 iterator 仍然指向同一个节点；前提是 erase 结束后 parent 链和 header 端点已经维护正确。

本章知识点总结

• 节点状态：red-black tree 节点由 key/value、parent、left、right 和 color 共同表达有序位置与平衡状态。
• header 哨兵：header 统一表达 root、begin、最大节点和 end()，空树时 root、leftmost、rightmost 都回到 header。
• 所有权边界：容器拥有节点内存和元素生命周期，节点指针只表达树结构链接。
• 左旋路径：左旋让右孩子顶替当前节点，并把右孩子的左子树转成当前节点的右子树。
• 右旋路径：右旋让左孩子顶替当前节点，并把左孩子的右子树转成当前节点的左子树。
• 旋转性质：旋转保持中序顺序，只改变局部父子关系和可能的 root 指针。
• 插入阶段：insert 先按二叉搜索树规则定位位置，再构造红色新节点并接入树。
• 插入修复：红色叔叔使用变色并上移检查点，黑色叔叔使用旋转和变色恢复红色父子约束。
• 删除阶段：erase 先确定实际移出树结构的节点，再按该节点原颜色决定是否修复黑高。
• 删除修复：erase_fixup 围绕兄弟节点颜色和兄弟孩子颜色处理黑高缺口。
• 迭代器移动：tree iterator 通过 successor 和 predecessor 实现中序遍历，header 表达 past-the-end 位置。
• 迭代器稳定：插入和旋转保留已有节点对象地址，删除只使被删除节点对应的 iterator 失效。
• 候选搜索：lower_bound 在搜索中记录不小于目标 key 的候选节点，并继续向左收缩答案范围。
• 判断顺序：检查 mini red-black tree 时，应依次验证顺序、链接、header、颜色黑高、iterator 和复杂度边界。