【C++进阶】红黑树的实现

目录本节学习目标1 红黑树概念1.1 红黑树四条硬性规则1.2 为什么最长路径 ≤ 2 × 最短路径1.3 AVL 树 vs 红黑树2 红黑树结点定义2.1 旋转函数说明3 红黑树插入完整逻辑插入步骤总览场景 1叔叔 u 存在并且 u 是红色只变色不旋转场景 2叔叔 u 不存在 /u 存在但是 u 是黑色单旋 变色场景 3叔叔 u 不存在 /u 存在但是 u 是黑色双旋 变色完整 Insert 插入源码4 红黑树查找5 红黑树校验函数调试必写6 关于红黑树删除本篇核心考点总结本节学习目标掌握红黑树 4 条核心规则理解 NIL 外部叶子结点概念理解红黑树 “最长路径不超过最短路径 2 倍” 的原理对比 AVL 树掌握红黑树结点结构_kv键值对、左右孩子、_parent父指针、颜色枚举掌握红黑树插入完整流程BST 插入、新增结点默认红色分三大 case 处理叔叔红 (仅变色)、叔叔黑 / 不存在单旋变色、叔叔黑 / 不存在双旋变色看懂红黑树的左单旋、右单旋和 AVL 旋转逻辑一致没有平衡因子手写红黑树校验函数校验根颜色、禁止连续红结点、所有路径黑色结点数目相等对比 AVL 树理解红黑树优势旋转次数更少STLmap/set底层就是红黑树了解删除复杂课件不实现删除1 红黑树概念红黑树是一棵二叉搜索树每个结点多一个颜色标记红色或者黑色。通过颜色约束间接实现近似平衡。性质保证任意一条从根到 NIL 空叶子结点的路径最长路径长度不会超过最短路径的 2 倍。1.1 红黑树四条硬性规则每个结点只能是红色 或者 黑色。根结点必须是黑色。不能出现连续的红色结点如果一个结点是红色那么它的两个直接孩子必须是黑色。父红则子不能红对于任意结点该结点到达所有 NIL空外部叶子结点的全部路径上黑色结点的数量完全相等。补充 NIL 外部结点说明 《算法导论》中提到所有 NIL 叶子外部空结点是黑色。课件实现中代码不专门创建 NIL 结点把nullptr等价看作黑色 NIL 结点。NIL 只是逻辑概念代码不实例化对象。1.2 为什么最长路径 ≤ 2 × 最短路径设黑色高度bh从某结点向下走到 NIL路径上面黑色结点数量。最短路径全部都是黑色结点路径长度 bh。根据规则 3不能连续红色结点极端最长路径红黑交替一红一黑路径长度 2*bh。所以bh ≤ h ≤ 2*bh。 结点数量 N时间复杂度增删查 \(O(logN)\)最坏 2logN。1.3 AVL 树 vs 红黑树表格AVL 树红黑树平衡约束严格平衡左右子树高度差绝对值≤1颜色约束近似平衡最长路径≤2 倍最短路径平衡控制平衡因子 bf记录高度差结点红、黑颜色标记旋转次数插入删除触发旋转频繁旋转少大部分情况只做变色查找性能理论略快略低同一复杂度级别 \(O(logN)\)工程使用极少手写标准库不使用STLmap/set底层实现工业界主流AVL 追求严格高度平衡红黑树牺牲一点点查找性能换取更少旋转综合工程表现更好。2 红黑树结点定义//结点颜色枚举 enum Colour { RED, BLACK }; templateclass K, class V struct RBTreeNode { pairK,V _kv; RBTreeNodeK,V* _left; RBTreeNodeK,V* _right; RBTreeNodeK,V* _parent; //父指针向上回溯处理颜色 Colour _col; RBTreeNode(const pairK,V kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_col(RED) //新结点默认红色 {} }; templateclass K,class V class RBTree { typedef RBTreeNodeK,V Node; private: Node* _root nullptr; public: //接口省略 };✨重点新插入结点默认设置为 RED 红色。 如果新增结点设置黑色直接破坏规则 4每条路径黑色数量相等修复代价巨大新增红色只会可能违反规则 3连续红。2.1 旋转函数说明红黑树的左单旋RotateL、右单旋RotateR和 AVL 树旋转代码完全一样红黑树没有平衡因子旋转之后不用维护 bf只需要修改颜色。 旋转核心要点修改父子孩子指针更新所有结点的_parent父指针如果旋转结点是根更新_root。//右单旋 void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if(subLR ! nullptr) subLR-_parent parent; Node* ppNode parent-_parent; subL-_right parent; parent-_parent subL; if(ppNode nullptr) { _root subL; subL-_parent nullptr; } else { if(parent ppNode-_left) ppNode-_left subL; else ppNode-_right subL; subL-_parent ppNode; } } //左单旋 void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if(subRL ! nullptr) subRL-_parent parent; Node* ppNode parent-_parent; subR-_left parent; parent-_parent subR; if(ppNode nullptr) { _root subR; subR-_parent nullptr; } else { if(parent ppNode-_left) ppNode-_left subR; else ppNode-_right subR; subR-_parent ppNode; } }3 红黑树插入完整逻辑插入步骤总览按照普通 BST 二叉搜索树规则查找位置插入新结点key 重复返回 false 插入失败。空树直接 new 结点根强制设置为 BLACK 黑色结束。非空树新结点cur默认红色。如果父结点parent是黑色没有违反任何红黑规则直接插入结束。如果父结点parent是红色违反规则 3连续红色。 此时祖父grandfather(g)一定是黑色。接下来看叔叔结点 uncle (u)分三大场景处理。符号约定cur(c)当前结点新增结点或者向上迭代上来的结点parent(p)cur 的父亲grandfather(g)cur 的祖父p 的父亲p 为红g 必然黑色uncle(u)p 的兄弟cur 的叔叔结点场景 1叔叔 u 存在并且 u 是红色只变色不旋转条件p红g黑u红处理逻辑parent (p) 变黑uncle (u) 变黑grandfather (g) 变红把g赋值给cur继续向上循环迭代处理循环结束之后最后强制把根结点置为黑色。原理p、u 变黑两条子路径黑色计数 1g 变红抵消增加的黑色计数子树黑色高度不变。但是 g 变红g 和 g 的父结点有可能形成连续红色必须继续向上处理。该场景不管 p 是 g 的左还是右cur 是 p 左还是右逻辑完全一样只变色不旋转。场景 2叔叔 u 不存在 /u 存在但是 u 是黑色单旋 变色两种子情况LLp 是 g 左孩子cur 是 p 左孩子 →右单旋 RotateR (g)旋转完成p 变黑g 变红处理完毕break 不再向上循环。RRp 是 g 右孩子cur 是 p 右孩子 →左单旋 RotateL (g)旋转完成p 变黑g 变红处理完毕break。旋转之后子树黑色高度不变上层不会出现连续红色不需要继续向上。场景 3叔叔 u 不存在 /u 存在但是 u 是黑色双旋 变色LRp 是 g 左孩子cur 是 p 右孩子先对 p 做左单旋RotateL(p)再对 g 做右单旋RotateR(g)cur 变黑g 变红break 结束。RLp 是 g 右孩子cur 是 p 左孩子先对 p 做右单旋RotateR(p)再对 g 做左单旋RotateL(g)cur 变黑g 变红break 结束。双旋完成后cur 成为这棵局部子树根黑色g 变红黑色高度不变停止向上迭代。完整 Insert 插入源码bool Insert(const pairK, V kv) { if (_root nullptr) { _root new Node(kv); _root-_col BLACK; //根必须黑色 return true; } //BST查找插入位置 Node* parent nullptr; Node* cur _root; while(cur ! nullptr) { if(cur-_kv.first kv.first) { parent cur; cur cur-_right; } else if(cur-_kv.first kv.first) { parent cur; cur cur-_left; } else { //key重复 return false; } } //创建新结点默认RED红色 cur new Node(kv); cur-_col RED; if(parent-_kv.first kv.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; //向上处理颜色冲突父结点为红色才进入循环 while(parent ! nullptr parent-_col RED) { Node* grandfather parent-_parent; //父是红祖父一定是黑 if(parent grandfather-_left) { //父亲是祖父的左孩子叔叔是祖父的右孩子 Node* uncle grandfather-_right; if(uncle ! nullptr uncle-_col RED) { //【场景1叔叔红色只变色】 parent-_col BLACK; uncle-_col BLACK; grandfather-_col RED; //g作为新cur继续向上 cur grandfather; parent cur-_parent; } else { //【场景2/3叔叔为空或者黑色旋转变色】 if(cur parent-_left) { //LL 右单旋 RotateR(grandfather); parent-_col BLACK; grandfather-_col RED; } else { //LR 双旋先左后右 RotateL(parent); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } break; //旋转处理完毕退出循环 } } else { //父亲是祖父的右孩子叔叔是祖父的左孩子 Node* uncle grandfather-_left; if(uncle ! nullptr uncle-_col RED) { //场景1叔叔红色变色 parent-_col BLACK; uncle-_col BLACK; grandfather-_col RED; cur grandfather; parent cur-_parent; } else { //叔叔空/黑色旋转变色 if(cur parent-_right) { //RR左单旋 RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; } else { //RL双旋先右后左 RotateR(parent); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } //循环结束强制根结点黑色 _root-_col BLACK; return true; }4 红黑树查找复用二叉搜索树查找逻辑时间复杂度 \(O(logN)\)Node* Find(const K key) { Node* cur _root; while(cur ! nullptr) { if(cur-_kv.first key) { cur cur-_right; } else if(cur-_kv.first key) { cur cur-_left; } else { return cur; } } return nullptr; }5 红黑树校验函数调试必写❗错误思路只判断最长路径 ≤2 倍最短路径不能作为红黑树校验标准。满足路径长度条件结点颜色依然可以违反 4 条规则后续插入会直接出错。 必须逐条校验四条规则根结点必须黑色。不能存在连续红色结点当前结点红色父结点不能红色。每一条从根到 nullptr (NIL) 路径黑色结点数目完全相等。递归校验代码//内部递归blackNum 当前路径累计黑色数量refNum 参考路径黑色计数 bool _Check(Node* root, int blackNum, const int refNum) { if(root nullptr) { //走到NIL空结点一条路径结束 if(blackNum ! refNum) { cout 路径黑色结点数目不一致 endl; return false; } return true; } //规则不能连续红色当前结点红父亲不能红 if(root-_col RED root-_parent-_col RED) { cout key: root-_kv.first 存在连续红色结点 endl; return false; } //黑色结点计数1 if(root-_col BLACK) { blackNum; } //递归校验左右子树 return _Check(root-_left, blackNum, refNum) _Check(root-_right, blackNum, refNum); } //对外接口 bool IsBalance() { if(_root nullptr) return true; //规则根结点必须黑色 if(_root-_col RED) { cout 根结点是红色违反红黑树规则 endl; return false; } //求参考黑色计数一直向左走到NIL统计黑色结点数量作为基准refNum int refNum 0; Node* cur _root; while(cur ! nullptr) { if(cur-_col BLACK) refNum; cur cur-_left; } return _Check(_root, 0, refNum); }6 关于红黑树删除本章节不实现删除操作。删除逻辑复杂分为大量 case需要处理结点删除后的颜色修复工程参考《算法导论》、《STL 源码剖析》阅读源码。笔试面试重点考察红黑树规则、插入三种 case、AVL 对比删除一般不手写。本篇核心考点总结红黑树 4 条核心规则①结点红或黑②根必须黑色③不能连续红色结点④任意结点到全部 NIL 空叶子路径黑色结点数量相等。最长路径不超过最短路径 2 倍时间复杂度\(O(logN)\)对比 AVL红黑树旋转更少STL map/set 底层采用红黑树。新增结点默认红色新增黑色极易破坏黑色计数规则。插入冲突处理三大 casecase1叔叔 uncle 为红色仅变色向上迭代不旋转case2叔叔为空 / 黑色LL/RR单旋 变色结束case3叔叔为空 / 黑色LR/RL双旋 变色结束循环结束强制根结点置为黑色。红黑树旋转和 AVL 旋转代码一样没有平衡因子旋转后只修改结点颜色。校验函数①根黑色②禁止连续红结点③全部路径黑色结点数目相等不能只靠路径长度倍数校验。面试简答Q红黑树和 AVL 树区别AAVL 依靠平衡因子严格高度平衡红黑树依靠颜色做近似平衡AVL 查找略快插入删除旋转多红黑树旋转次数少综合性能更好STL map set 底层红黑树。Q红黑树新结点为什么默认是红色A新增黑色直接破坏规则 4所有路径黑色计数被打乱修复成本高新增红色只会可能触发连续红色修复逻辑简单。Q红黑树插入叔叔结点红色的时候做什么A父亲、叔叔变黑祖父变红把祖父当做 cur 继续向上处理不需要旋转。