c++怎么实现一个红黑树_c++红黑树数据结构实现思路-C++-PHP中文网

c++怎么实现一个红黑树_c++红黑树数据结构实现思路

裘德小鎮的故事

发布： 2025-10-26 09:06:02

原创

929人浏览过

红黑树通过颜色标记和旋转维持平衡，保证操作时间复杂度O(log n)。其性质包括：根黑、叶黑、红节点子节点为黑、黑高一致。插入后通过变色和左右旋修复，删除黑色节点后需调整兄弟子树恢复黑高，核心是五条性质的维护。

c++怎么实现一个红黑树_c++红黑树数据结构实现思路

红黑树是一种自平衡的二叉查找树，通过颜色标记和旋转操作维持树的平衡，保证插入、删除、查找操作的时间复杂度为 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 value) : data(value), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}

登录后复制

};

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

使用枚举表示颜色，初始化默认为红色（插入时临时设为红，再根据规则调整）。

基本操作：插入与修复

插入操作沿用 BST 插入方式，新节点初始为红色，然后根据红黑性质进行修复：

快写红薯通AI

快写红薯通AI，专为小红书而生的AI写作工具

查看详情

如果父节点是黑色，无需处理
如果父节点是红色，检查叔叔节点颜色
通过变色和旋转（左旋/右旋）恢复平衡

主要分三种情况处理：

void fixInsert(Node* node) {
    while (node != root && node->parent->color == RED) {
        if (node->parent == node->parent->parent->left) {
            Node* uncle = node->parent->parent->right;
            if (uncle && uncle->color == RED) {
                // 情况1：叔叔为红，变色
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                // 情况2：叔叔为黑，LR 或 LL 型
                if (node == node->parent->right) {
                    node = node->parent;
                    leftRotate(node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rightRotate(node->parent->parent);
            }
        } else {
            // 对称处理右子树
            ...
        }
    }
    root->color = BLACK; // 根始终为黑
}

登录后复制

旋转操作实现

旋转用于调整树形结构，保持 BST 性质同时恢复红黑约束：

左旋：以 x 为轴，x 的右孩子 y 上提，y 的左子树变为 x 的右子树
右旋：以 y 为轴，y 的左孩子 x 上提，x 的右子树变为 y 的左子树

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

登录后复制