红黑树是一种自平衡的二叉搜索树，其基本结构可以通过以下代码实现：
#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类来实现红黑树的基本操作，包括左旋转、右旋转、修正插入操作中可能出现的违反规则的情况等。
在
