手写红黑树内核

手写红黑树内核

使用左倾红黑树实现旋转、变色、插入与删除，为 set/map 系列建立共享有序索引。

本系列代码使用 C++20 和 oc::handmade 命名空间，目标是解释实现机制、复杂度和工程边界，不是替代标准库。普通容器与缓存核心不内置互斥锁；这不代表 lock-free。

---

一、学习目标

• 理解红黑树五条性质
• 实现局部旋转与颜色修复
• 用黑高约束证明 O(log n)

---

二、前置条件

熟悉二叉搜索树、递归、unique_ptr 和比较器。

Linux/macOS：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j
ctest --test-dir build --output-on-failure

Windows PowerShell：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure

---

三、问题与设计选择

采用左倾红黑树表达 2-3 树：红链接向左，任何路径黑高相同。递归修改返回新的子树根，根节点最终染黑。

这里刻意保留一条边界：教学实现覆盖构造、复制移动、核心修改、查找和迭代契约，但不复刻标准库全部重载、ABI、constexpr、异构查找或节点句柄。

---

四、内存布局与核心不变量

根为黑色；空链接视为黑色；没有连续红节点；红链接左倾；任一节点到空叶子的黑节点数量相同。

每个修改操作都按“准备资源 → 构造新状态 → 提交连接或指针 → 清理旧状态”的顺序设计。提交点之前发生异常，应保持原对象可继续使用；无法提供强保证时，会在接口说明中明确基本保证。

---

五、核心实现

node* fix_up(node* h) noexcept {
    if (is_red(h->right) && !is_red(h->left)) h = rotate_left(h);
    if (is_red(h->left) && is_red(h->left->left)) h = rotate_right(h);
    if (is_red(h->left) && is_red(h->right)) flip_colors(h);
    return h;
}

上面先聚焦最容易写错的核心步骤；若本篇对应一个独立组件，下一节给出统一工程中的完整教学实现。代码没有放入 std 命名空间，避免未定义行为和名称冲突。

---

六、完整教学实现

下面是统一工程中经过 GCC、Clang、GoogleTest 和 Sanitizer 验证的完整组件。它依赖前序文章已经实现的公共类型以及头文件中的标准库 #include。

namespace oc::handmade {

template<class Key, class Mapped, class Compare = std::less<Key>>
class rb_tree {
    struct node {
        Key key;
        Mapped mapped;
        bool red{true};
        std::unique_ptr<node> left;
        std::unique_ptr<node> right;
        node(Key key_value, Mapped mapped_value)
            : key(std::move(key_value)), mapped(std::move(mapped_value)) {}
    };
    std::unique_ptr<node> root_;
    std::size_t size_{};
    Compare compare_{};

