企业官网建设流程全解析

C++手撕红黑树：从0到200行，拿下STL map底层核心

红黑树是一种自平衡的二叉搜索树，广泛应用于STL的std::map和std::set作为底层核心数据结构。它通过以下性质确保高效操作（插入、删除、搜索平均时间复杂度为$O(\log n)$）：

1. 每个节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶节点（NIL）是黑色。
4. 如果一个节点是红色的，那么其子节点必须是黑色的。
5. 从任意节点到其所有叶节点的路径上，黑色节点的数量（称为黑高）相同。

下面，我将逐步引导您实现一个完整的红黑树类，代码控制在200行以内，覆盖关键操作如插入、旋转和平衡。核心包括节点结构、旋转助手函数和平衡修正逻辑。

步骤1：红黑树节点定义

首先定义节点结构，存储键值对、颜色标记、左/右子节点和父节点指针。使用NIL哨兵节点简化叶节点处理。

#include <iostream> #include <stdexcept> enum Color { RED, BLACK }; template <typename Key, typename Value> class RedBlackNode { public: Key key; Value value; Color color; RedBlackNode* left; RedBlackNode* right; RedBlackNode* parent; RedBlackNode(Key k, Value v, Color c, RedBlackNode* l = nullptr, RedBlackNode* r = nullptr, RedBlackNode* p = nullptr) : key(k), value(v), color(c), left(l), right(r), parent(p) {} };

步骤2：红黑树类框架

定义红黑树类，管理根节点和NIL哨兵节点。提供构造函数、析构函数和旋转助手函数（左旋和右旋）。

template <typename Key, typename Value> class RedBlackTree { private: RedBlackNode<Key, Value>* root; RedBlackNode<Key, Value>* nil; // NIL哨兵节点 public: RedBlackTree() { nil = new RedBlackNode<Key, Value>(Key(), Value(), BLACK); nil->left = nil->right = nil->parent = nil; root = nil; // 初始根指向NIL } ~RedBlackTree() { deleteTree(root); delete nil; } // 左旋函数（核心平衡操作） void leftRotate(RedBlackNode<Key, Value>* x) { RedBlackNode<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(RedBlackNode<Key, Value>* y) { RedBlackNode<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; } };

步骤3：插入操作和平衡修正

插入新节点后，颜色可能违反红黑树性质（如红色节点父节点也是红色），需要通过旋转和重新着色修正。

public: void insert(Key key, Value value) { RedBlackNode<Key, Value>* z = new RedBlackNode<Key, Value>(key, value, RED, nil, nil, nil); RedBlackNode<Key, Value>* y = nil; RedBlackNode<Key, Value>* x = root; // 标准二叉搜索树插入逻辑 while (x != nil) { y = x; if (z->key < x->key) x = x->left; else x = x->right; } z->parent = y; if (y == nil) root = z; else if (z->key < y->key) y->left = z; else y->right = z; z->color = RED; // 新节点初始终为红色 fixInsert(z); } private: void fixInsert(RedBlackNode<Key, Value>* z) { while (z->parent->color == RED) { // 仅当父节点红色时修正 RedBlackNode<Key, Value>* uncle; if (z->parent == z->parent->parent->left) { 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 { // 父节点为右子节点，逻辑对称 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; // 确保根节点黑色 } void deleteTree(RedBlackNode<Key, Value>* node) { // 析构函数辅助 if (node == nil) return; deleteTree(node->left); deleteTree(node->right); delete node; } };

完整代码清单（少于200行）

将以上所有部分整合，并添加简单的查找功能。

#include <iostream> #include <stdexcept> enum Color { RED, BLACK }; template <typename Key, typename Value> class RedBlackNode { public: Key key; Value value; Color color; RedBlackNode* left; RedBlackNode* right; RedBlackNode* parent; RedBlackNode(Key k, Value v, Color c, RedBlackNode* l = nullptr, RedBlackNode* r = nullptr, RedBlackNode* p = nullptr) : key(k), value(v), color(c), left(l), right(r), parent(p) {} }; template <typename Key, typename Value> class RedBlackTree { private: RedBlackNode<Key, Value>* root; RedBlackNode<Key, Value>* nil; public: RedBlackTree() { nil = new RedBlackNode<Key, Value>(Key(), Value(), BLACK); nil->left = nil->right = nil->parent = nil; root = nil; } ~RedBlackTree() { deleteTree(root); delete nil; } void leftRotate(RedBlackNode<Key, Value>* x) { RedBlackNode<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(RedBlackNode<Key, Value>* y) { RedBlackNode<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 insert(Key key, Value value) { RedBlackNode<Key, Value>* z = new RedBlackNode<Key, Value>(key, value, RED, nil, nil, nil); RedBlackNode<Key, Value>* y = nil; RedBlackNode<Key, Value>* x = root; while (x != nil) { y = x; if (z->key < x->key) x = x->left; else x = x->right; } z->parent = y; if (y == nil) root = z; else if (z->key < y->key) y->left = z; else y->right = z; z->color = RED; fixInsert(z); } bool search(Key key) { RedBlackNode<Key, Value>* current = root; while (current != nil) { if (key == current->key) return true; else if (key < current->key) current = current->left; else current = current->right; } return false; } private: void fixInsert(RedBlackNode<Key, Value>* z) { while (z->parent->color == RED) { if (z->parent == z->parent->parent->left) { RedBlackNode<Key, Value>* uncle = z->parent->parent->right; 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->right) { z = z->parent; leftRotate(z); } z->parent->color = BLACK; z->parent->parent->color = RED; rightRotate(z->parent->parent); } } else { RedBlackNode<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; } void deleteTree(RedBlackNode<Key, Value>* node) { if (node == nil) return; deleteTree(node->left); deleteTree(node->right); delete node; } };

注：以上完整代码约160行，覆盖了插入、旋转和平衡的核心逻辑。删除操作更复杂（涉及黑高修正），但为控制行数暂未实现。可将此扩展至完整std::map行为。

调试和使用建议

在实际开发中，建议添加：

1. 删除操作的平衡修正逻辑（参考CLRS算法书案例）。
2. 迭代器支持，以便兼容STL风格。
3. 单元测试验证平衡性。

例如，验证黑高不变量的伪代码如下：

bool checkBlackHeight(RedBlackNode* node) { if (node == nil) return true; int leftHeight = node->left.color == BLACK ? 1 + getHeight(node->left) : getHeight(node->left); int rightHeight = node->right.color == BLACK ? 1 + getHeight(node->right) : getHeight(node->right); return leftHeight == rightHeight && checkBlackHeight(node->left) && checkBlackHeight(node->right); }

通过这份实现，您已掌握了STLmap的核心基础！红黑树高效平衡的本质在于其数学约束，确保操作在$O(\log n)$内完成。下一步可添加模板元优化或内存管理。