硬核图解红黑树｜从原理到C++完整实现，吃透面试高频考点

硬核图解红黑树从原理到C完整实现吃透面试高频考点本文已同步收录至「数据结构与算法」专栏全网累计10w阅读专注面试高频工程落地从0到1吃透红黑树文章目录硬核图解红黑树从原理到C完整实现吃透面试高频考点一、开篇为什么要学红黑树二、红黑树核心规则必背三、关键为什么最长路径不超最短 2 倍四、红黑树 vs AVL树面试高频对比五、红黑树结构定义C六、插入全解析3 种情况变色旋转情况 1uncle 存在且为 红色 → 只变色情况 2uncle 不存在 / 为黑 同侧 → 单旋变色情况 3uncle 不存在 / 为黑 异侧 → 双旋变色七、完整插入代码可直接复制运行八、红黑树验证判断是否合法九、总结面试 1 分钟背完一、开篇为什么要学红黑树在二叉搜索树BST中极端情况会退化成链表查找效率直接掉到O(n)AVL树通过严格高度差保证绝对平衡但旋转频繁、插入删除代价高而红黑树用一套简单的颜色规则实现近似平衡保证最长路径 ≤ 最短路径 × 2增删查改稳定 O(logN)实际工程中旋转更少、性能更优工程应用直接拉满Java HashMap、TreeMapC STL set/mapLinux 内核进程调度、虚拟内存管理二、红黑树核心规则必背红黑树本质是带颜色约束的二叉搜索树每个节点非红即黑必须满足 4 条铁律每个节点只能是红色 / 黑色根节点一定是黑色红色节点的两个孩子必须都是黑色无连续红节点任意节点到其所有 NULL 叶子路径上黑色节点数量完全相同小补充《算法导论》提到 NIL 叶子为黑工程实现可忽略不影响逻辑。三、关键为什么最长路径不超最短 2 倍这是红黑树平衡本质面试必问由规则 4 → 所有路径黑高相同最短路径 全黑路径长度 bh由规则 3 → 不能有连续红节点最长路径 一黑一红交替长度 2×bh结论bh ≤ 树高 h ≤ 2×bh树高依然是 logN 级别效率稳得一批。四、红黑树 vs AVL树面试高频对比特性红黑树AVL树平衡标准近似平衡颜色约束严格平衡高度差≤1旋转次数少插入最多 2 次删除最多 3 次多频繁触发旋转查找效率略低于 AVL理论最优插入删除更快工程首选理论优实际开销大适用场景频繁增删的场景STL、内核读多写少一句话总结工程选红黑树追求极致查找选 AVL。五、红黑树结构定义C// 颜色枚举enumColour{RED,BLACK};// 红黑树节点templateclassK,classVstructRBTreeNode{pairK,V_kv;// 键值对RBTreeNode*_left;// 左孩子RBTreeNode*_right;// 右孩子RBTreeNode*_parent;// 父节点必须有Colour _col;// 节点颜色RBTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED)// 新节点默认红色{}};templateclassK,classVclassRBTree{typedefRBTreeNodeK,VNode;private:Node*_rootnullptr;};✅ 关键点新节点默认红色插入黑节点会直接破坏规则4必须带parent 指针回溯调整颜色与旋转六、插入全解析3 种情况变色旋转插入流程固定 4 步按 BST 规则插入新节点设为红色父节点黑 → 直接结束父节点红 → 违反规则3开始调整统一命名cur当前节点红parent父节点红grandfather祖父节点黑uncle叔叔节点情况 1uncle 存在且为 红色 → 只变色处理逻辑parent、uncle 变黑grandfather 变红cur 上移到 grandfather继续向上调整若 grandfather 是根最后强制变黑// 核心代码parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;✅ 特点只变色、不旋转处理最快。情况 2uncle 不存在 / 为黑 同侧 → 单旋变色两种同侧场景parent 是 g 左cur 是 p 左 →右单旋parent 是 g 右cur 是 p 右 →左单旋处理旋转后p 变黑g 变红无需继续向上调整// 右单旋示例RotateR(grandfather);parent-_colBLACK;grandfather-_colRED;情况 3uncle 不存在 / 为黑 异侧 → 双旋变色两种异侧场景p 是 g 左cur 是 p 右 →先左单旋 p再右单旋 gp 是 g 右cur 是 p 左 →先右单旋 p再左单旋 g处理旋转后cur 变黑g 变红无需继续向上调整// 左-右双旋示例RotateL(parent);RotateR(grandfather);cur-_colBLACK;grandfather-_colRED;七、完整插入代码可直接复制运行// 右单旋voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;parent-_leftsubLR;if(subLR)subLR-_parentparent;Node*grandParentparent-_parent;subL-_rightparent;parent-_parentsubL;subL-_parentgrandParent;if(grandParentnullptr)_rootsubL;else{if(grandParent-_leftparent)grandParent-_leftsubL;elsegrandParent-_rightsubL;}}// 左单旋voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*grandParentparent-_parent;subR-_leftparent;parent-_parentsubR;subR-_parentgrandParent;if(grandParentnullptr)_rootsubR;else{if(grandParent-_leftparent)grandParent-_leftsubR;elsegrandParent-_rightsubR;}}// 插入主函数boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}elsereturnfalse;}curnewNode(kv);cur-_colRED;if(parent-_kv.firstkv.first)parent-_rightcur;elseparent-_leftcur;cur-_parentparent;// 调整颜色与旋转while(parentparent-_colRED){Node*grandfatherparent-_parent;if(parentgrandfather-_left){Node*unclegrandfather-_right;// 情况1uncle红只变色if(uncleuncle-_colRED){parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}// 情况2、3uncle黑/不存在else{if(curparent-_left){RotateR(grandfather);parent-_colBLACK;grandfather-_colRED;}else{RotateL(parent);RotateR(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}else{Node*unclegrandfather-_left;if(uncleuncle-_colRED){parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else{if(curparent-_right){RotateL(grandfather);parent-_colBLACK;grandfather-_colRED;}else{RotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}}_root-_colBLACK;returntrue;}八、红黑树验证判断是否合法只检查路径长度不够必须严格校验 4 大规则boolCheck(Node*root,intblackNum,constintrefNum){if(rootnullptr){if(blackNum!refNum){cout路径黑色节点数不一致endl;returnfalse;}returntrue;}// 检查连续红节点if(root-_colREDroot-_parent-_colRED){coutroot-_kv.first 存在连续红色节点endl;returnfalse;}if(root-_colBLACK)blackNum;returnCheck(root-_left,blackNum,refNum)Check(root-_right,blackNum,refNum);}boolIsBalance(){if(_rootnullptr)returntrue;if(_root-_colRED)returnfalse;// 取最左路径黑高作为参考intrefNum0;Node*cur_root;while(cur){if(cur-_colBLACK)refNum;curcur-_left;}returnCheck(_root,0,refNum);}九、总结面试 1 分钟背完红黑树 颜色约束 BST保证最长路径 ≤ 最短×2新节点默认红色减少破坏规则4插入调整 3 种情况uncle 红 → 变色向上回溯uncle 黑 同侧 → 单旋变色uncle 黑 异侧 → 双旋变色工程首选STL、内核大量使用效率稳定O(logN)旋转比 AVL 少很多原创不易觉得有用欢迎点赞、收藏、关注后续持续更新硬核算法干货有疑问欢迎评论区交流我会第一时间回复