C++ --红黑树

红黑树的五大性质每个节点是红色或黑色根节点是黑色所有叶子NIL空节点都是黑色红色节点的两个子节点都是黑色即不能有连续的红节点从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点黑色高度一致节点定义与辅助函数#include iostream using namespace std; enum Color { RED, BLACK }; templatetypename Key, typename Value struct RBNode { Key key; Value value; Color color; RBNode* left; RBNode* right; RBNode* parent; RBNode(Key k, Value v, Color c RED) : key(k), value(v), color(c), left(nullptr), right(nullptr), parent(nullptr) {} };辅助函数// 判断节点颜色空节点视为黑色 templatetypename Key, typename Value bool isRed(RBNodeKey, Value* node) { return node ! nullptr node-color RED; } // 左旋 templatetypename Key, typename Value void leftRotate(RBNodeKey, Value* root, RBNodeKey, Value* x) { RBNodeKey, Value* y x-right; x-right y-left; if (y-left) y-left-parent x; y-parent x-parent; if (!x-parent) root y; else if (x x-parent-left) x-parent-left y; else x-parent-right y; y-left x; x-parent y; } // 右旋对称 templatetypename Key, typename Value void rightRotate(RBNodeKey, Value* root, RBNodeKey, Value* y) { RBNodeKey, Value* x y-left; y-left x-right; if (x-right) x-right-parent y; x-parent y-parent; if (!y-parent) root x; else if (y y-parent-left) y-parent-left x; else y-parent-right x; x-right y; y-parent x; }旋转的具体步骤插入前的核心认知1为什么新节点必须是红色核心原因如果插入黑色节点会立即违反性质5黑色高度一致因为这条路径多了一个黑色节点修复起来需要调整整棵树。而插入红色节点只可能违反性质4不能有连续红节点这种冲突是局部的可以通过旋转和变色在有限范围内修复。插入操作的两阶段阶段操作复杂度阶段1标准BST插入找到位置挂载新红节点O(log n)阶段2修复红黑性质处理连续红冲突O(log n) 但旋转次数≤2阶段1标准BST插入templatetypename Key, typename Value void insert(RBNodeKey, Value* root, Key key, Value value) { // 步骤1创建新节点红色 RBNodeKey, Value* z new RBNodeKey, Value(key, value, RED); // 步骤2BST查找插入位置 RBNodeKey, Value* y nullptr; // y最终指向z的父节点 RBNodeKey, Value* x root; // x是游标指针 while (x ! nullptr) { y x; // 记录父节点 if (key x-key) x x-left; else if (key x-key) x x-right; else { // 键已存在更新值释放新节点 x-value value; delete z; return; } } // 步骤3挂载新节点 z-parent y; if (y nullptr) { root z; // 树为空新节点就是根 } else if (key y-key) { y-left z; } else { y-right z; } // 步骤4修复红黑性质 insertFixup(root, z); }细节解读y指针记录当前节点的父节点如果树为空新节点直接成为根但根必须是黑色修复阶段会处理。如果键已存在我们直接更新值并返回不进行任何颜色修复。阶段2插入修复修复的触发条件只有一种情况需要修复父节点是红色因为新节点也是红色形成连续红。如果父节点是黑色树已经满足所有红黑性质无需任何操作。修复的总体策略while (父节点是红色) { 判断父节点是祖父的左孩子还是右孩子对称处理 获取叔叔节点的颜色 if (叔叔是红色) { 处理情况1颜色翻转 } else { // 叔叔是黑色或null if (当前节点是父节点的内侧孩子) { 处理情况2旋转父节点转换为情况3 } 处理情况3旋转祖父节点 变色 } } 最后确保根是黑色三种情况详解假设父节点是祖父的左孩子情况1叔叔是红色G(黑) G(红) / \ ---- / \ P(红) U(红) P(黑) U(黑) / / z(红) z(红)操作将父节点P设为黑色将叔叔U设为黑色将祖父G设为红色为了保持黑色高度将z指针上移到G继续循环检查为什么这样做有效局部黑色高度不变原来路径G-P-z有1个黑G现在G-P有1个黑PG-U有1个黑U黑色高度保持。但祖父变红后可能与其父节点形成连续红所以需要继续向上检查。代码实现if (isRed(y)) { // y是叔叔节点 z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; // 上移两层 }情况2叔叔是黑色叔叔节点为空也默认是黑色NIL且z是父节点的右孩子内侧情况G(黑) G(黑) / / P(红) z(红) \ / z(红) P(红)操作将z指向父节点P对z进行左旋为什么要旋转当前z是右孩子属于内侧插入直接右旋祖父会让z跑到左边但结构不对称。通过左旋父节点将情况转化为情况3z变成左孩子即外侧情况。注意旋转后颜色不变因为还没完成修复代码实现if (z z-parent-right) { z z-parent; leftRotate(root, z); }情况3叔叔是黑色且z是父节点的左孩子外侧情况G(黑) P(黑) / / \ P(红) z(红) G(红) / z(红)操作将父节点P设为黑色将祖父G设为红色对祖父G进行右旋为什么这样做有效旋转后P成为新的子树根G变成P的右孩子。P原来是红色现在变黑保证不会与上层形成连续红。G原来是黑色现在变红但它的左右子树黑色高度保持不变。黑色高度验证原路径z→P→G黑色节点数 1只有G新路径z→P→G黑色节点数 1只有P代码实现z-parent-color BLACK; z-parent-parent-color RED; rightRotate(root, z-parent-parent); // 旋转后循环可以结束因为z的父节点已变黑对称情况父节点是祖父的右孩子完全对称只需将左和右互换else { // 父节点是祖父的右孩子 RBNodeKey, Value* y z-parent-parent-left; // 叔叔在左 if (isRed(y)) { // 情况1对称 z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-left) { // 情况2对称z是左孩子 z z-parent; rightRotate(root, z); } // 情况3对称 z-parent-color BLACK; z-parent-parent-color RED; leftRotate(root, z-parent-parent); } }完整插入修复流程图开始插入新节点为红色 ↓ 父节点是红色 ↓ 是 祖父存在且叔叔是红色 ↓ 是 ↓ 否 情况1颜色翻转 叔叔是黑色 ↓ ↓ z上移到祖父 z是父节点的内侧孩子 继续循环 ↓ 是 ↓ 否 情况2旋转父节点 情况3旋转祖父变色 ↓ ↓ 转换为情况3 修复完成退出循环 ↓ 情况3旋转祖父变色 ↓ 修复完成退出循环 ↓ 确保根为黑色 ↓ 结束复杂度和性能分析指标值说明时间O(log n)BST查找O(log n) 修复最多O(log n)旋转次数≤2次情况3后退出情况2转情况3也算1次颜色翻转次数≤O(log n)可能一直上移到根空间O(1)只使用了几个指针变量为什么旋转最多2次情况1颜色翻转不会旋转但可能向上传播情况2旋转父节点后必然进入情况3情况3旋转祖父节点后必然退出循环所以最多2次旋转情况2情况3各一次完整的insertFixup代码templatetypename Key, typename Value void insertFixup(RBNodeKey, Value* root, RBNodeKey, Value* z) { // 只要父节点是红色就需要修复 while (z ! root isRed(z-parent)) { // 分支A父节点是祖父的左孩子 if (z-parent z-parent-parent-left) { RBNodeKey, Value* uncle z-parent-parent-right; // ★情况1叔叔是红色 → 颜色翻转 if (isRed(uncle)) { z-parent-color BLACK; uncle-color BLACK; z-parent-parent-color RED; z z-parent-parent; // 上移两层继续检查 } else { // ★情况2z是右孩子内侧→ 左旋父节点 if (z z-parent-right) { z z-parent; leftRotate(root, z); } // ★情况3z是左孩子外侧→ 右旋祖父 变色 z-parent-color BLACK; z-parent-parent-color RED; rightRotate(root, z-parent-parent); // 此时父节点已变黑循环必然结束 } } else { // 分支B父节点是祖父的右孩子完全对称 RBNodeKey, Value* uncle z-parent-parent-left; if (isRed(uncle)) { 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(root, z); } z-parent-color BLACK; z-parent-parent-color RED; leftRotate(root, z-parent-parent); } } } // 保证根永远是黑色处理情况1传播到根的情况 root-color BLACK; }总结插入操作的思维导图红黑树插入├── 阶段1BST插入│ ├── 查找位置y记录父节点│ ├── 挂载新节点红色│ └── 更新父指针│└── 阶段2修复while父为红├── 父是祖父左孩子│ ├── 叔红 → 翻转颜色上移│ └── 叔黑│ ├── z是右孩子 → 左旋父转情况3│ └── z是左孩子 → 右旋祖父变色结束│└── 父是祖父右孩子对称├── 叔红 → 翻转颜色上移└── 叔黑├── z是左孩子 → 右旋父转情况3└── z是右孩子 → 左旋祖父变色结束最后根变黑强制