c++怎么实现一个红黑树_c++平衡二叉搜索树插入与旋转算法-C++-PHP中文网

c++怎么实现一个红黑树_c++平衡二叉搜索树插入与旋转算法

穿越時空

发布： 2025-11-11 10:13:02

原创

192人浏览过

红黑树通过着色规则和旋转保持平衡，插入后修复以确保根黑、无连续红、黑高一致，C++实现包含左旋右旋与insertFixup，最终中序遍历验证有序性。

c++怎么实现一个红黑树_c++平衡二叉搜索树插入与旋转算法

红黑树是一种自平衡的二叉搜索树（BST），它通过为每个节点着色（红色或黑色）并遵循特定规则来保持树的近似平衡，从而保证查找、插入和删除操作的时间复杂度为 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++免费学习笔记（深入）”；

左旋与右旋操作

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

void leftRotate(Node* &root, Node* x) {
    Node* y = x->right;
    x->right = y->left;
    if (y->left != nullptr)
        y->left->parent = x;
    y->parent = x->parent;
<pre class='brush:php;toolbar:false;'>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;

登录后复制

}

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

void rightRotate(Node &root, Node y) { Node* 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;

登录后复制

}

插入与修复操作

插入新节点后，可能破坏红黑性质，需进行修复。新节点默认为红色，然后根据父节点颜色和叔节点状态分情况处理。

void insertFixup(Node* &root, Node* z) {
    while (z != root && z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            Node* uncle = z->parent->parent->right;
            if (uncle != nullptr && uncle->color == RED) {
                // 情况1：叔节点为红
                z->parent->color = BLACK;
                uncle->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                // 情况2：叔节点为黑且当前节点为右孩子
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(root, z);
                }
                // 情况3：叔节点为黑且当前节点为左孩子
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(root, z->parent->parent);
            }
        } else {
            Node* uncle = z->parent->parent->left;
            if (uncle != nullptr && uncle->color == RED) {
                z->parent->color = BLACK;
                uncle->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rightRotate(root, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                leftRotate(root, z->parent->parent);
            }
        }
    }
    root->color = BLACK; // 根节点始终为黑
}
<p>void insert(Node<em> &root, int data) {
Node</em> z = new Node(data);
Node<em> y = nullptr;
Node</em> x = root;</p><pre class='brush:php;toolbar:false;'>while (x != nullptr) {
    y = x;
    if (z->data < x->data)
        x = x->left;
    else
        x = x->right;
}

z->parent = y;
if (y == nullptr)
    root = z;
else if (z->data < y->data)
    y->left = z;
else
    y->right = z;

insertFixup(root, z);

登录后复制

}

完整使用示例

以下是一个简单的测试主函数：

#include <iostream>
using namespace std;
<p>// 上述所有代码放在这里</p><p>void inorder(Node* root) {
if (root != nullptr) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}</p><p>int main() {
Node* root = nullptr;
insert(root, 10);
insert(root, 20);
insert(root, 30);
insert(root, 15);
insert(root, 25);</p><pre class='brush:php;toolbar:false;'>cout << "Inorder traversal: ";
inorder(root);
cout << endl;

return 0;

登录后复制

}

基本上就这些。这个实现涵盖了红黑树插入和旋转的核心机制。虽然没有包含删除操作（更复杂），但已足够理解其平衡原理。实际工程中可考虑使用 std::set 或 std::map，它们底层正是基于红黑树实现的。

以上就是c++++怎么实现一个红黑树_c++平衡二叉搜索树插入与旋转算法的详细内容，更多请关注php中文网其它相关文章！