C++红黑树:

#include <bits/stdc++.h>

/*
如果没有用，改为
#include <iostream>
#include <queue>
#include <stdexcept>
*/
using namespace std;

enum Color { RED, BLACK };

// 红黑树键值对节点
template <typename Key, typename Value>
class RBTreeNode {
	public:
		Key key;
		Value value;
		Color color;
		RBTreeNode *left, *right, *parent;
	
		RBTreeNode(Key k, Value v, Color c = RED)
			: key(k), value(v), color(c), left(nullptr), right(nullptr), parent(nullptr) {}
};

template <typename Key, typename Value>
class RBTree {
	private:
		RBTreeNode<Key, Value>* root;
		RBTreeNode<Key, Value>* nil;  // 哨兵节点
	
		// 左旋操作
		void leftRotate(RBTreeNode<Key, Value>* x) {
			RBTreeNode<Key, Value>* y = x->right;
			x->right = y->left;
	
			if (y->left != nil)
				y->left->parent = x;
	
			y->parent = x->parent;
	
			if (x->parent == nil)
				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(RBTreeNode<Key, Value>* y) {
			RBTreeNode<Key, Value>* x = y->left;
			y->left = x->right;
	
			if (x->right != nil)
				x->right->parent = y;
	
			x->parent = y->parent;
	
			if (y->parent == nil)
				root = x;
			else if (y == y->parent->left)
				y->parent->left = x;
			else
				y->parent->right = x;
	
			x->right = y;
			y->parent = x;
		}
	
		// 插入后修复平衡
		void fixInsert(RBTreeNode<Key, Value>* z) {
			while (z->parent->color == RED) {
				if (z->parent == z->parent->parent->left) {
					RBTreeNode<Key, Value>* uncle = z->parent->parent->right;
	
					// Case 1: 叔节点为红色
					if (uncle->color == RED) {
						z->parent->color = BLACK;
						uncle->color = BLACK;
						z->parent->parent->color = RED;
						z = z->parent->parent;
					} else {
						// Case 2: 叔节点为黑且z为右子
						if (z == z->parent->right) {
							z = z->parent;
							leftRotate(z);
						}
						// Case 3: 叔节点为黑且z为左子
						z->parent->color = BLACK;
						z->parent->parent->color = RED;
						rightRotate(z->parent->parent);
					}
				} else {  // 对称情况
					RBTreeNode<Key, Value>* uncle = z->parent->parent->left;
	
					if (uncle->color == RED) {
						z->parent->color = BLACK;
						uncle->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;  // 根节点始终为黑
		}
	
		// 查找最小节点
		RBTreeNode<Key, Value>* minimum(RBTreeNode<Key, Value>* node) {
			while (node->left != nil)
				node = node->left;
			return node;
		}
	
		// 子树移植（用v替换u）
		void transplant(RBTreeNode<Key, Value>* u, RBTreeNode<Key, Value>* v) {
			if (u->parent == nil)
				root = v;
			else if (u == u->parent->left)
				u->parent->left = v;
			else
				u->parent->right = v;
			v->parent = u->parent;
		}
	
		// 删除后修复平衡
		void fixDelete(RBTreeNode<Key, Value>* x) {
			while (x != root && x->color == BLACK) {
				if (x == x->parent->left) {
					RBTreeNode<Key, Value>* sibling = x->parent->right;
	
					// Case 1: 兄弟节点为红色
					if (sibling->color == RED) {
						sibling->color = BLACK;
						x->parent->color = RED;
						leftRotate(x->parent);
						sibling = x->parent->right;
					}
	
					// Case 2: 兄弟节点的两个子节点均为黑色
					if (sibling->left->color == BLACK && sibling->right->color == BLACK) {
						sibling->color = RED;
						x = x->parent;
					} else {
						// Case 3: 兄弟节点的右子为黑
						if (sibling->right->color == BLACK) {
							sibling->left->color = BLACK;
							sibling->color = RED;
							rightRotate(sibling);
							sibling = x->parent->right;
						}
						// Case 4: 兄弟节点的右子为红
						sibling->color = x->parent->color;
						x->parent->color = BLACK;
						sibling->right->color = BLACK;
						leftRotate(x->parent);
						x = root;  // 终止循环
					}
				} else {  // 对称情况
					RBTreeNode<Key, Value>* sibling = x->parent->left;
	
					if (sibling->color == RED) {
						sibling->color = BLACK;
						x->parent->color = RED;
						rightRotate(x->parent);
						sibling = x->parent->left;
					}
	
					if (sibling->right->color == BLACK && sibling->left->color == BLACK) {
						sibling->color = RED;
						x = x->parent;
					} else {
						if (sibling->left->color == BLACK) {
							sibling->right->color = BLACK;
							sibling->color = RED;
							leftRotate(sibling);
							sibling = x->parent->left;
						}
	
						sibling->color = x->parent->color;
						x->parent->color = BLACK;
						sibling->left->color = BLACK;
						rightRotate(x->parent);
						x = root;
					}
				}
			}
			x->color = BLACK;
		}
	
		// 递归复制树
		RBTreeNode<Key, Value>* copyTree(RBTreeNode<Key, Value>* src, RBTreeNode<Key, Value>* srcNil) {
			if (src == srcNil)
				return nil;
			RBTreeNode<Key, Value>* node = new RBTreeNode<Key, Value>(src->key, src->value, src->color);
			node->left = copyTree(src->left, srcNil);
	
			if (node->left != nil)
				node->left->parent = node;
			node->right = copyTree(src->right, srcNil);
			if (node->right != nil)
				node->right->parent = node;
			node->parent = nil; // 将在上层设置
			return node;
		}
	
		// 递归释放树
		void clearTree(RBTreeNode<Key, Value>* node) {
			if (node != nil) {
				clearTree(node->left);
				clearTree(node->right);
				delete node;
			}
		}
	
	public:
		// 构造函数
		RBTree() {
			nil = new RBTreeNode<Key, Value>(Key(), Value(), BLACK);
			nil->left = nil->right = nil->parent = nil;
			root = nil;
		}
	
		// 拷贝构造函数
		RBTree(const RBTree& other) {
			nil = new RBTreeNode<Key, Value>(Key(), Value(), BLACK);
			nil->left = nil->right = nil->parent = nil;
			root = nil;
	
			if (other.root != other.nil) {
				root = copyTree(other.root, other.nil);
				root->parent = nil;
			}
		}
	
		// 赋值运算符
		RBTree& operator=(const RBTree& other) {
			if (this != &other) {
				// 创建临时副本
				RBTree temp(other);
				// 交换内容
				swap(root, temp.root);
				swap(nil, temp.nil);
			}
			return *this;
		}
	
		// 析构函数
		~RBTree() {
			clearTree(root);
			delete nil;
		}
	
		// 插入键值对（若存在则更新）
		void insert(const Key& key, const Value& value) {
			RBTreeNode<Key, Value>* z = root;
			RBTreeNode<Key, Value>* parent = nil;
	
			// 查找插入位置并检查是否已存在
			while (z != nil) {
				parent = z;
				if (key == z->key) {
					// 键已存在，更新值
					z->value = value;
					return;
				}
				else if (key < z->key)
					z = z->left;
				else
					z = z->right;
	
			}
	
			// 创建新节点
			z = new RBTreeNode<Key, Value>(key, value);
			z->parent = parent;
	
			if (parent == nil)
				root = z;
			else if (key < parent->key)
				parent->left = z;
			else
				parent->right = z;
	
	
			z->left = z->right = nil;
			z->color = RED;
			fixInsert(z);
		}
	
		// 查找键对应的值（指针）
		Value* find(const Key& key) {
			RBTreeNode<Key, Value>* node = root;
			while (node != nil){
				if (key == node->key)
					return &node->value;
				else if (key < node->key)
					node = node->left;
				else
					node = node->right;
			}
			return nullptr; // 未找到
		}
	
		// 下标访问运算符（若不存在则插入默认值）
		Value& operator[](const Key& key) {
			RBTreeNode<Key, Value>* node = root;
			RBTreeNode<Key, Value>* parent = nil;
	
			while (node != nil) {
				parent = node;
				if (key == node->key)
					return node->value;
				else if (key < node->key)
					node = node->left;
				else 
					node = node->right;
	
			}
	
			// 键不存在，创建新节点
			node = new RBTreeNode<Key, Value>(key, Value());
			node->parent = parent;
			node->left = node->right = nil;
	
			if (parent == nil)
				root = node;
			else if (key < parent->key)
				parent->left = node;
			else
				parent->right = node;
	
			fixInsert(node);
			return node->value;
		}
	
		// 删除键
		void remove(const Key& key) {
			RBTreeNode<Key, Value>* z = root;
			// 查找目标节点
			while (z != nil) {
				if (z->key == key) break;
				z = (key < z->key) ? z->left : z->right;
			}
			if (z == nil) return;  // 未找到
	
			RBTreeNode<Key, Value>* y = z;
			Color yOriginalColor = y->color;
			RBTreeNode<Key, Value>* x;
	
			if (z->left == nil) {
				x = z->right;
				transplant(z, z->right);
			} else if (z->right == nil) {
				x = z->left;
				transplant(z, z->left);
			} else {
				y = minimum(z->right);
				yOriginalColor = y->color;
				x = y->right;
	
				if (y->parent == z)
					x->parent = y;
				else {
					transplant(y, y->right);
					y->right = z->right;
					y->right->parent = y;
				}
	
				transplant(z, y);
				y->left = z->left;
				y->left->parent = y;
				y->color = z->color;
			}
	
			delete z;
			if (yOriginalColor == BLACK)
				fixDelete(x);
		}
	
		// 层次遍历（用于调试）
		void levelOrder() const {
			if (root == nil) {
				cout << "Empty tree" << endl;
				return;
			}
	
			queue<RBTreeNode<Key, Value>*> q;
			q.push(root);
	
			while (!q.empty()) {
				RBTreeNode<Key, Value>* curr = q.front();
				q.pop();
	
				cout << curr->key << ":" << curr->value
					 << "(" << (curr->color == RED ? "R" : "B") << ") ";
	
				if (curr->left != nil) q.push(curr->left);
				if (curr->right != nil) q.push(curr->right);
			}
			cout << endl;
		}
	
		// 中序遍历（按键排序）
		void inorder() const {
			inorderHelper(root);
			cout << endl;
		}
	
	private:
		void inorderHelper(RBTreeNode<Key, Value>* node) const {
			if (node == nil) return;
			inorderHelper(node->left);
			cout << "[" << node->key << ": " << node->value << "] ";
			inorderHelper(node->right);
		}

};

// 测试用例
int main() {
	// 测试插入和查找功能
	RBTree<string, int> scoreTree;
	scoreTree.insert("Alice", 92);
	scoreTree.insert("Bob", 85);
	scoreTree.insert("Charlie", 95);

	cout << "Bob的分数: " << *scoreTree.find("Bob") << endl;

	// 测试[]运算符
	scoreTree["David"] = 88;             // 插入新键值对
	scoreTree["Bob"] = 90;               // 更新Bob的分数
	cout << "更新后Bob的分数: " << scoreTree["Bob"] << endl;
	cout << "Eva的分数(默认值): " << scoreTree["Eva"] << endl;

	// 测试遍历功能
	cout << "\n层次遍历:" << endl;
	scoreTree.levelOrder();

	cout << "\n中序遍历(按键排序):" << endl;
	scoreTree.inorder();

	// 测试删除功能
	scoreTree.remove("Charlie");
	cout << "\n删除Charlie后:" << endl;
	scoreTree.inorder();  // 显示删除后的树结构

	// 测试赋值运算符
	RBTree<string, int> copyTree = scoreTree;
	cout << "\n复制树的中序遍历:" << endl;
	copyTree.inorder();  // 显示复制树的内容

	// 修改副本不影响原树
	copyTree["Alice"] = 100;
	cout << "\n原树中Alice的分数: " << scoreTree["Alice"] << endl;
	cout << "复制树中Alice的分数: " << copyTree["Alice"] << endl;

	// 测试查找未存在键的情况
	int* unknown = scoreTree.find("Unknown");
	if (unknown) {
		cout << "找到Unknown的分数: " << *unknown << endl;
	} else {
		cout << "未找到Unknown" << endl;
	}

	return 0;
}