用C++实现红黑树的算法代码

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

#include <iostream>
using namespace std;

enum Color { RED, BLACK };

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

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

class RedBlackTree {
private:
    Node *root;

protected:
    void rotateLeft(Node *&);
    void rotateRight(Node *&);
    void fixViolation(Node *&);
    void inorderBST(Node *);

public:
    RedBlackTree() { root = NULL; }
    void insert(const int &n);
    void inorder();
};

void RedBlackTree::rotateLeft(Node *&ptr) {
    Node *newPtr = ptr->right;
    ptr->right = newPtr->left;

    if (ptr->right != NULL)
        ptr->right->parent = ptr;

    newPtr->parent = ptr->parent;

    if (ptr->parent == NULL)
        root = newPtr;

    else if (ptr == ptr->parent->left)
        ptr->parent->left = newPtr;

    else
        ptr->parent->right = newPtr;

    newPtr->left = ptr;
    ptr->parent = newPtr;
}

void RedBlackTree::rotateRight(Node *&ptr) {
    Node *newPtr = ptr->left;
    ptr->left = newPtr->right;

    if (ptr->left != NULL)
        ptr->left->parent = ptr;

    newPtr->parent = ptr->parent;

    if (ptr->parent == NULL)
        root = newPtr;

    else if (ptr == ptr->parent->left)
        ptr->parent->left = newPtr;

    else
        ptr->parent->right = newPtr;

    newPtr->right = ptr;
    ptr->parent = newPtr;
}

void RedBlackTree::fixViolation(Node *&ptr) {
    Node *parentPtr = NULL;
    Node *grandParentPtr = NULL;

    while ((ptr != root) && (ptr->color != BLACK) &&
           (ptr->parent->color == RED)) {

        parentPtr = ptr->parent;
        grandParentPtr = ptr->parent->parent;

        if (parentPtr == grandParentPtr->left) {

            Node *unclePtr = grandParentPtr->right;

            if (unclePtr != NULL && unclePtr->color == RED) {
                grandParentPtr->color = RED;
                parentPtr->color = BLACK;
                unclePtr->color = BLACK;
                ptr = grandParentPtr;
            } else {
                if (ptr == parentPtr->right) {
                    rotateLeft(parentPtr);
                    ptr = parentPtr;
                    parentPtr = ptr->parent;
                }

                rotateRight(grandParentPtr);
                swap(parentPtr->color, grandParentPtr->color);
                ptr = parentPtr;
            }
        } else {
            Node *unclePtr = grandParentPtr->left;

            if ((unclePtr != NULL) && (unclePtr->color == RED)) {
                grandParentPtr->color = RED;
                parentPtr->color = BLACK;
                unclePtr->color = BLACK;
                ptr = grandParentPtr;
            } else {
                if (ptr == parentPtr->left) {
                    rotateRight(parentPtr);
                    ptr = parentPtr;
                    parentPtr = ptr->parent;
                }

                rotateLeft(grandParentPtr);
                swap(parentPtr->color, grandParentPtr->color);
                ptr = parentPtr;
            }
        }
    }

    root->color = BLACK;
}

void RedBlackTree::insert(const int &data) {
    Node *ptr = new Node(data);
    root = ptr;
    fixViolation(ptr);
}

void RedBlackTree::inorderBST(Node *ptr) {
    if (ptr == NULL)
        return;

    inorderBST(ptr->left);
    cout << ptr->data << " ";
    inorderBST(ptr->right);
}

void RedBlackTree::inorder() { inorderBST(root); }

int main() {
    RedBlackTree tree;

    tree.insert(7);
    tree.insert(6);
    tree.insert(5);
    tree.insert(4);
    tree.insert(3);
    tree.insert(2);
    tree.insert(1);

    cout << "Inorder Traversal of Created Tree\n";
    tree.inorder();

    return 0;
}

上面的代码实现了红黑树的插入、旋转和修复违规的操作。其中，`rotateLeft`和`rotateRight`函数实现了左旋和右旋操作，`fixViolation`函数用于修复插入数据后可能会违反红黑树规则的情况，`insert`函数用于向红黑树中插入一个节点，`inorderBST`函数实现了中序遍历。