在C++中實現(xiàn)紅黑樹的基本結(jié)構(gòu)

紅黑樹是一種自平衡的二叉搜索樹，其基本結(jié)構(gòu)可以通過以下代碼實現(xiàn)：

#include <iostream>
using namespace std;

enum Color {RED, BLACK};

struct Node {
    int data;
    Color color;
    Node* left;
    Node* right;
    Node* parent;
    
    Node(int val) : data(val), color(RED), left(nullptr), right(nullptr), 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* 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 fixViolation(Node* z) {
        while (z != root && z->parent->color == RED) {
            if (z->parent == z->parent->parent->left) {
                Node* y = z->parent->parent->right;
                if (y != nullptr && y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->right) {
                        z = z->parent;
                        leftRotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    rightRotate(z->parent->parent);
                }
            } else {
                Node* y = z->parent->parent->left;
                if (y != nullptr && y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->left) {
                        z = z->parent;
                        rightRotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    leftRotate(z->parent->parent);
                }
            }
        }
        root->color = BLACK;
    }

public:
    RedBlackTree() : root(nullptr) {}
    
    void insert(int val) {
        Node* z = new Node(val);
        Node* y = nullptr;
        Node* x = root;
        
        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;
        }
        
        fixViolation(z);
    }
    
    // Traversal functions (inorder, preorder, postorder)
    // Other functions like delete, search, etc. can also be added
    
};

int main() {
    RedBlackTree rbTree;
    
    rbTree.insert(7);
    rbTree.insert(3);
    rbTree.insert(18);
    rbTree.insert(10);
    rbTree.insert(22);
    
    return 0;
}

在上面的代碼中，我們定義了一個Node結(jié)構(gòu)體表示紅黑樹的節(jié)點，其中包含數(shù)據(jù)值、顏色、左右孩子節(jié)點以及父節(jié)點。然后定義了一個RedBlackTree類來實現(xiàn)紅黑樹的基本操作，包括左旋轉(zhuǎn)、右旋轉(zhuǎn)、修正插入操作中可能出現(xiàn)的違反規(guī)則的情況等。

在