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

C++怎么实现一个红黑树_C++数据结构与红黑树实现

尼克

发布： 2025-11-16 16:37:02

原创

538人浏览过

红黑树通过颜色属性和旋转操作维持平衡，确保插入删除后仍满足二叉搜索树性质且黑高一致，最长路径不超过最短路径两倍，从而保证O(log n)时间复杂度。

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

红黑树是一种自平衡的二叉查找树，通过为每个节点添加颜色属性（红色或黑色）并遵循特定规则，保证树在插入和删除操作后依然大致保持平衡。C++中实现红黑树需要理解其结构定义、旋转操作、插入与删除的修复逻辑。

红黑树的性质

红黑树满足以下五条性质：

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

这些性质确保了最长路径不超过最短路径的两倍，从而维持O(log n)的操作复杂度。

节点结构定义

定义一个红黑树节点类，包含值、颜色、左右子节点和父节点指针：

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

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) {}

登录后复制

};

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

旋转操作：维持平衡的基础

旋转是调整树结构而不破坏二叉搜索树性质的关键操作。红黑树需要左旋和右旋：

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;
}
<p>void rightRotate(Node<em> y) {
Node</em> x = y->left;
y->left = x->right;
if (x->right != nullptr)
x->right->parent = y;
x->parent = y->parent;
if (y->parent == nullptr)
root = x;
else if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
x->right = y;
y->parent = x;
}</p>

登录后复制

左旋将右孩子提升，右旋将左孩子提升，用于后续插入修复中调整结构。

插入操作与修复

插入按BST规则找到位置后插入红色节点，然后根据情况修复红黑性质：

快写红薯通AI

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

查看详情

void insert(int value) {
    Node* node = new Node(value);
    root = bstInsert(root, node);  // 标准BST插入
    fixInsert(node);               // 修复红黑性质
}

登录后复制

修复分为几种情况：

父节点为黑色：无需处理
父节点为红色：检查叔节点颜色
叔节点为红色：变色并上移问题到祖父
叔节点为黑色：通过旋转+变色解决

具体修复代码会根据父节点是左孩子还是右孩子对称处理，核心是重新着色和旋转以恢复性质。

删除操作与修复

删除比插入更复杂。先执行标准BST删除，若删除的是黑色节点，可能导致黑高不一致，需修复。

修复从替代节点开始，分情况处理兄弟节点的颜色和结构，通过变色、旋转逐步向上修复。

由于篇幅较长，完整删除修复逻辑通常涉及多个case判断，建议参考经典算法教材如《算法导论》中的RB-DELETE-FIXUP过程实现。

基本操作接口设计

可封装成类提供清晰接口：

class RedBlackTree {
private:
    Node* root;
    void leftRotate(Node*);
    void rightRotate(Node*);
    void fixInsert(Node*);
    void fixDelete(Node*);
    Node* bstInsert(Node*, Node*);
public:
    RedBlackTree() : root(nullptr) {}
    void insert(int value);
    void remove(int value);
    Node* search(int value);
    void inorder();
};

登录后复制

配合中序遍历可验证是否仍为有效BST，辅助调试。

基本上就这些。红黑树实现关键是理解各种插入/删除场景下的修复策略，结合旋转与着色操作逐步恢复平衡。虽然代码量较大，但逻辑清晰，适合深入学习自平衡树的设计思想。

以上就是C++怎么实现一个红黑树_C++数据结构与红黑树实现的详细内容，更多请关注php中文网其它相关文章！