红黑树是一种自平衡二叉搜索树，它在插入和删除元素时能够保持树的平衡，从而保证了树的查找、插入和删除操作的时间复杂度都是O(logn)。红黑树有以下几个性质：
每个节点要么是黑色，要么是红色。根节点是黑色。每个叶子节点（NIL节点）是黑色。如果一个节点是红色，则它的子节点都是黑色。对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数量的黑色节点。下面是一个简单的C++实现红黑树的例子：
#include <iostream>#include <vector>enum Color { RED, BLACK };template <typename T>struct Node { T data; Color color; Node* left; Node* right; Node* parent; Node(T data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}};template <typename T>class RedBlackTree {public: RedBlackTree() : root(nullptr) {} void insert(T data) { Node<T>* node = new Node<T>(data); insertNode(node); fixInsert(node); } void printInorder() { printInorderHelper(root); std::cout << std::endl; }private: Node<T>* root; void insertNode(Node<T>* node) { Node<T>* temp = nullptr; Node<T>* current = root; while (current != nullptr) { temp = current; if (node->data < current->data) { current = current->left; } else { current = current->right; } } node->parent = temp; if (temp == nullptr) { root = node; } else if (node->data < temp->data) { temp->left = node; } else { temp->right = node; } } void fixInsert(Node<T>* node) { while (node != root && node->parent->color == RED) { if (node->parent == node->parent->parent->left) { Node<T>* uncle = node->parent->parent->right; if (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; leftRotate(node); } node->parent->color = BLACK; node->parent->parent->color = RED; rightRotate(node->parent->parent); } } else { Node<T>* uncle = node->parent->parent->left; if (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; rightRotate(node); } node->parent->color = BLACK; node->parent->parent->color = RED; leftRotate(node->parent->parent); } } } root->color = BLACK; } void leftRotate(Node<T>* node) { Node<T>* temp = node->right; node->right = temp->left; if (temp->left != nullptr) { temp->left->parent = node; } temp->parent = node->parent; if (node->parent == nullptr) { root = temp; } else if (node == node->parent->left) { node->parent->left = temp; } else { node->parent->right = temp; } temp->left = node; node->parent = temp; } void rightRotate(Node<T>* node) { Node<T>* temp = node->left; node->left = temp->right; if (temp->right != nullptr) { temp->right->parent = node; } temp->parent = node->parent; if (node->parent == nullptr) { root = temp; } else if (node == node->parent->right) { node->parent->right
