文章目录C手撕红黑树从0到200行拿下STL map底层核心1. 红黑树的概念1.1 红黑树的规则1.2 红黑树如何确保最长路径不超过最短路径的2倍1.3 红黑树的效率2. 红黑树的实现2.1 红黑树的结构2.2 红黑树的插入2.2.1 插入的大概过程2.2.2 情况1变色2.2.3 情况2单旋 变色2.2.4 情况3双旋 变色2.3 红黑树的插入代码实现2.4 红黑树的查找2.5 红黑树的验证C手撕红黑树从0到200行拿下STL map底层核心1. 红黑树的概念红黑树是一棵二叉搜索树它的每个结点增加一个存储位来表示结点的颜色可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍因而是接近平衡的。1.1 红黑树的规则每个结点不是红色就是黑色。根结点是黑色的。如果一个结点是红色的则它的两个孩子结点必须是黑色的即任意一条路径不会有连续的红色结点。对于任意一个结点从该结点到其所有 NULL 结点的简单路径上均包含相同数量的黑色结点。说明《算法导论》等书籍中补充了“每个叶子结点NIL都是黑色的”规则。这里所指的叶子结点不是传统意义上的叶子结点而是我们说的空结点NIL也叫外部结点。引入 NIL 是为了准确标识所有路径但在实现细节中通常忽略 NIL 结点了解概念即可。1.2 红黑树如何确保最长路径不超过最短路径的2倍由规则4可知从根到 NULL 结点的每条路径都有相同数量的黑色结点。极端场景下最短路径一定是全为黑色结点的路径假设最短路径长度为bhblack height。由规则2和规则3可知任意一条路径不会有连续的红色结点。极端场景下最长路径就是一黑一红间隔组成那么最长路径的长度为2 * bh。综合红黑树的4点规则理论上的全黑最短路径和一黑一红的最长路径并不一定在每棵红黑树中都存在。假设任意一条从根到 NULL 结点的路径长度为h那么bh h 2 * bh。1.3 红黑树的效率假设N是红黑树中结点数量h是最短路径的长度那么2^h - 1 N 2^(2*h) - 1由此推出h ≈ logN即红黑树增删查改的最坏情况是走最长路径2*logN时间复杂度仍为O(logN)。红黑树的表达相对 AVL 树要抽象一些。AVL 树通过高度差直观地控制平衡而红黑树通过4条规则的颜色约束间接实现了近似平衡。两者效率属于同一档次但红黑树在插入相同数量的结点时旋转次数更少因为它对平衡的控制没那么严格。2. 红黑树的实现2.1 红黑树的结构// 枚举值表示颜色enumColour{RED,BLACK};// 这里默认按 key/value 结构实现templateclassK,classVstructRBTreeNode{// 更新控制平衡需要加入 parent 指针pairK,V_kv;RBTreeNodeK,V*_left;RBTreeNodeK,V*_right;RBTreeNodeK,V*_parent;Colour _col;RBTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};templateclassK,classVclassRBTree{typedefRBTreeNodeK,VNode;public:// ...private:Node*_rootnullptr;};2.2 红黑树的插入2.2.1 插入的大概过程按二叉搜索树规则插入新结点。如果是空树插入新增结点为黑色如果是非空树插入新增结点必须为红色否则会破坏规则4。非空树插入后如果父亲结点是黑色则插入结束如果父亲结点是红色则违反规则3需要进一步处理。约定c为当前结点curp为父亲parentg为祖父grandfatheru为叔叔uncle即p的兄弟。2.2.2 情况1变色条件c为红p为红g为黑u存在且为红。处理将p和u变黑g变红然后把g当作新的c继续往上更新。无论c是p的左还是右p是g的左还是右处理方法相同。如果g是根最后再将g变回黑色。2.2.3 情况2单旋 变色条件c为红p为红g为黑u不存在或为黑。如果u不存在c一定是新增结点。如果u存在且为黑c一定不是新增而是由情况1变色更新上来的。处理p是g的左c是p的左以g为旋转点进行右单旋再将p变黑g变红。p是g的右c是p的右以g为旋转点进行左单旋再将p变黑g变红。2.2.4 情况3双旋 变色条件c为红p为红g为黑u不存在或为黑且c与p的方向不一致。处理p是g的左c是p的右先以p为旋转点进行左单旋再以g为旋转点进行右单旋最后将c变黑g变红。p是g的右c是p的左先以p为旋转点进行右单旋再以g为旋转点进行左单旋最后将c变黑g变红。2.3 红黑树的插入代码实现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;}else{returnfalse;}}curnewNode(kv);cur-_colRED;// 新增结点为红色if(parent-_kv.firstkv.first){parent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;while(parentparent-_colRED){Node*grandfatherparent-_parent;if(parentgrandfather-_left){Node*unclegrandfather-_right;if(uncleuncle-_colRED){// 情况1叔叔存在且为红parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else{// 情况2/3叔叔不存在或为黑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){// 情况1叔叔存在且为红parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else{// 情况2/3叔叔不存在或为黑if(curparent-_right){RotateL(grandfather);parent-_colBLACK;grandfather-_colRED;}else{RotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}}_root-_colBLACK;returntrue;}旋转代码与 AVL 树相同只需调整指针无需更新平衡因子。2.4 红黑树的查找按二叉搜索树逻辑实现时间复杂度O(logN)。Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}else{returncur;}}returnnullptr;}2.5 红黑树的验证不能简单地通过检查最长路径不超过最短路径2倍来验证因为即使满足该条件颜色规则也可能被破坏。必须检查4点规则根结点为黑色。无连续红色结点。每条路径黑色结点数量相同。boolCheck(Node*root,intblackNum,constintrefNum){if(rootnullptr){if(refNum!blackNum){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);}
C++手撕红黑树：从0到200行，拿下STL map底层核心
文章目录C手撕红黑树从0到200行拿下STL map底层核心1. 红黑树的概念1.1 红黑树的规则1.2 红黑树如何确保最长路径不超过最短路径的2倍1.3 红黑树的效率2. 红黑树的实现2.1 红黑树的结构2.2 红黑树的插入2.2.1 插入的大概过程2.2.2 情况1变色2.2.3 情况2单旋 变色2.2.4 情况3双旋 变色2.3 红黑树的插入代码实现2.4 红黑树的查找2.5 红黑树的验证C手撕红黑树从0到200行拿下STL map底层核心1. 红黑树的概念红黑树是一棵二叉搜索树它的每个结点增加一个存储位来表示结点的颜色可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍因而是接近平衡的。1.1 红黑树的规则每个结点不是红色就是黑色。根结点是黑色的。如果一个结点是红色的则它的两个孩子结点必须是黑色的即任意一条路径不会有连续的红色结点。对于任意一个结点从该结点到其所有 NULL 结点的简单路径上均包含相同数量的黑色结点。说明《算法导论》等书籍中补充了“每个叶子结点NIL都是黑色的”规则。这里所指的叶子结点不是传统意义上的叶子结点而是我们说的空结点NIL也叫外部结点。引入 NIL 是为了准确标识所有路径但在实现细节中通常忽略 NIL 结点了解概念即可。1.2 红黑树如何确保最长路径不超过最短路径的2倍由规则4可知从根到 NULL 结点的每条路径都有相同数量的黑色结点。极端场景下最短路径一定是全为黑色结点的路径假设最短路径长度为bhblack height。由规则2和规则3可知任意一条路径不会有连续的红色结点。极端场景下最长路径就是一黑一红间隔组成那么最长路径的长度为2 * bh。综合红黑树的4点规则理论上的全黑最短路径和一黑一红的最长路径并不一定在每棵红黑树中都存在。假设任意一条从根到 NULL 结点的路径长度为h那么bh h 2 * bh。1.3 红黑树的效率假设N是红黑树中结点数量h是最短路径的长度那么2^h - 1 N 2^(2*h) - 1由此推出h ≈ logN即红黑树增删查改的最坏情况是走最长路径2*logN时间复杂度仍为O(logN)。红黑树的表达相对 AVL 树要抽象一些。AVL 树通过高度差直观地控制平衡而红黑树通过4条规则的颜色约束间接实现了近似平衡。两者效率属于同一档次但红黑树在插入相同数量的结点时旋转次数更少因为它对平衡的控制没那么严格。2. 红黑树的实现2.1 红黑树的结构// 枚举值表示颜色enumColour{RED,BLACK};// 这里默认按 key/value 结构实现templateclassK,classVstructRBTreeNode{// 更新控制平衡需要加入 parent 指针pairK,V_kv;RBTreeNodeK,V*_left;RBTreeNodeK,V*_right;RBTreeNodeK,V*_parent;Colour _col;RBTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};templateclassK,classVclassRBTree{typedefRBTreeNodeK,VNode;public:// ...private:Node*_rootnullptr;};2.2 红黑树的插入2.2.1 插入的大概过程按二叉搜索树规则插入新结点。如果是空树插入新增结点为黑色如果是非空树插入新增结点必须为红色否则会破坏规则4。非空树插入后如果父亲结点是黑色则插入结束如果父亲结点是红色则违反规则3需要进一步处理。约定c为当前结点curp为父亲parentg为祖父grandfatheru为叔叔uncle即p的兄弟。2.2.2 情况1变色条件c为红p为红g为黑u存在且为红。处理将p和u变黑g变红然后把g当作新的c继续往上更新。无论c是p的左还是右p是g的左还是右处理方法相同。如果g是根最后再将g变回黑色。2.2.3 情况2单旋 变色条件c为红p为红g为黑u不存在或为黑。如果u不存在c一定是新增结点。如果u存在且为黑c一定不是新增而是由情况1变色更新上来的。处理p是g的左c是p的左以g为旋转点进行右单旋再将p变黑g变红。p是g的右c是p的右以g为旋转点进行左单旋再将p变黑g变红。2.2.4 情况3双旋 变色条件c为红p为红g为黑u不存在或为黑且c与p的方向不一致。处理p是g的左c是p的右先以p为旋转点进行左单旋再以g为旋转点进行右单旋最后将c变黑g变红。p是g的右c是p的左先以p为旋转点进行右单旋再以g为旋转点进行左单旋最后将c变黑g变红。2.3 红黑树的插入代码实现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;}else{returnfalse;}}curnewNode(kv);cur-_colRED;// 新增结点为红色if(parent-_kv.firstkv.first){parent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;while(parentparent-_colRED){Node*grandfatherparent-_parent;if(parentgrandfather-_left){Node*unclegrandfather-_right;if(uncleuncle-_colRED){// 情况1叔叔存在且为红parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else{// 情况2/3叔叔不存在或为黑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){// 情况1叔叔存在且为红parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else{// 情况2/3叔叔不存在或为黑if(curparent-_right){RotateL(grandfather);parent-_colBLACK;grandfather-_colRED;}else{RotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}}_root-_colBLACK;returntrue;}旋转代码与 AVL 树相同只需调整指针无需更新平衡因子。2.4 红黑树的查找按二叉搜索树逻辑实现时间复杂度O(logN)。Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}else{returncur;}}returnnullptr;}2.5 红黑树的验证不能简单地通过检查最长路径不超过最短路径2倍来验证因为即使满足该条件颜色规则也可能被破坏。必须检查4点规则根结点为黑色。无连续红色结点。每条路径黑色结点数量相同。boolCheck(Node*root,intblackNum,constintrefNum){if(rootnullptr){if(refNum!blackNum){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);}
