红黑树是一种自平衡的二叉查找树，可以在O(log n)的时间复杂度内进行插入、删除和查找操作。以下是一个简单的C++实现红黑树的算法：
#include <iostream>using namespace std;enum Color { RED, BLACK };struct Node { int data; Color color; Node *left, *right, *parent; Node(int data) : data(data) { parent = left = right = NULL; color = RED; }};class RedBlackTree {private: Node *root; void rotateLeft(Node *x) { Node *y = x->right; x->right = y->left; if (y->left != NULL) { y->left->parent = x; } y->parent = x->parent; if (x->parent == NULL) { root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; x->parent = y; } void rotateRight(Node *x) { Node *y = x->left; x->left = y->right; if (y->right != NULL) { y->right->parent = x; } y->parent = x->parent; if (x->parent == NULL) { root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->right = x; x->parent = y; } void fixViolation(Node *x) { Node *parent = NULL; Node *grandparent = NULL; while (x != root && x->color == RED && x->parent->color == RED) { parent = x->parent; grandparent = x->parent->parent; if (parent == grandparent->left) { Node *uncle = grandparent->right; if (uncle != NULL && uncle->color == RED) { grandparent->color = RED; parent->color = BLACK; uncle->color = BLACK; x = grandparent; } else { if (x == parent->right) { rotateLeft(parent); x = parent; parent = x->parent; } rotateRight(grandparent); swap(parent->color, grandparent->color); x = parent; } } else { Node *uncle = grandparent->left; if (uncle != NULL && uncle->color == RED) { grandparent->color = RED; parent->color = BLACK; uncle->color = BLACK; x = grandparent; } else { if (x == parent->left) { rotateRight(parent); x = parent; parent = x->parent; } rotateLeft(grandparent); swap(parent->color, grandparent->color); x = parent; } } } root->color = BLACK; } void insertHelper(Node *node) { Node *cur = root; Node *parent = NULL; while (cur != NULL) { parent = cur; if (node->data < cur->data) { cur = cur->left; } else { cur = cur->right; } } node->parent = parent; if (parent == NULL) { root = node; } else if (node->data < parent->data) { parent->left = node; } else { parent->right = node; } fixViolation(node); } void inorderHelper(Node *node) { if (node == NULL) { return; } inorderHelper(node->left); cout << node->data << " "; inorderHelper(node->right); }public: RedBlackTree() : root(NULL) {} void insert(int data) { Node *node = new Node(data); insertHelper(node); } void inorder() { inorderHelper(root); }};int main() { RedBlackTree tree; tree.insert(7); tree.insert(3); tree.insert(18); tree.insert(10); tree.insert(22); tree.insert(8); tree.insert(11); tree.insert(26); cout << "Inorder traversal of the constructed Red-Black tree is: "; tree.inorder(); return 0;}