红黑树c++-实现

红黑树是一种自平衡的二叉查找树，具有以下特点：

1. 每个节点要么是红色，要么是黑色

2. 根节点是黑色的

3. 每个叶子节点（NIL节点，空节点）是黑色的

4. 如果一个节点是红色的，则它的两个子节点都是黑色的（反之不一定成立）

5. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点

基于以上特点，我们可以实现红黑树的插入、删除、查找等操作。

以下是红黑树的C++实现代码：

#include <iostream>

using namespace std;

enum Color { RED, BLACK };

struct Node {
    int data;
    Color color;
    Node *left, *right, *parent;

    Node(int data) {
        this->data = data;
        color = RED;
        left = right = parent = nullptr;
    }
};

class RedBlackTree {
private:
    Node *root;

    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;
    }

    void rightRotate(Node *&x) {
        Node *y = x->left;
        x->left = y->right;
        if (y->right != nullptr)
            y->right->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->right = x;
        x->parent = y;
    }

    void fixInsert(Node *&x) {
        while (x != root && x->parent->color == RED) {
            if (x->parent == x->parent->parent->left) {
                Node *y = x->parent->parent->right;
                if (y != nullptr && y->color == RED) {
                    x->parent->color = BLACK;
                    y->color = BLACK;
                    x->parent->parent->color = RED;
                    x = x->parent->parent;
                } else {
                    if (x == x->parent->right) {
                        x = x->parent;
                        leftRotate(x);
                    }
                    x->parent->color = BLACK;
                    x->parent->parent->color = RED;
                    rightRotate(x->parent->parent);
                }
            } else {
                Node *y = x->parent->parent->left;
                if (y != nullptr && y->color == RED) {
                    x->parent->color = BLACK;
                    y->color = BLACK;
                    x->parent->parent->color = RED;
                    x = x->parent->parent;
                } else {
                    if (x == x->parent->left) {
                        x = x->parent;
                        rightRotate(x);
                    }
                    x->parent->color = BLACK;
                    x->parent->parent->color = RED;
                    leftRotate(x->parent->parent);
                }
            }
        }
        root->color = BLACK;
    }

    Node *BSTInsert(Node *&root, Node *x) {
        if (root == nullptr)
            return x;
        if (x->data < root->data) {
            root->left = BSTInsert(root->left, x);
            root->left->parent = root;
        } else if (x->data > root->data) {
            root->right = BSTInsert(root->right, x);
            root->right->parent = root;
        }
        return root;
    }

    void inorderHelper(Node *root) {
        if (root == nullptr)
            return;
        inorderHelper(root->left);
        cout << root->data << " ";
        inorderHelper(root->right);
    }

public:
    RedBlackTree() {
        root = nullptr;
    }

    void insert(int data) {
        Node *node = new Node(data);
        root = BSTInsert(root, node);
        fixInsert(node);
    }

    void inorder() {
        inorderHelper(root);
    }
};

int main() {
    RedBlackTree rbTree;
    rbTree.insert(7);
    rbTree.insert(3);
    rbTree.insert(18);
    rbTree.insert(10);
    rbTree.insert(22);
    rbTree.insert(8);
    rbTree.insert(11);
    rbTree.insert(26);
    rbTree.insert(2);
    rbTree.insert(6);
    rbTree.insert(13);
    cout << "Inorder traversal of the constructed Red-Black tree is: ";
    rbTree.inorder();
    return 0;
}

输出结果：

Inorder traversal of the constructed Red-Black tree is: 2 3 6 7 8 10 11 13 18 22 26

以上代码实现了红黑树的插入操作，并且通过中序遍历验证了树的正确性。在删除和查找操作中，需要根据红黑树的特点进行调整，具体实现可以参考其他的资料。