文章目录1 红黑树的概念1.1 红黑树五大规则1.2 最长路径不超过最短路径 2 倍2. 红黑树的底层实现2.1 初始框架2.2 红黑树的插入2.2.1 情况一仅变色2.2.2 情况二单旋变色2.2.3 双旋变色2.3 左右旋代码分享3. 整体代码1 红黑树的概念红黑树是一棵二叉搜索树每个节点额外存储颜色标识颜色分为红色、黑色两种。红黑树通过约束根到叶子路径上的节点颜色保证任意一条路径的长度不会超过其他路径的2倍属于近似平衡二叉树。1.1 红黑树五大规则每个节点的颜色只能是红色或黑色。根节点必须为黑色。若一个节点为红色则其两个子节点都必须是黑色路径中不存在连续红色节点。对于任意节点从该节点出发到所有空NIL节点的每条路径包含的黑色节点数量相同。所有空节点NIL/外部节点均为黑色。补充说明此处的叶子特指空NIL节点外部节点并非传统意义上的实际叶子节点部分代码实现中会省略对NIL节点的显性处理了解概念即可。这里给几个红黑树图例帮助理解1.2 最长路径不超过最短路径 2 倍红黑树依靠自身五大约束保证最长路径≤最短路径的2倍所有根到空节点的路径黑节点数量一致黑高bh全黑路径即为最短路径长度等于bh。规则禁止连续红节点路径中红节点必须与黑节点相间排列。极限情况下每条黑节点后搭配一个红节点最长路径长度为2bh。综上任意路径长度介于bh与2bh之间因此最长路径不会超过最短路径的2倍。2. 红黑树的底层实现2.1 初始框架// 枚举值表示颜色enumColour{RED,BLACK};// 这里我们默认按key/value结构实现templateclass K,class VstructRBTreeNode{// 这里更新控制平衡也要加入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){}};templateclass K,class Vclass RBTree{typedefRBTreeNodeK,VNode;public:private:Node*_rootnullptr;};2.2 红黑树的插入红黑树的插入分三种情况我们需要在每次插入式考虑红黑树的4条规则。大概有以下内容1.空树插入新增结点为黑色结点。2.非空树插入新增结点必须为红色结点若插入黑色结点会直接破坏红黑树规则 4每条路径黑结点数量相同该规则极难维护因此非空插入默认染红。3.非空树插入后新增结点为红色若父结点是黑色未违反任何红黑树规则插入直接结束。4.非空树插入后新增结点为红色若父结点是红色违反红黑树规则 3红色结点不能有红色子结点即无连续红结点此时可确定固定颜色当前结点红、父结点红、祖父结点黑最终调整方案完全由叔叔结点u 的颜色决定需分情况处理。2.2.1 情况一仅变色只要叔叔节点 u 是红色就只变色、不旋转这其实很好理解。为什么这种情况只变色、不旋转因为叔叔 u 是红色 → 变色就能直接修复连续红还能保持黑高不变。完整逻辑链c红、p红、g黑、u红出现了连续红c-p违反规则。p 和 u 都是红色、且都是 g 的孩子把p、u 同时变黑→ 两条子树的黑高各 1为了保持整棵树黑高不变把g 变红→ g 所在路径黑高 -1→ 整体黑高恢复平衡连续红消失了黑高也没变→完全不需要旋转这里给出图例代码实现if(uncleuncle-_colRED)// 修改8 RED - RED{parent-_coluncle-_colBLACK;grandfather-_colRED;//继续往上处理curgrandfather;parentcur-_parent;}2.2.2 情况二单旋变色情况叔叔 u 为黑 / 不存在前提条件当前节点c红色父节点p红色祖父节点g黑色叔叔节点u不存在或存在且为黑色关键推论u不存在 → c一定是新增节点u存在且为黑 → c一定不是新增节点是之前变色后向上更新上来的核心分析存在连续红色节点c-p违规单纯变色无法修复黑高平衡必须采用旋转 变色组合处理具体处理规则1.左左情况p是g的左孩子c是p的左孩子操作以g为支点执行右单旋变色p变黑g变红结果p成为子树根节点黑高不变无连续红节点无需向上更新右右情况p是g的右孩子c是p的右孩子操作以g为支点执行左单旋变色p变黑g变红结果p成为子树根节点黑高不变无连续红节点无需向上更新给个示例代码分享//在左边if(curparent-_left){// g// p u// cRotateR(grandfather);//将g右旋p为父p变黑g变红这里P肯定是红的,循环条件parent-_colBLACK;grandfather-_colRED;}左右旋代码后面给出。2.2.3 双旋变色父子节点呈折线、叔叔节点为空或黑色时执行双旋。前提条件当前节点c红色父节点p红色祖父节点g黑色叔叔节点u不存在或存在且为黑色关键推论u不存在 → c 一定是新增节点u存在且为黑 → c 一定不是新增节点是子树插入后经变色向上更新而来核心分析存在c-p连续红色节点违规单纯变色无法修复黑高必须旋转变色1. 左右情况p是g的左孩子c是p的右孩子以p为支点执行左单旋以g为支点执行右单旋变色c变黑g变红结果c成为子树根黑高不变无连续红节点无需向上更新2. 右左情况p是g的右孩子c是p的左孩子以p为支点执行右单旋以g为支点执行左单旋变色c变黑g变红结果c成为子树根黑高不变无连续红节点无需向上更新核心叔叔红只变色叔叔黑/无则旋转加变色。示例代码分享else//在右边{// g// p u// cRotateL(parent);//先左旋再右旋将parent右边节点与parent左旋再一g右旋// g// c u// pRotateR(grandfather);// c// p g// ucur-_colBLACK;grandfather-_colRED;}2.3 左右旋代码分享//右旋voidRotateR(Node*parent){//subl是子节点subl右节点放parent左边parent的父节点换为subl,subl的右节点换为parent//如果parent为root则subl的父节点为null,不为root就换为parent之前的父节点Node*sublparent-_left;Node*sublRsubl-_right;parent-_leftsublR;if(sublR){sublR-_parentparent;}Node*pParentparent-_parent;// 修改11保存祖父节点subl-_rightparent;parent-_parentsubl;if(parent_root){_rootsubl;subl-_parentnullptr;}else{if(pParent-_leftparent){pParent-_leftsubl;// 修改12subL - subl}else{pParent-_rightsubl;// 修改13subL - subl}subl-_parentpParent;// 修改14subL - subl}}//左转和右转差不多voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*parentParentparent-_parent;subR-_leftparent;parent-_parentsubR;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentparentParent-_left){parentParent-_leftsubR;}else{parentParent-_rightsubR;}subR-_parentparentParent;}}3. 整体代码#pragmaonce#includeiostreamusing namespace std;// 枚举值表示颜色enumColour{RED,BLACK};// 这里我们默认按key/value结构实现templateclass K,class VstructRBTreeNode{// 这里更新控制平衡也要加入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){}};templateclass K,class Vclass RBTree{typedefRBTreeNodeK,VNode;public:boolInsert(constpairK,Vkv){//先来个根节点if(_rootnullptr){// 修改1null - nullptr_rootnewNode(kv);//这里是指针_root-_colBLACK;returntrue;}Node*parentnullptr;// 修改2NULL - nullptrNode*cur_root;//找到插入位置while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}//开始插入(一般插入为红设计上选红色代价最小、最好调//这里cur还是空这里实例化curnewNode(kv);cur-_colRED;//因为之前cur是空指针所以需要重新关联父节点if(parent-_kv.firstkv.first){// 修改3parent-kv.first - parent-_kv.firstparent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;// 修改4插入后设置父节点指针//这里已经插入节点但还需要通过旋转来维护红黑树规则while(parentparent-_colRED){//定义个爷便于找Node*grandfatherparent-_parent;// 修改5parent-_right - parent-_parent//parent在g左边if(parentgrandfather-_left)// 修改6grandfather-_right - grandfather-_left{Node*unclegrandfather-_right;// 修改7grandfather-_right - grandfather-_right保持但上面条件改了//叔节点在且为红与parent节点一样if(uncleuncle-_colRED)// 修改8 RED - RED{parent-_coluncle-_colBLACK;grandfather-_colRED;//继续往上处理curgrandfather;parentcur-_parent;}//uncle为空或为黑这个时候为了维护规则//需要以g右旋g,u,p均变色else{//在左边if(curparent-_left){// g// p u// cRotateR(grandfather);//将g右旋p为父p变黑g变红这里P肯定是红的,循环条件parent-_colBLACK;grandfather-_colRED;}else//在右边{// g// p u// cRotateL(parent);//先左旋再右旋将parent右边节点与parent左旋再一g右旋// g// c u// pRotateR(grandfather);// c// p g// ucur-_colBLACK;grandfather-_colRED;}break;}}else//差不多反着来{// g// u pNode*unclegrandfather-_left;// 叔叔存在且为红-》变色即可if(uncleuncle-_colRED){parent-_coluncle-_colBLACK;grandfather-_colRED;// 继续往上处理curgrandfather;parentcur-_parent;}else// 叔叔不存在或者存在且为黑{// 情况二叔叔不存在或者存在且为黑// 旋转变色// g// u p// cif(curparent-_right){RotateL(grandfather);parent-_colBLACK;grandfather-_colRED;}else{RotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}}_root-_colBLACK;// 修改9确保根节点为黑色returntrue;// 修改10添加返回值}//右旋voidRotateR(Node*parent){//subl是子节点subl右节点放parent左边parent的父节点换为subl,subl的右节点换为parent//如果parent为root则subl的父节点为null,不为root就换为parent之前的父节点Node*sublparent-_left;Node*sublRsubl-_right;parent-_leftsublR;if(sublR){sublR-_parentparent;}Node*pParentparent-_parent;// 修改11保存祖父节点subl-_rightparent;parent-_parentsubl;if(parent_root){_rootsubl;subl-_parentnullptr;}else{if(pParent-_leftparent){pParent-_leftsubl;// 修改12subL - subl}else{pParent-_rightsubl;// 修改13subL - subl}subl-_parentpParent;// 修改14subL - subl}}//左转和右转差不多voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*parentParentparent-_parent;subR-_leftparent;parent-_parentsubR;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentparentParent-_left){parentParent-_leftsubR;}else{parentParent-_rightsubR;}subR-_parentparentParent;}}void_InOrder(Node*root){if(rootnullptr){return;}_InOrder(root-_left);coutroot-_kv.first ;_InOrder(root-_right);}// 前序递归遍历boolCheck(Node*root,intblackNum,constintrefNum){if(rootnullptr){// 前序遍历走到空时意味着一条路径走完了//cout blackNum endl;if(refNum!blackNum){cout存在黑色结点的数量不相等的路径endl;returnfalse;}returntrue;}// 检查孩子不太方便因为孩子有两个且不一定存在反过来检查父亲就方便多了if(root-_colREDroot-_parentroot-_parent-_colRED){coutroot-_kv.first存在连续的红色结点endl;returnfalse;}if(root-_colBLACK){blackNum;}returnCheck(root-_left,blackNum,refNum)Check(root-_right,blackNum,refNum);}boolIsBalanceTree(){if(_rootnullptr)returntrue;if(_root-_colRED)returnfalse;// 参考值intrefNum0;Node*cur_root;while(cur){if(cur-_colBLACK){refNum;}curcur-_left;}returnCheck(_root,0,refNum);}Node*getroot(){return_root;}private:Node*_rootnullptr;};
C++：红黑树实现
文章目录1 红黑树的概念1.1 红黑树五大规则1.2 最长路径不超过最短路径 2 倍2. 红黑树的底层实现2.1 初始框架2.2 红黑树的插入2.2.1 情况一仅变色2.2.2 情况二单旋变色2.2.3 双旋变色2.3 左右旋代码分享3. 整体代码1 红黑树的概念红黑树是一棵二叉搜索树每个节点额外存储颜色标识颜色分为红色、黑色两种。红黑树通过约束根到叶子路径上的节点颜色保证任意一条路径的长度不会超过其他路径的2倍属于近似平衡二叉树。1.1 红黑树五大规则每个节点的颜色只能是红色或黑色。根节点必须为黑色。若一个节点为红色则其两个子节点都必须是黑色路径中不存在连续红色节点。对于任意节点从该节点出发到所有空NIL节点的每条路径包含的黑色节点数量相同。所有空节点NIL/外部节点均为黑色。补充说明此处的叶子特指空NIL节点外部节点并非传统意义上的实际叶子节点部分代码实现中会省略对NIL节点的显性处理了解概念即可。这里给几个红黑树图例帮助理解1.2 最长路径不超过最短路径 2 倍红黑树依靠自身五大约束保证最长路径≤最短路径的2倍所有根到空节点的路径黑节点数量一致黑高bh全黑路径即为最短路径长度等于bh。规则禁止连续红节点路径中红节点必须与黑节点相间排列。极限情况下每条黑节点后搭配一个红节点最长路径长度为2bh。综上任意路径长度介于bh与2bh之间因此最长路径不会超过最短路径的2倍。2. 红黑树的底层实现2.1 初始框架// 枚举值表示颜色enumColour{RED,BLACK};// 这里我们默认按key/value结构实现templateclass K,class VstructRBTreeNode{// 这里更新控制平衡也要加入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){}};templateclass K,class Vclass RBTree{typedefRBTreeNodeK,VNode;public:private:Node*_rootnullptr;};2.2 红黑树的插入红黑树的插入分三种情况我们需要在每次插入式考虑红黑树的4条规则。大概有以下内容1.空树插入新增结点为黑色结点。2.非空树插入新增结点必须为红色结点若插入黑色结点会直接破坏红黑树规则 4每条路径黑结点数量相同该规则极难维护因此非空插入默认染红。3.非空树插入后新增结点为红色若父结点是黑色未违反任何红黑树规则插入直接结束。4.非空树插入后新增结点为红色若父结点是红色违反红黑树规则 3红色结点不能有红色子结点即无连续红结点此时可确定固定颜色当前结点红、父结点红、祖父结点黑最终调整方案完全由叔叔结点u 的颜色决定需分情况处理。2.2.1 情况一仅变色只要叔叔节点 u 是红色就只变色、不旋转这其实很好理解。为什么这种情况只变色、不旋转因为叔叔 u 是红色 → 变色就能直接修复连续红还能保持黑高不变。完整逻辑链c红、p红、g黑、u红出现了连续红c-p违反规则。p 和 u 都是红色、且都是 g 的孩子把p、u 同时变黑→ 两条子树的黑高各 1为了保持整棵树黑高不变把g 变红→ g 所在路径黑高 -1→ 整体黑高恢复平衡连续红消失了黑高也没变→完全不需要旋转这里给出图例代码实现if(uncleuncle-_colRED)// 修改8 RED - RED{parent-_coluncle-_colBLACK;grandfather-_colRED;//继续往上处理curgrandfather;parentcur-_parent;}2.2.2 情况二单旋变色情况叔叔 u 为黑 / 不存在前提条件当前节点c红色父节点p红色祖父节点g黑色叔叔节点u不存在或存在且为黑色关键推论u不存在 → c一定是新增节点u存在且为黑 → c一定不是新增节点是之前变色后向上更新上来的核心分析存在连续红色节点c-p违规单纯变色无法修复黑高平衡必须采用旋转 变色组合处理具体处理规则1.左左情况p是g的左孩子c是p的左孩子操作以g为支点执行右单旋变色p变黑g变红结果p成为子树根节点黑高不变无连续红节点无需向上更新右右情况p是g的右孩子c是p的右孩子操作以g为支点执行左单旋变色p变黑g变红结果p成为子树根节点黑高不变无连续红节点无需向上更新给个示例代码分享//在左边if(curparent-_left){// g// p u// cRotateR(grandfather);//将g右旋p为父p变黑g变红这里P肯定是红的,循环条件parent-_colBLACK;grandfather-_colRED;}左右旋代码后面给出。2.2.3 双旋变色父子节点呈折线、叔叔节点为空或黑色时执行双旋。前提条件当前节点c红色父节点p红色祖父节点g黑色叔叔节点u不存在或存在且为黑色关键推论u不存在 → c 一定是新增节点u存在且为黑 → c 一定不是新增节点是子树插入后经变色向上更新而来核心分析存在c-p连续红色节点违规单纯变色无法修复黑高必须旋转变色1. 左右情况p是g的左孩子c是p的右孩子以p为支点执行左单旋以g为支点执行右单旋变色c变黑g变红结果c成为子树根黑高不变无连续红节点无需向上更新2. 右左情况p是g的右孩子c是p的左孩子以p为支点执行右单旋以g为支点执行左单旋变色c变黑g变红结果c成为子树根黑高不变无连续红节点无需向上更新核心叔叔红只变色叔叔黑/无则旋转加变色。示例代码分享else//在右边{// g// p u// cRotateL(parent);//先左旋再右旋将parent右边节点与parent左旋再一g右旋// g// c u// pRotateR(grandfather);// c// p g// ucur-_colBLACK;grandfather-_colRED;}2.3 左右旋代码分享//右旋voidRotateR(Node*parent){//subl是子节点subl右节点放parent左边parent的父节点换为subl,subl的右节点换为parent//如果parent为root则subl的父节点为null,不为root就换为parent之前的父节点Node*sublparent-_left;Node*sublRsubl-_right;parent-_leftsublR;if(sublR){sublR-_parentparent;}Node*pParentparent-_parent;// 修改11保存祖父节点subl-_rightparent;parent-_parentsubl;if(parent_root){_rootsubl;subl-_parentnullptr;}else{if(pParent-_leftparent){pParent-_leftsubl;// 修改12subL - subl}else{pParent-_rightsubl;// 修改13subL - subl}subl-_parentpParent;// 修改14subL - subl}}//左转和右转差不多voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*parentParentparent-_parent;subR-_leftparent;parent-_parentsubR;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentparentParent-_left){parentParent-_leftsubR;}else{parentParent-_rightsubR;}subR-_parentparentParent;}}3. 整体代码#pragmaonce#includeiostreamusing namespace std;// 枚举值表示颜色enumColour{RED,BLACK};// 这里我们默认按key/value结构实现templateclass K,class VstructRBTreeNode{// 这里更新控制平衡也要加入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){}};templateclass K,class Vclass RBTree{typedefRBTreeNodeK,VNode;public:boolInsert(constpairK,Vkv){//先来个根节点if(_rootnullptr){// 修改1null - nullptr_rootnewNode(kv);//这里是指针_root-_colBLACK;returntrue;}Node*parentnullptr;// 修改2NULL - nullptrNode*cur_root;//找到插入位置while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}//开始插入(一般插入为红设计上选红色代价最小、最好调//这里cur还是空这里实例化curnewNode(kv);cur-_colRED;//因为之前cur是空指针所以需要重新关联父节点if(parent-_kv.firstkv.first){// 修改3parent-kv.first - parent-_kv.firstparent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;// 修改4插入后设置父节点指针//这里已经插入节点但还需要通过旋转来维护红黑树规则while(parentparent-_colRED){//定义个爷便于找Node*grandfatherparent-_parent;// 修改5parent-_right - parent-_parent//parent在g左边if(parentgrandfather-_left)// 修改6grandfather-_right - grandfather-_left{Node*unclegrandfather-_right;// 修改7grandfather-_right - grandfather-_right保持但上面条件改了//叔节点在且为红与parent节点一样if(uncleuncle-_colRED)// 修改8 RED - RED{parent-_coluncle-_colBLACK;grandfather-_colRED;//继续往上处理curgrandfather;parentcur-_parent;}//uncle为空或为黑这个时候为了维护规则//需要以g右旋g,u,p均变色else{//在左边if(curparent-_left){// g// p u// cRotateR(grandfather);//将g右旋p为父p变黑g变红这里P肯定是红的,循环条件parent-_colBLACK;grandfather-_colRED;}else//在右边{// g// p u// cRotateL(parent);//先左旋再右旋将parent右边节点与parent左旋再一g右旋// g// c u// pRotateR(grandfather);// c// p g// ucur-_colBLACK;grandfather-_colRED;}break;}}else//差不多反着来{// g// u pNode*unclegrandfather-_left;// 叔叔存在且为红-》变色即可if(uncleuncle-_colRED){parent-_coluncle-_colBLACK;grandfather-_colRED;// 继续往上处理curgrandfather;parentcur-_parent;}else// 叔叔不存在或者存在且为黑{// 情况二叔叔不存在或者存在且为黑// 旋转变色// g// u p// cif(curparent-_right){RotateL(grandfather);parent-_colBLACK;grandfather-_colRED;}else{RotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}}_root-_colBLACK;// 修改9确保根节点为黑色returntrue;// 修改10添加返回值}//右旋voidRotateR(Node*parent){//subl是子节点subl右节点放parent左边parent的父节点换为subl,subl的右节点换为parent//如果parent为root则subl的父节点为null,不为root就换为parent之前的父节点Node*sublparent-_left;Node*sublRsubl-_right;parent-_leftsublR;if(sublR){sublR-_parentparent;}Node*pParentparent-_parent;// 修改11保存祖父节点subl-_rightparent;parent-_parentsubl;if(parent_root){_rootsubl;subl-_parentnullptr;}else{if(pParent-_leftparent){pParent-_leftsubl;// 修改12subL - subl}else{pParent-_rightsubl;// 修改13subL - subl}subl-_parentpParent;// 修改14subL - subl}}//左转和右转差不多voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*parentParentparent-_parent;subR-_leftparent;parent-_parentsubR;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentparentParent-_left){parentParent-_leftsubR;}else{parentParent-_rightsubR;}subR-_parentparentParent;}}void_InOrder(Node*root){if(rootnullptr){return;}_InOrder(root-_left);coutroot-_kv.first ;_InOrder(root-_right);}// 前序递归遍历boolCheck(Node*root,intblackNum,constintrefNum){if(rootnullptr){// 前序遍历走到空时意味着一条路径走完了//cout blackNum endl;if(refNum!blackNum){cout存在黑色结点的数量不相等的路径endl;returnfalse;}returntrue;}// 检查孩子不太方便因为孩子有两个且不一定存在反过来检查父亲就方便多了if(root-_colREDroot-_parentroot-_parent-_colRED){coutroot-_kv.first存在连续的红色结点endl;returnfalse;}if(root-_colBLACK){blackNum;}returnCheck(root-_left,blackNum,refNum)Check(root-_right,blackNum,refNum);}boolIsBalanceTree(){if(_rootnullptr)returntrue;if(_root-_colRED)returnfalse;// 参考值intrefNum0;Node*cur_root;while(cur){if(cur-_colBLACK){refNum;}curcur-_left;}returnCheck(_root,0,refNum);}Node*getroot(){return_root;}private:Node*_rootnullptr;};
