c++紅黑樹算法怎么實(shí)現(xiàn)

紅黑樹是一種自平衡的二叉查找樹，可以在O(log n)的時(shí)間復(fù)雜度內(nèi)進(jìn)行插入、刪除和查找操作。以下是一個(gè)簡單的C++實(shí)現(xiàn)紅黑樹的算法：

#include <iostream>
using namespace std;

enum Color { RED, BLACK };

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

    Node(int data) : data(data) {
        parent = left = right = NULL;
        color = RED;
    }
};

class RedBlackTree {
private:
    Node *root;

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

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

    void fixViolation(Node *x) {
        Node *parent = NULL;
        Node *grandparent = NULL;

        while (x != root && x->color == RED && x->parent->color == RED) {
            parent = x->parent;
            grandparent = x->parent->parent;

            if (parent == grandparent->left) {
                Node *uncle = grandparent->right;
                if (uncle != NULL && uncle->color == RED) {
                    grandparent->color = RED;
                    parent->color = BLACK;
                    uncle->color = BLACK;
                    x = grandparent;
                } else {
                    if (x == parent->right) {
                        rotateLeft(parent);
                        x = parent;
                        parent = x->parent;
                    }
                    rotateRight(grandparent);
                    swap(parent->color, grandparent->color);
                    x = parent;
                }
            } else {
                Node *uncle = grandparent->left;
                if (uncle != NULL && uncle->color == RED) {
                    grandparent->color = RED;
                    parent->color = BLACK;
                    uncle->color = BLACK;
                    x = grandparent;
                } else {
                    if (x == parent->left) {
                        rotateRight(parent);
                        x = parent;
                        parent = x->parent;
                    }
                    rotateLeft(grandparent);
                    swap(parent->color, grandparent->color);
                    x = parent;
                }
            }
        }
        root->color = BLACK;
    }

    void insertHelper(Node *node) {
        Node *cur = root;
        Node *parent = NULL;

        while (cur != NULL) {
            parent = cur;
            if (node->data < cur->data) {
                cur = cur->left;
            } else {
                cur = cur->right;
            }
        }

        node->parent = parent;
        if (parent == NULL) {
            root = node;
        } else if (node->data < parent->data) {
            parent->left = node;
        } else {
            parent->right = node;
        }

        fixViolation(node);
    }

    void inorderHelper(Node *node) {
        if (node == NULL) {
            return;
        }

        inorderHelper(node->left);
        cout << node->data << " ";
        inorderHelper(node->right);
    }

public:
    RedBlackTree() : root(NULL) {}

    void insert(int data) {
        Node *node = new Node(data);
        insertHelper(node);
    }

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

int main() {
    RedBlackTree tree;

    tree.insert(7);
    tree.insert(3);
    tree.insert(18);
    tree.insert(10);
    tree.insert(22);
    tree.insert(8);
    tree.insert(11);
    tree.insert(26);

    cout << "Inorder traversal of the constructed Red-Black tree is: ";
    tree.inorder();

    return 0;
}