C++如何实现一个红黑树_C++数据结构与红黑树实现-C++-PHP中文网

C++如何实现一个红黑树_C++数据结构与红黑树实现

穿越時空

发布： 2025-11-24 20:31:02

原创

678人浏览过

红黑树通过颜色规则和旋转维持平衡，确保操作时间复杂度为O(log n)。其节点含颜色、值及指针，新节点默认红色。左旋右旋调整结构，插入后按叔叔颜色等分情况修复，最终根节点染黑以满足性质。

c++如何实现一个红黑树_c++数据结构与红黑树实现

红黑树是一种自平衡的二叉查找树，它通过特定的颜色规则和旋转操作保证树的高度接近 log(n)，从而确保插入、删除和查找操作的时间复杂度为 O(log n)。在 C++ 中实现红黑树，需要理解其基本性质，并通过指针操作维护这些性质。

红黑树的五条基本性质

为了保持平衡，红黑树中的每个节点都带有颜色（红色或黑色），并满足以下条件：

每个节点是红色或黑色
根节点是黑色
所有叶子（NULL 节点）视为黑色
如果一个节点是红色，则它的两个子节点都是黑色（即不能有两个连续的红色节点）
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑高一致）

节点结构设计

定义一个红黑树节点类，包含值、颜色、左右子节点和父节点指针。使用枚举表示颜色更清晰。

enum Color { RED, BLACK };
<p>struct Node {
int data;
Color color;
Node <em>left, </em>right, *parent;</p><pre class='brush:php;toolbar:false;'>Node(int data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}

登录后复制

};

立即学习“C++免费学习笔记（深入）”；

注意：新插入节点默认为红色，这样可以最小化对黑高性质的影响。

左旋与右旋操作

旋转是维持红黑树平衡的核心操作。左旋用于处理右倾情况，右旋处理左倾。

左旋示例：

畅图

AI可视化工具

147

查看详情

void leftRotate(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    if (y->left != nullptr)
        y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == nullptr)
        root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}

登录后复制

右旋类似，交换 left 和 right 的角色即可。

插入操作与修复

插入过程分为两步：按二叉搜索树方式插入，然后根据红黑性质进行修复。

修复主要处理三种情况：

叔叔是红色：变色并上移问题节点
叔叔是黑色且当前节点是右孩子：左旋调整形态
叔叔是黑色且当前节点是左孩子：右旋并重新着色

修复函数大致如下：

void insertFix(Node* k) {
    while (k != root && k->parent->color == RED) {
        if (k->parent == k->parent->parent->left) {
            Node* u = k->parent->parent->right;
            if (u != nullptr && u->color == RED) {
                k->parent->color = BLACK;
                u->color = BLACK;
                k->parent->parent->color = RED;
                k = k->parent->parent;
            } else {
                if (k == k->parent->right) {
                    k = k->parent;
                    leftRotate(k);
                }
                k->parent->color = BLACK;
                k->parent->parent->color = RED;
                rightRotate(k->parent->parent);
            }
        } else {
            // 对称情况
        }
    }
    root->color = BLACK;
}

登录后复制