在C++中实现红黑树的基本结构

红黑树是一种自平衡的二叉搜索树，其基本结构可以通过以下代码实现：

#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结构体表示红黑树的节点，其中包含数据值、颜色、左右孩子节点以及父节点。然后定义了一个RedBlackTree类来实现红黑树的基本操作，包括左旋转、右旋转、修正插入操作中可能出现的违反规则的情况等。

在