要手动实现一个红黑树，在C++中，你需要首先定义红黑树的节点结构，并实现红黑树的插入、删除、查找等基本操作。下面是一个简单的红黑树的实现示例：
#include <iostream>enum Color { RED, BLACK };struct Node { int key; Color color; Node* left; Node* right; Node* parent; Node(int key) : key(key), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}};class RedBlackTree {private: Node* root; void rotateLeft(Node* node) { Node* rightChild = node->right; node->right = rightChild->left; if (rightChild->left != nullptr) { rightChild->left->parent = node; } rightChild->parent = node->parent; if (node->parent == nullptr) { root = rightChild; } else if (node == node->parent->left) { node->parent->left = rightChild; } else { node->parent->right = rightChild; } rightChild->left = node; node->parent = rightChild; } void rotateRight(Node* node) { Node* leftChild = node->left; node->left = leftChild->right; if (leftChild->right != nullptr) { leftChild->right->parent = node; } leftChild->parent = node->parent; if (node->parent == nullptr) { root = leftChild; } else if (node == node->parent->right) { node->parent->right = leftChild; } else { node->parent->left = leftChild; } leftChild->right = node; node->parent = leftChild; } void fixInsertion(Node* node) { while (node != root && node->parent->color == RED) { if (node->parent == node->parent->parent->left) { Node* uncle = node->parent->parent->right; if (uncle != nullptr && uncle->color == RED) { node->parent->color = BLACK; uncle->color = BLACK; node->parent->parent->color = RED; node = node->parent->parent; } else { if (node == node->parent->right) { node = node->parent; rotateLeft(node); } node->parent->color = BLACK; node->parent->parent->color = RED; rotateRight(node->parent->parent); } } else { Node* uncle = node->parent->parent->left; if (uncle != nullptr && uncle->color == RED) { node->parent->color = BLACK; uncle->color = BLACK; node->parent->parent->color = RED; node = node->parent->parent; } else { if (node == node->parent->left) { node = node->parent; rotateRight(node); } node->parent->color = BLACK; node->parent->parent->color = RED; rotateLeft(node->parent->parent); } } } root->color = BLACK; } void insert(Node* node) { Node* current = root; Node* parent = nullptr; while (current != nullptr) { parent = current; if (node->key < current->key) { current = current->left; } else { current = current->right; } } node->parent = parent; if (parent == nullptr) { root = node; } else if (node->key < parent->key) { parent->left = node; } else { parent->right = node; } node->color = RED; fixInsertion(node); }public: RedBlackTree() : root(nullptr) {} void insert(int key) { Node* node = new Node(key); insert(node); } void printInOrderTraversal(Node* node) { if (node == nullptr) { return; } printInOrderTraversal(node->left); std::cout << node->key << " "; printInOrderTraversal(node->right); } void print() { printInOrderTraversal(root); std::cout << std::endl; }};int main() { RedBlackTree tree; tree.insert(10); tree.insert(20); tree.insert(30); tree.insert(15); tree.insert(25); tree.print(); return
