手撕红黑树：C++实现200行核心代码

C手撕红黑树从0到200行拿下STL map底层核心红黑树是一种自平衡的二叉搜索树广泛应用于STL的std::map和std::set作为底层核心数据结构。它通过以下性质确保高效操作插入、删除、搜索平均时间复杂度为$O(\log n)$每个节点是红色或黑色。根节点是黑色。每个叶节点NIL是黑色。如果一个节点是红色的那么其子节点必须是黑色的。从任意节点到其所有叶节点的路径上黑色节点的数量称为黑高相同。下面我将逐步引导您实现一个完整的红黑树类代码控制在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: RedBlackNodeKey, Value* root; RedBlackNodeKey, Value* nil; // NIL哨兵节点 public: RedBlackTree() { nil new RedBlackNodeKey, Value(Key(), Value(), BLACK); nil-left nil-right nil-parent nil; root nil; // 初始根指向NIL } ~RedBlackTree() { deleteTree(root); delete nil; } // 左旋函数核心平衡操作 void leftRotate(RedBlackNodeKey, Value* x) { RedBlackNodeKey, 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(RedBlackNodeKey, Value* y) { RedBlackNodeKey, 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) { RedBlackNodeKey, Value* z new RedBlackNodeKey, Value(key, value, RED, nil, nil, nil); RedBlackNodeKey, Value* y nil; RedBlackNodeKey, 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(RedBlackNodeKey, Value* z) { while (z-parent-color RED) { // 仅当父节点红色时修正 RedBlackNodeKey, 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(RedBlackNodeKey, 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: RedBlackNodeKey, Value* root; RedBlackNodeKey, Value* nil; public: RedBlackTree() { nil new RedBlackNodeKey, Value(Key(), Value(), BLACK); nil-left nil-right nil-parent nil; root nil; } ~RedBlackTree() { deleteTree(root); delete nil; } void leftRotate(RedBlackNodeKey, Value* x) { RedBlackNodeKey, 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(RedBlackNodeKey, Value* y) { RedBlackNodeKey, 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) { RedBlackNodeKey, Value* z new RedBlackNodeKey, Value(key, value, RED, nil, nil, nil); RedBlackNodeKey, Value* y nil; RedBlackNodeKey, 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) { RedBlackNodeKey, 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(RedBlackNodeKey, Value* z) { while (z-parent-color RED) { if (z-parent z-parent-parent-left) { RedBlackNodeKey, 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 { RedBlackNodeKey, 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(RedBlackNodeKey, Value* node) { if (node nil) return; deleteTree(node-left); deleteTree(node-right); delete node; } };注以上完整代码约160行覆盖了插入、旋转和平衡的核心逻辑。删除操作更复杂涉及黑高修正但为控制行数暂未实现。可将此扩展至完整std::map行为。调试和使用建议在实际开发中建议添加删除操作的平衡修正逻辑参考CLRS算法书案例。迭代器支持以便兼容STL风格。单元测试验证平衡性。例如验证黑高不变量的伪代码如下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)$内完成。下一步可添加模板元优化或内存管理。