    static bool is_red(const std::unique_ptr<node>& value) noexcept {
        return value && value->red;
    }
    static std::unique_ptr<node> rotate_left(std::unique_ptr<node> h) {
        auto x = std::move(h->right);
        h->right = std::move(x->left);
        x->left = std::move(h);
        x->red = x->left->red;
        x->left->red = true;
        return x;
    }
    static std::unique_ptr<node> rotate_right(std::unique_ptr<node> h) {
        auto x = std::move(h->left);
        h->left = std::move(x->right);
        x->right = std::move(h);
        x->red = x->right->red;
        x->right->red = true;
        return x;
    }
    static void flip_colors(node* h) noexcept {
        h->red = !h->red;
        if (h->left) h->left->red = !h->left->red;
        if (h->right) h->right->red = !h->right->red;
    }
    static std::unique_ptr<node> fix_up(std::unique_ptr<node> h) {
        if (is_red(h->right) && !is_red(h->left)) h = rotate_left(std::move(h));
        if (is_red(h->left) && is_red(h->left->left)) h = rotate_right(std::move(h));
        if (is_red(h->left) && is_red(h->right)) flip_colors(h.get());
        return h;
    }
    static std::unique_ptr<node> move_red_left(std::unique_ptr<node> h) {
        flip_colors(h.get());
        if (h->right && is_red(h->right->left)) {
            h->right = rotate_right(std::move(h->right));
            h = rotate_left(std::move(h));
            flip_colors(h.get());
        }
        return h;
    }
    static std::unique_ptr<node> move_red_right(std::unique_ptr<node> h) {
        flip_colors(h.get());
        if (h->left && is_red(h->left->left)) {
            h = rotate_right(std::move(h));
            flip_colors(h.get());
        }
        return h;
    }
    std::unique_ptr<node> insert_impl(
        std::unique_ptr<node> h,
        Key key,
        Mapped mapped,
        node*& result,
        bool& inserted
    ) {
        if (!h) {
            inserted = true;
            ++size_;
            auto fresh = std::make_unique<node>(std::move(key), std::move(mapped));
            result = fresh.get();
            return fresh;
        }
        if (compare_(key, h->key)) {
            h->left = insert_impl(
                std::move(h->left), std::move(key), std::move(mapped), result, inserted);
        } else if (compare_(h->key, key)) {
            h->right = insert_impl(
                std::move(h->right), std::move(key), std::move(mapped), result, inserted);
        } else {
            result = h.get();
        }
        return fix_up(std::move(h));
    }
    static node* minimum(node* h) noexcept {
        while (h->left) h = h->left.get();
        return h;
    }
    static std::unique_ptr<node> erase_min(std::unique_ptr<node> h) {
        if (!h->left) return nullptr;
        if (!is_red(h->left) && !is_red(h->left->left))
            h = move_red_left(std::move(h));
        h->left = erase_min(std::move(h->left));
        return fix_up(std::move(h));
    }
    std::unique_ptr<node> erase_impl(std::unique_ptr<node> h, const Key& key) {
        if (compare_(key, h->key)) {
            if (h->left) {
                if (!is_red(h->left) && !is_red(h->left->left))
                    h = move_red_left(std::move(h));
                h->left = erase_impl(std::move(h->left), key);
            }
        } else {
            if (is_red(h->left)) h = rotate_right(std::move(h));
            const bool equal = !compare_(key, h->key) && !compare_(h->key, key);
            if (equal && !h->right) return nullptr;
            if (h->right) {
                if (!is_red(h->right) && !is_red(h->right->left))
                    h = move_red_right(std::move(h));
                const bool now_equal =
                    !compare_(key, h->key) && !compare_(h->key, key);
                if (now_equal) {
                    node* successor = minimum(h->right.get());
                    h->key = successor->key;
                    h->mapped = successor->mapped;
                    h->right = erase_min(std::move(h->right));
                } else {
                    h->right = erase_impl(std::move(h->right), key);
                }
            }
        }
        return fix_up(std::move(h));
    }
    template<class F>
    static void inorder_impl(const node* current, F& callback) {
        if (!current) return;
        inorder_impl(current->left.get(), callback);
        callback(current->key, current->mapped);
        inorder_impl(current->right.get(), callback);
    }
    static int validate_black_height(const node* current) {
        if (!current) return 1;
        if (current->right && current->right->red) return -1;
        if (current->red &&
            ((current->left && current->left->red) ||
             (current->right && current->right->red))) return -1;
        int left = validate_black_height(current->left.get());
        int right = validate_black_height(current->right.get());
        if (left < 0 || right < 0 || left != right) return -1;
        return left + (current->red ? 0 : 1);
    }

public:
    struct entry {
        const Key* key;
        Mapped* mapped;
    };
    std::pair<entry, bool> insert(Key key, Mapped mapped) {
        node* result = nullptr;
        bool inserted = false;
        root_ = insert_impl(
            std::move(root_), std::move(key), std::move(mapped), result, inserted);
        root_->red = false;
        return {{&result->key, &result->mapped}, inserted};
    }
    Mapped* find(const Key& key) {
        node* current = root_.get();
        while (current) {
            if (compare_(key, current->key)) current = current->left.get();
            else if (compare_(current->key, key)) current = current->right.get();
            else return &current->mapped;
        }
        return nullptr;
    }
    const Mapped* find(const Key& key) const {
        return const_cast<rb_tree*>(this)->find(key);
    }
    bool contains(const Key& key) const { return find(key) != nullptr; }
    bool erase(const Key& key) {
        if (!contains(key)) return false;
        if (!is_red(root_->left) && !is_red(root_->right)) root_->red = true;
        root_ = erase_impl(std::move(root_), key);
        if (root_) root_->red = false;
        --size_;
        return true;
    }
    std::size_t size() const noexcept { return size_; }
    bool empty() const noexcept { return size_ == 0; }
    template<class F>
    void inorder(F&& callback) const {
        inorder_impl(root_.get(), callback);
    }
    bool valid() const {
        return (!root_ || !root_->red) && validate_black_height(root_.get()) > 0;
    }
};

}  // namespace oc::handmade

生产级标准库还要处理完整 allocator 传播、全部重载、ABI、调试迭代器和平台特化；这里保留的是能够独立推导核心数据结构的教学边界。

---

七、使用示例与输出

预期输出或状态：

插入 7 3 9 1 5 后中序为 1 3 5 7 9，校验器报告根黑、无连续红节点且黑高一致。

示例必须在文章对应的测试目标中实际编译。涉及顺序的输出只依赖接口明确承诺的顺序；无序容器不会把某次桶顺序写成稳定结果。

---

八、复杂度与失效规则

操作	复杂度	说明
find/lower_bound	O(log n)	按比较器下降
insert	O(log n)	旋转和变色
erase	O(log n)	向下移动红链接
遍历	O(n)	中序有序

复杂度中的 O(1) 若标记为“平均”或“摊还”，不能在面试中省略限定词。任何重新分配、节点删除、rehash 或缓存淘汰都必须单独说明迭代器、引用与指针是否失效。

---

九、异常安全与资源管理

• 获取资源后立即交给 RAII 对象或明确记录已构造数量。
• 用户类型构造、复制、移动、比较器和哈希器都可能抛异常。
• 只有在所有后续步骤不会失败时才修改不可回滚的链接。
• 析构、释放和关闭路径不得抛异常。
• 并发包装通过回调在锁内访问，避免返回保护对象的裸引用。

---

十、常见错误

1. 旋转时漏掉颜色转移

旋转时漏掉颜色转移会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 只验证搜索树顺序而不验证黑高

只验证搜索树顺序而不验证黑高会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 删除前没有保证下降方向存在红链接

删除前没有保证下降方向存在红链接会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

---

十一、面试追问

1. 红黑树最长路径为何不超过最短路径两倍？
2. AVL 与红黑树如何取舍？
3. 为什么旋转不破坏中序顺序？

回答时先说数据结构不变量，再给复杂度，最后说明异常、迭代器或并发边界，通常比背诵结论更有说服力。

---

十二、练习与自测

1. 实现 invariant checker
2. 输出 Graphviz 结构
3. 统计随机插入时的旋转次数

自测标准：能够不看代码画出内存或节点关系，解释一次成功操作和一次失败回滚，并写出至少一个会击穿错误实现的测试。

---

十三、官方资料与延伸阅读

• C++20 工作草案 N4861
• C++ Core Guidelines

---

上一篇：手写 std::priority_queue ｜ 下一篇：手写 std::set