红黑树的删除红黑树删除极其复杂,实现难度比AVL树删除更大要考虑的各种分支情况繁多编程实现时在琐碎的细节上容易出错但只要用心正确实现删除算法不难对红黑树按对二叉搜索树执行删除的方式执行删除,如果实际删除的节点是红节点,按正常方式删除删除后原树仍为红黑树结束若实际删除的是黑节点该节点有父节点并且有唯一子女节点且该子女节点为红将该子女节点染黑,并按对二叉搜索树执行删除的方式删掉实际删除的节点即可结束若实际删除黑节点该节点有父节点没有子女节点直接删除实际删除节点将父节点对应指针域置空令g父节点,unullptr若实际删除黑节点该节点有父节点有唯一女节点该子女节点为黑则按对二叉搜索树执行删除的方式正常执行删除并令g实际删除节点父节点 u实际删除节点子女节点若实际删除黑节点该节点没有父节点若该节点没有子树直接删除啦若该节点有左子树没有右子树删除该黑节点然后若左子树根节点为红染黑结束 无左子树有右子树类似至于既有左子树又有右子树的情形已经被之前所述情形包括在内了不用考虑经过上述步骤后如果删除操作未结束我们有子树gg为其根节点,u为g左子树或右子树根节点,注意u可能为nullptr即外节点而且可以发现u子树满足条件A:在u中删除一个节点并在u中做或不做颜色调整和平衡化旋转后根节点u为黑色,从原红黑树根节点到子树u各外节点的路径上黑色节点(不包括原红黑树根节点)数目比删除前原红黑树黑高度小一,从根节点u至子树u各外节点的路径上没有两个连续的红色节点,子树u为二叉搜索树,子树u的节点非红即黑现设有执行删除操作的红黑树的子树gg为其根节点以u为根节点的子树为g左子树或右子树,u可以为nullptr并且u子树满足条件A首先注意任意非外节点的节点都有两个子女两个子女要么都是外节点要么其中一个是要么都不是当然了红色节点都不是外节点所以必有两个子女黑色节点可能为也可能不为外节点若u为g的右子女则有以下几种情形g的左子女v为黑色,g为红色此时v不可能是外节点,若v是外节点注意原红黑树根节点到外节点v的路径上黑色节点(不包括原红黑树根节点)数目等于删除前原红黑树黑高度r,而原红黑树根节点到子树u的各外节点的路径上黑色节点(不包括原红黑树根节点)数目等于r-1(子树u满足条件A),因此g到v路径(节点g不算在内)上黑色节点数目减一即为g到子树u各外节点的路径(节点g不算在内)上黑色节点数目由假设v是外节点故g到v路径(节点g不算在内)上黑色节点数目为1因此g到子树u各外节点的路径(节点g不算在内)上黑色节点数目为0这是不可能的因为u为黑色v不是外节点所以有左子女w,这里若w为红色即如上图所示此时交换g,w和v的颜色,对子树g右单旋转,然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为黑色,g为红色,v的左子女w为黑色,v的有子女r为红色对g先左后右双旋转,将g染黑,然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为黑色,g为红色,v的左子女w为黑色,v的有子女r为黑色,此时交换g,v颜色然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为黑色,g为黑色,v(由上述理由它不是外节点)的左子女w为红色,此时对g右单旋转然后将w染黑然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为黑色,g为黑色,v的左子女w为黑色,v的右子女r为红色,此时对g做先左后右双旋转然后将r染黑,然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为黑色,g为黑色,v的左子女w为黑色,v的右子女r为黑色,此时对g作右单旋转,并将g染红色于是根据子树u满足条件A不难验证g树旋转后为红黑树而且恰好满足条件A那么若旋转后的g树的根已为执行删除操作的红黑树根节点则可以结束平衡化过程,若不为根节点由于旋转后的g树满足条件A所以原红黑树仍然不平衡于是令u旋转后g树根节点 g旋转前g树根节点父节点,回溯至上一层按所列各情形执行平衡化这样做是合理的因为旋转后的g树满足条件A。g的左子女v为红色,g为黑色,v的右子女r为黑色(显然),按和上述同样的理由r不可能是外节点,所以r必有左子女s,若s为红色,则对g做先左后右双旋转,将s染黑,然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为红色,g为黑色,v的右子女r为黑色,r的左子女s为黑色,r的右子女t为红色,此时对子树r做左单旋转,旋转完后将其根节点链接至v的右指针域,然后对子树g做先左后右双旋转并把t染成黑色然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为红色,g为黑色,v的右子女r为黑色,r的左子女s为黑色,r的右子女t为黑色,此时对子树g做右单旋转并交换v和r的颜色然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束若u为g的右子女则有如下几种情形这些情形和u为g的右子女时对应的情形是对称的以下所列这些情形从上之下依次和上文所列各情形从上至下保持对应的对称关系平衡化操作和颜色调整操作也保持对应颜色调整操作不便平衡化操作正好相反分析是类似就不一一分析只简单地列出平衡化操作的类型和颜色调整操作。g左单旋转,交换w,g和v颜色,结束g先右后左双旋转,g染黑结束交换g,v颜色,结束g左单旋转,w染黑,结束g先右后左双旋转,r染黑结束g左单旋转,g染红,若旋转后的g树的根已为执行删除操作的红黑树根节点,结束否则令u旋转后g树根节点 g旋转前g树根节点父节点,回溯至上一层按所列各情形执行平衡化g先右后左双旋转,s染黑,结束r右单旋转,g先右后左双旋转,t染黑结束g左单旋转,改变u和r的颜色,结束从以上讨论就可以看出循环不变量了它就是u子树满足的条件A利用该循环不变量结合前面的介绍和博主所写的AVL树插入删除算法分析一文中的分析思路就可总结出红黑树的删除算法这里省略可自行分析。红黑树删除算法的具体实现请参考下方代码。下面讨论红黑树的插入在空树中插入可直接插入再把插入节点染黑如果在非空红黑树中插入设插入的新节点为uu在节点p下插入那么无论u是在p的左子树还是右子树中插入,以u为根的子树(左右子树为外节点)总满足以下条件B按对二叉搜索树执行插入的方式在子树u中插入新节点后在u中做或不做颜色调整及平衡化旋转后子树u根节点u为红色从执行插入操作的红黑树根节点至子树u各外节点的路径上黑色节点(不包括该红黑树根节点)的数目都等于插入前原红黑树的黑高度u至子树u任意外节点的路径上没有两个连续的红色节点,子树u为二叉搜索树,子树u所有节点非红即黑。先设有执行插入操作的红黑树的子树u它满足条件B,u的父节点为p,u为p的左子女或右子女。若u为p的左子女则有如下几种情形p为黑色,此时由子树u满足条件B不难验证执行插入操作的红黑树已恢复平衡结束平衡化过程p为红色,由原红黑树的特性知p有父节点g,p为g的左子女g为黑色,若g的右子女r为红色则交换g和p,r的颜色若g已为执行插入操作的红黑树的根节点则将g染黑此时由子树u满足条件B不难验证子树g为红黑树于是结束平衡化过程 。若g不为执行插入操作的红黑树的根节点由子树u满足条件B不难验证此时子树g满足条件B但g的颜色由黑变红意味着g和其父节点有可能组成一对连续红节点所以此时应令ug pg的父节点回溯至上一层按所列各情形进行相同的平衡化处理以消除可能出现的一对连续红色节点这样做是合理的因为交换颜色后的子树g满足条件B。p为红色,由原红黑树的特性知p有父节点g,p为g的右子女g为黑色,若g的左子女r为红色则同样交换g和p,r的颜色和上一情形类似若g已为执行插入操作的红黑树的根节点则将g染黑结束。若g不为执行插入操作的红黑树的根节点,则令ug pg的父节点回溯至上一层按所列各情形进行相同的平衡化处理p为红色,由原红黑树的特性知p有父节点g,p为g的左子女g为黑色,g的右子女r为黑色此时g做右单旋转并交换p,g颜色然后由子树u满足条件B不难验证此时执行插入操作的红黑树已恢复红黑树特性结束平衡化过程。p为红色,p有父节点g,p为g的右子女g为黑色,g的左子女r为黑色此时对g先右后左双旋转并交换v,g颜色然后由子树u满足条件B不难验证此时执行插入操作的红黑树已恢复红黑树特性结束平衡化过程。若u为p的右子女也有类似诸情形这些情形和以上对应各情形保持对称每一种情形和其对应的以上情形相比颜色调整操作不便旋转操作互为镜像下面将这些情形及相应的处理方式列出这些情形从上至下和上述情形从上至下保持对应和对称p为黑色已平衡结束p为红色,由原红黑树的特性知p有父节点g,p为g的右子女g为黑色,若g的左子女r为红色则交换g和p,r颜色,若g已为执行插入操作的红黑树的根节点则将g染黑结束平衡化过程 。若g不为执行插入操作的红黑树的根节点令ug pg的父节点回溯至上一层按所列各情形进行相同的平衡化处理p为红色,由原红黑树的特性知p有父节点g,p为g的左子女g为黑色,若g的右子女r为红色则同样交换g和p,r颜色然后若g已为执行插入操作的红黑树的根节点则将g染黑结束。若g不为执行插入操作的红黑树的根节点,则令ug pg的父节点回溯至上一层按所列各情形进行相同的平衡化处理p为红色,由原红黑树的特性知p有父节点g,p为g的右子女g为黑色,g的左子女r为黑色此时g做左单旋转并交换p,g颜色然后已平衡结束平衡化过程。p为红色,p有父节点g,p为g的左子女g为黑色,g的右子女r为黑色此时对g先左后右双旋转并交换v,g颜色然后结束平衡化过程。从以上讨论就可以看出循环不变量就是u子树满足的条件B由此可总结出红黑树的插入算法这里省略可自行分析。红黑树插入算法的具体实现请参考下方代码。下面是实现红黑树插入与删除操作的具体代码(c),代码中加入了判断节点颜色非红即黑的二叉树是否为红黑树的函数用其在每次插入删除成功后检验插入删除后的二叉树是否仍为红黑树以判断插入删除算法的正确性#include string #include vector #include iostream #include stack #include random #include ctime using namespace std; #define TYPE int enum ColorFlag { RED, BLACK }; template typename T struct RBTreeNode { T data; //节点数据域 ColorFlag color; //节点颜色 RBTreeNode* left; RBTreeNode* right; RBTreeNode(T d, ColorFlag c) :data(d), color(c), left(nullptr), right(nullptr) {} }; template typename T void RotateLR(RBTreeNodeT* ptr) //对以ptr为根的子树执行先左后右双旋转,ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-left; RBTreeNodeT* q p-right; p-right q-left; q-left p; ptr-left q-right; q-right ptr; ptr q; } template typename T void RotateRL(RBTreeNodeT* ptr) //对以ptr为根的子树执行先右后左双旋转,ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-right; RBTreeNodeT* q p-left; p-left q-right; q-right p; ptr-right q-left; q-left ptr; ptr q; } template typename T void RotateR(RBTreeNodeT* ptr) //对以ptr为根的子树执行右单旋转,ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-left; ptr-left p-right; p-right ptr; ptr p; } template typename T void RotateL(RBTreeNodeT* ptr) ////对以ptr为根的子树执行左单旋转,ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-right; ptr-right p-left; p-left ptr; ptr p; } bool examineBlackHeight(bool TF, int preroadblacknum, const int blacknum) { if (TF false) { TF true; preroadblacknum blacknum; } else { if (preroadblacknum ! blacknum) { cout 从根节点到外节点的路径上黑节点数目不等,非红黑树 endl; return false; } } return true; } template typename T void addBlackNum(RBTreeNodeT* ptr, int blacknum) { if (ptr-color ColorFlag::BLACK) blacknum; } template typename T void reduceBlackNum(RBTreeNodeT* ptr, int blacknum) { if (ptr-color ColorFlag::BLACK) --blacknum; } template typename T bool isRB(RBTreeNodeT* root) //判断以root为根的二叉树是否为红黑树(已假定节点颜色不是为红色就是为黑色) { if (root-color ColorFlag::RED) { cout 根节点不为黑色,非红黑树 endl; return false; } struct memory { RBTreeNodeT* p; int direction; T lmin; memory(RBTreeNodeT* p, int d) :p(p), direction(d) {} }; T lmax; T rmin; T rmax; int d 0; RBTreeNodeT* ptr root; RBTreeNodeT* const dest ptr; stackmemory arrange; bool TF false; int blacknum 0; //统计路径上黑节点个数的变量 int preroadblacknum 0; //当前路径的前一路径上黑节点数目 while (true) { int result; if ((result Searchd(ptr, d)) 0) { if (ptr dest) { if (d 0) return true; } if (d 0) { addBlackNum(ptr, blacknum); if (examineBlackHeight(TF, preroadblacknum, blacknum) false) return false; if (arrange.top().direction 1) { arrange.top().lmin ptr-data; lmax ptr-data; } else { rmin ptr-data; rmax ptr-data; } } else { if (d 1) { if (lmax ptr-data) { cout 当前树非二叉搜索树,也非红黑树 endl; return false; } if (ptr dest) return true; T lmin arrange.top().lmin; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; lmax ptr-data; } else { rmin lmin; rmax ptr-data; } } else { if (rmin ptr-data) { cout 当前树非二叉搜索树,也非红黑树 endl; return false; } if (ptr dest) return true; if (ptr-left nullptr) { arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin ptr-data; lmax rmax; } else rmin ptr-data; } else { T lmin arrange.top().lmin; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; lmax rmax; } else rmin lmin; } } } reduceBlackNum(ptr, blacknum); ptr arrange.top().p; d arrange.top().direction; } else { RBTreeNodeT* interval nullptr; if (d 0) { if (ptr-color ColorFlag::RED) { if (result 2) { if (ptr-right-color ColorFlag::RED) { cout 在根节点到外节点的路径上存在两个连续红色节点,非红黑树 endl; return false; } } else { if (ptr-left-color ColorFlag::RED || ptr-right ! nullptr ptr-right-color ColorFlag::RED) { cout 在根节点到外节点的路径上存在两个连续红色节点,非红黑树 endl; return false; } } } else blacknum; if (ptr-left nullptr || ptr-right nullptr) { if (examineBlackHeight(TF, preroadblacknum, blacknum) false) return false; } arrange.push(memory(ptr, result)); if (arrange.top().direction 1) ptr ptr-left; else ptr ptr-right; } else { if (ptr-data lmax) { cout 当前树非二叉搜索树,也非红黑树 endl; return false; } arrange.top().direction 2; ptr ptr-right; } d 0; } } } template typename T void linkWithUpper(RBTreeNodeT* parent, RBTreeNodeT* original, RBTreeNodeT* _new) { if (original parent-left) { parent-left _new; } else { parent-right _new; } } template typename T bool executeDelete(RBTreeNodeT* p, RBTreeNodeT* q) { p-data q-data; if (q-color ColorFlag::RED) //如果被删节点为红色,直接删除即可 { delete q; return true; //已平衡返回根节点 } if (q-right ! nullptr q-right-color ColorFlag::RED) //被删节点右子树根节点为红色 //右子树根节点染黑,删除被删节点,红黑树恢复平衡,结束 { q-right-color ColorFlag::BLACK; delete q; return true; } //或被删节点及其右子女均为黑色,直接删除被删节点//被删节点为叶子黑节点,直接删除,子树q满足循环不变条件,向下进入do-while循环 delete q; return false; } template typename T RBTreeNodeT* executeDelete(RBTreeNodeT*p, RBTreeNodeT* root, RBTreeNodeT* stackforflashback_top, RBTreeNodeT* p_left_or_right) { if (stackforflashback_top ! nullptr) //被删节点有父节点 { if (stackforflashback_top-left p) stackforflashback_top-left p_left_or_right; //将被删节点左子树或右子树链接至被删节点父节点相应链指针 else stackforflashback_top-right p_left_or_right; //被删节点一定为黑其左子女一定为红,左子女染黑,删除被删节点,已平衡返回根节点 } else //被删节点为根节点且只有左子树或只有右子树 root p_left_or_right; //直接删除被删节点,左子女直接染黑,这样左子树为红黑树,结束 p_left_or_right-color ColorFlag::BLACK; delete p; return root; } template typename T RBTreeNodeT* DelRB(RBTreeNodeT* root, T key) { //红黑树删除 RBTreeNodeT* p root; stackRBTreeNodeT* stackforflashback; while (p ! nullptr) //搜索被删除节点,同时将回溯路径记录在栈中 { if (p-data key) break; else { stackforflashback.push(p); if (key p-data) { p p-left; } else { p p-right; } } } if (p ! nullptr) //被删除节点存在,被p指向 { RBTreeNodeT* parent nullptr; RBTreeNodeT* q nullptr; if (p-left ! nullptr p-right ! nullptr) //被删节点左右子树均存在 { q p-right; parent p; if (q-left ! nullptr) //被删节点右子树根节点有左子树 { while (q-left ! nullptr) //在被删节点右子树根节点左子树中搜索中序遍历的第一个节点,同时用栈记录回溯路径 { stackforflashback.push(parent); parent q; q q-left; } parent-left q-right; //用该节点数据域替换被删节点数据域,将其右子树链接至其父节点左链指针 if (executeDelete(p, q)) return root; q parent-left; //parent为需要做或不做平衡化旋转及颜色调整的第一棵子树根节点指针,q为该子树左子树根节点指针 } else { p-right q-right; //用被删节点右子女数据域替换被删节点指针域,将右子女右子树链接至被删节点右链指针 if (executeDelete(p, q)) return root; q p-right; //parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树根节点指针 } } else { if (p-left ! nullptr) //被删节点左子树不空,右子树空 return executeDelete(p, root, stackforflashback.empty() ? nullptr : stackforflashback.top(), p-left); if (p-right ! nullptr) //处理过程和以上情形完全对称{ return executeDelete(p, root, stackforflashback.empty() ? nullptr : stackforflashback.top(), p-right); //被删节点为叶节点 if (stackforflashback.empty()) { delete p; //被删叶节点为根节点,直接删除,结束 return nullptr; } parent stackforflashback.top(); //被删叶节点有父节点 stackforflashback.pop(); if (parent-left p) parent-left nullptr; else //将叶节点的父节点对应指针域置空 parent-right nullptr; q nullptr; if (p-color ColorFlag::RED) { delete p; return root; } delete p; //被删叶节点为黑,直接删除,此时q为需要做或不做平衡化旋转和颜色调整的第一棵子树根节点指针,q子树满足循环不变条件,向下进入do-while循环 } enum class condition_be_processed {C1, C2, C3, C4, C5, C6, C7, C8, C9, _C1, _C10, _C3, _C4, _C5, _C6, _C7, _C8, _C9} distinguish; bool TF false; do //do-while循环所做工作是,从满足循环不变条件的第一棵子树起,沿父节点到第一棵子树根节点的路径向上平衡化旋转或调整颜色,直到原红黑树重新恢复平衡为止 { if (TF true) { linkWithUpper(stackforflashback.top(), q, parent); if (q-color ! ColorFlag::RED) return root; q parent; parent stackforflashback.top(); stackforflashback.pop(); } else TF true; if (parent-right q) { p parent-left; if (parent-color ColorFlag::RED) { if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::C1; else if(p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::C2; else distinguish condition_be_processed::C3; } else { if (p-color ColorFlag::BLACK) { if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::C4; else if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::C5; else distinguish condition_be_processed::C6; } else { q p-right; if (q-left ! nullptr q-left-color ColorFlag::RED) distinguish condition_be_processed::C7; else if (q-right ! nullptr q-right-color ColorFlag::RED) distinguish condition_be_processed::C8; else distinguish condition_be_processed::C9; } } } else { p parent-right; if (parent-color ColorFlag::RED) { if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::_C1; else if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::_C10; else distinguish condition_be_processed::_C3; } else { if (p-color ColorFlag::BLACK) { if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::_C4; else if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::_C5; else distinguish condition_be_processed::_C6; } else { q p-left; if (q-right ! nullptr q-right-color ColorFlag::RED) distinguish condition_be_processed::_C7; else if (q-left ! nullptr q-left-color ColorFlag::RED) distinguish condition_be_processed::_C8; else distinguish condition_be_processed::_C9; } } } if (distinguish condition_be_processed::C1 || distinguish condition_be_processed::_C1 || distinguish condition_be_processed::C2 || distinguish condition_be_processed::_C10) { q parent; parent-color ColorFlag::BLACK; if (distinguish condition_be_processed::C1 || distinguish condition_be_processed::_C1) { p-color ColorFlag::RED; if (distinguish condition_be_processed::C1) { p-left-color ColorFlag::BLACK; RotateR(parent); } else { p-right-color ColorFlag::BLACK; RotateL(parent); } } else { if (distinguish condition_be_processed::C2) RotateLR(parent); else RotateRL(parent); } } else if (distinguish condition_be_processed::C3 || distinguish condition_be_processed::_C3) { parent-color ColorFlag::BLACK; p-color ColorFlag::RED; return root; } else if (distinguish condition_be_processed::C4 || distinguish condition_be_processed::_C4) { q parent; if (distinguish condition_be_processed::C4) { p-left-color ColorFlag::BLACK; RotateR(parent); } else { p-right-color ColorFlag::BLACK; RotateL(parent); } } else if (distinguish condition_be_processed::C5 || distinguish condition_be_processed::_C5) { q parent; if (distinguish condition_be_processed::C5) { p-right-color ColorFlag::BLACK; RotateLR(parent); } else { p-left-color ColorFlag::BLACK; RotateRL(parent); } } else if (distinguish condition_be_processed::C6 || distinguish condition_be_processed::_C6) { q parent; parent-color ColorFlag::RED; if (distinguish condition_be_processed::C6) RotateR(parent); else RotateL(parent); } else if (distinguish condition_be_processed::C7 || distinguish condition_be_processed::_C8) { q-left-color ColorFlag::BLACK; q parent; if (distinguish condition_be_processed::C7) RotateLR(parent); else { RotateR(p-left); RotateRL(parent); } } else if (distinguish condition_be_processed::_C7 || distinguish condition_be_processed::C8) { q-right-color ColorFlag::BLACK; q parent; if (distinguish condition_be_processed::_C7) RotateRL(parent); else { RotateL(p-right); RotateLR(parent); } } else if (distinguish condition_be_processed::C9 || distinguish condition_be_processed::_C9) { p-color ColorFlag::BLACK; q-color ColorFlag::RED; q parent; if (distinguish condition_be_processed::C9) RotateR(parent); else RotateL(parent); } } while (stackforflashback.empty() false); parent-color ColorFlag::BLACK; return parent; } else { cout 红黑树中不存在要删除的数据元素,删除失败 endl; return nullptr; } } template typename T RBTreeNodeT* InsertRB(RBTreeNodeT* root, T key) { //红黑树插入 if (root nullptr) return new RBTreeNodeT(key, ColorFlag::BLACK); else { stackRBTreeNodeT* stackforflashback; RBTreeNodeT* p root; while (p ! nullptr) //搜索插入位置 { stackforflashback.push(p); if (key p-data) p p-left; else if (key p-data) p p-right; else { cout 要插入的关键字在AVL树中已存在,插入失败 endl; return nullptr; } } if (key stackforflashback.top()-data) { p stackforflashback.top()-left new RBTreeNodeT(key, ColorFlag::RED); } else { p stackforflashback.top()-right new RBTreeNodeT(key, ColorFlag::RED); } enum class condition_be_processed {L1, L2, L3, _L1, _L2, _L3}distinguish; RBTreeNodeT* q nullptr; RBTreeNodeT* g nullptr; while (stackforflashback.empty() false) //从第一棵满足循环不变条件的子树(就是新插入的节点)开始逐步向上调整颜色或进行平衡化旋转,直到原红黑树重新恢复平衡为止 { if (g ! nullptr) { if (g-color ColorFlag::BLACK) { linkWithUpper(stackforflashback.top(), p, g); return root; } else p g; } q stackforflashback.top(); //进入新一轮循环后p为满足循环不变条件的子树的根节点,stackforflashback栈顶指针为其父节点指针 stackforflashback.pop(); if (q-color ColorFlag::BLACK) return root; g stackforflashback.top(); stackforflashback.pop(); if (q g-left) { if (g-right ! nullptr g-right-color ColorFlag::RED) distinguish condition_be_processed::L1; else if (p q-left) distinguish condition_be_processed::L2; else distinguish condition_be_processed::L3; } else if (g-left ! nullptr g-left-color ColorFlag::RED) distinguish condition_be_processed::_L1; else if (p q-left) distinguish condition_be_processed::_L2; else distinguish condition_be_processed::_L3; g-color ColorFlag::RED; if (distinguish condition_be_processed::L1 || distinguish condition_be_processed::_L1) { q-color ColorFlag::BLACK; if (distinguish condition_be_processed::L1) g-right-color ColorFlag::BLACK; else g-left-color ColorFlag::BLACK; } else if (distinguish condition_be_processed::L2 || distinguish condition_be_processed::_L3) { q-color ColorFlag::BLACK; p g; if (distinguish condition_be_processed::L2) RotateR(g); else RotateL(g); } else if (distinguish condition_be_processed::_L2 || distinguish condition_be_processed::L3) { p-color ColorFlag::BLACK; p g; if (distinguish condition_be_processed::_L2) RotateRL(g); else RotateLR(g); } } g-color ColorFlag::BLACK; return g; } } template typename T int Searchd(RBTreeNodeT* ptr, int d) { if (d 2) return 0; else { if (d 1) { if (ptr-right nullptr) return 0; else return 2; } else { if (ptr-left ! nullptr) return 1; else { if (ptr-right ! nullptr) return 2; else return 0; } } } } template typename T void output(RBTreeNodeT* ptr) //输出以ptr为根的红黑树对应的广义表形式 { struct memory { RBTreeNodeT* p; int direction; int last; memory(RBTreeNodeT* p, int d, int l) :p(p), direction(d), last(l) {} }; int d 0; RBTreeNodeT* const dest ptr; stackmemory arrange; while (true) { if (Searchd(ptr, d) 0) { if (ptr dest) { if (d 0) cout ptr-data (; else { if (arrange.top().last 1) cout , ; } cout ); break; } else { if (d 0) { if (arrange.top().last 0) { if (arrange.top().direction 1) { cout ptr-data; arrange.top().last 1; } else { cout , ptr-data; arrange.top().last 2; } } else { cout ,; cout ptr-data; arrange.top().last 2; } } else { if (arrange.top().last 2) cout ); else { cout , ); } arrange.pop(); } ptr arrange.top().p; d arrange.top().direction; } } else { RBTreeNodeT* interval nullptr; if (d 0) { if (arrange.empty() false) { if (arrange.top().last 0) { if (arrange.top().direction 1) { cout ptr-data (; arrange.top().last 1; } else { cout , ptr-data (; arrange.top().last 2; } } else { cout ,; cout ptr-data (; arrange.top().last 2; } } else { cout ptr-data (; } arrange.push(memory(ptr, Searchd(ptr, d), 0)); if (arrange.top().direction 1) interval ptr-left; else interval ptr-right; } else { arrange.top().direction 2; interval ptr-right; } d 0; ptr interval; } } } int main() { const int N 1000; //vectorTYPE insertvalue{ 13, 2}; vectorTYPE insertvalue; for (int i 1; i N; i) { insertvalue.push_back(i); } shuffle(insertvalue.begin(), insertvalue.end(), default_random_engine()); RBTreeNodeTYPE* root nullptr; for (vectorTYPE::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { root InsertRB(root, *p); cout 插入 *p endl; //output(root); cout endl; if (isRB(root) true) { cout 当前树是红黑树; cout endl; } else { cerr 错误当前树不是红黑树! endl; exit(0); } } cout endl; //cout 插入完成后删除前红黑树对应的广义表形式为: endl; //output(root); cout endl; cout endl; for (vectorTYPE::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { cout 删除节点 *p endl; root DelRB(root, *p); if (root ! nullptr) { //output(root); cout endl; if (isRB(root) true) { cout 当前树是红黑树; cout endl; } else { cerr 错误当前树不是红黑树! endl; exit(0); } } else cout NULL; cout endl; } return 0; }
红黑树的删除红黑树删除极其复杂,实现难度比AVL树删除更大要考虑的各种分支情况繁多编程实现时在琐碎的细节上容易出错但只要用心正确实现删除算法不难对红黑树按对二叉搜索树执行删除的方式执行删除,如果实际删除的节点是红节点,按正常方式删除删除后原树仍为红黑树结束若实际删除的是黑节点该节点有父节点并且有唯一子女节点且该子女节点为红将该子女节点染黑,并按对二叉搜索树执行删除的方式删掉实际删除的节点即可结束若实际删除黑节点该节点有父节点没有子女节点直接删除实际删除节点将父节点对应指针域置空令g父节点,unullptr若实际删除黑节点该节点有父节点有唯一女节点该子女节点为黑则按对二叉搜索树执行删除的方式正常执行删除并令g实际删除节点父节点 u实际删除节点子女节点若实际删除黑节点该节点没有父节点若该节点没有子树直接删除啦若该节点有左子树没有右子树删除该黑节点然后若左子树根节点为红染黑结束 无左子树有右子树类似至于既有左子树又有右子树的情形已经被之前所述情形包括在内了不用考虑经过上述步骤后如果删除操作未结束我们有子树gg为其根节点,u为g左子树或右子树根节点,注意u可能为nullptr即外节点而且可以发现u子树满足条件A:在u中删除一个节点并在u中做或不做颜色调整和平衡化旋转后根节点u为黑色,从原红黑树根节点到子树u各外节点的路径上黑色节点(不包括原红黑树根节点)数目比删除前原红黑树黑高度小一,从根节点u至子树u各外节点的路径上没有两个连续的红色节点,子树u为二叉搜索树,子树u的节点非红即黑现设有执行删除操作的红黑树的子树gg为其根节点以u为根节点的子树为g左子树或右子树,u可以为nullptr并且u子树满足条件A首先注意任意非外节点的节点都有两个子女两个子女要么都是外节点要么其中一个是要么都不是当然了红色节点都不是外节点所以必有两个子女黑色节点可能为也可能不为外节点若u为g的右子女则有以下几种情形g的左子女v为黑色,g为红色此时v不可能是外节点,若v是外节点注意原红黑树根节点到外节点v的路径上黑色节点(不包括原红黑树根节点)数目等于删除前原红黑树黑高度r,而原红黑树根节点到子树u的各外节点的路径上黑色节点(不包括原红黑树根节点)数目等于r-1(子树u满足条件A),因此g到v路径(节点g不算在内)上黑色节点数目减一即为g到子树u各外节点的路径(节点g不算在内)上黑色节点数目由假设v是外节点故g到v路径(节点g不算在内)上黑色节点数目为1因此g到子树u各外节点的路径(节点g不算在内)上黑色节点数目为0这是不可能的因为u为黑色v不是外节点所以有左子女w,这里若w为红色即如上图所示此时交换g,w和v的颜色,对子树g右单旋转,然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为黑色,g为红色,v的左子女w为黑色,v的有子女r为红色对g先左后右双旋转,将g染黑,然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为黑色,g为红色,v的左子女w为黑色,v的有子女r为黑色,此时交换g,v颜色然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为黑色,g为黑色,v(由上述理由它不是外节点)的左子女w为红色,此时对g右单旋转然后将w染黑然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为黑色,g为黑色,v的左子女w为黑色,v的右子女r为红色,此时对g做先左后右双旋转然后将r染黑,然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为黑色,g为黑色,v的左子女w为黑色,v的右子女r为黑色,此时对g作右单旋转,并将g染红色于是根据子树u满足条件A不难验证g树旋转后为红黑树而且恰好满足条件A那么若旋转后的g树的根已为执行删除操作的红黑树根节点则可以结束平衡化过程,若不为根节点由于旋转后的g树满足条件A所以原红黑树仍然不平衡于是令u旋转后g树根节点 g旋转前g树根节点父节点,回溯至上一层按所列各情形执行平衡化这样做是合理的因为旋转后的g树满足条件A。g的左子女v为红色,g为黑色,v的右子女r为黑色(显然),按和上述同样的理由r不可能是外节点,所以r必有左子女s,若s为红色,则对g做先左后右双旋转,将s染黑,然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为红色,g为黑色,v的右子女r为黑色,r的左子女s为黑色,r的右子女t为红色,此时对子树r做左单旋转,旋转完后将其根节点链接至v的右指针域,然后对子树g做先左后右双旋转并把t染成黑色然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束g的左子女v为红色,g为黑色,v的右子女r为黑色,r的左子女s为黑色,r的右子女t为黑色,此时对子树g做右单旋转并交换v和r的颜色然后根据子树u满足条件A不难验证此时原树为红黑树已平衡结束若u为g的右子女则有如下几种情形这些情形和u为g的右子女时对应的情形是对称的以下所列这些情形从上之下依次和上文所列各情形从上至下保持对应的对称关系平衡化操作和颜色调整操作也保持对应颜色调整操作不便平衡化操作正好相反分析是类似就不一一分析只简单地列出平衡化操作的类型和颜色调整操作。g左单旋转,交换w,g和v颜色,结束g先右后左双旋转,g染黑结束交换g,v颜色,结束g左单旋转,w染黑,结束g先右后左双旋转,r染黑结束g左单旋转,g染红,若旋转后的g树的根已为执行删除操作的红黑树根节点,结束否则令u旋转后g树根节点 g旋转前g树根节点父节点,回溯至上一层按所列各情形执行平衡化g先右后左双旋转,s染黑,结束r右单旋转,g先右后左双旋转,t染黑结束g左单旋转,改变u和r的颜色,结束从以上讨论就可以看出循环不变量了它就是u子树满足的条件A利用该循环不变量结合前面的介绍和博主所写的AVL树插入删除算法分析一文中的分析思路就可总结出红黑树的删除算法这里省略可自行分析。红黑树删除算法的具体实现请参考下方代码。下面讨论红黑树的插入在空树中插入可直接插入再把插入节点染黑如果在非空红黑树中插入设插入的新节点为uu在节点p下插入那么无论u是在p的左子树还是右子树中插入,以u为根的子树(左右子树为外节点)总满足以下条件B按对二叉搜索树执行插入的方式在子树u中插入新节点后在u中做或不做颜色调整及平衡化旋转后子树u根节点u为红色从执行插入操作的红黑树根节点至子树u各外节点的路径上黑色节点(不包括该红黑树根节点)的数目都等于插入前原红黑树的黑高度u至子树u任意外节点的路径上没有两个连续的红色节点,子树u为二叉搜索树,子树u所有节点非红即黑。先设有执行插入操作的红黑树的子树u它满足条件B,u的父节点为p,u为p的左子女或右子女。若u为p的左子女则有如下几种情形p为黑色,此时由子树u满足条件B不难验证执行插入操作的红黑树已恢复平衡结束平衡化过程p为红色,由原红黑树的特性知p有父节点g,p为g的左子女g为黑色,若g的右子女r为红色则交换g和p,r的颜色若g已为执行插入操作的红黑树的根节点则将g染黑此时由子树u满足条件B不难验证子树g为红黑树于是结束平衡化过程 。若g不为执行插入操作的红黑树的根节点由子树u满足条件B不难验证此时子树g满足条件B但g的颜色由黑变红意味着g和其父节点有可能组成一对连续红节点所以此时应令ug pg的父节点回溯至上一层按所列各情形进行相同的平衡化处理以消除可能出现的一对连续红色节点这样做是合理的因为交换颜色后的子树g满足条件B。p为红色,由原红黑树的特性知p有父节点g,p为g的右子女g为黑色,若g的左子女r为红色则同样交换g和p,r的颜色和上一情形类似若g已为执行插入操作的红黑树的根节点则将g染黑结束。若g不为执行插入操作的红黑树的根节点,则令ug pg的父节点回溯至上一层按所列各情形进行相同的平衡化处理p为红色,由原红黑树的特性知p有父节点g,p为g的左子女g为黑色,g的右子女r为黑色此时g做右单旋转并交换p,g颜色然后由子树u满足条件B不难验证此时执行插入操作的红黑树已恢复红黑树特性结束平衡化过程。p为红色,p有父节点g,p为g的右子女g为黑色,g的左子女r为黑色此时对g先右后左双旋转并交换v,g颜色然后由子树u满足条件B不难验证此时执行插入操作的红黑树已恢复红黑树特性结束平衡化过程。若u为p的右子女也有类似诸情形这些情形和以上对应各情形保持对称每一种情形和其对应的以上情形相比颜色调整操作不便旋转操作互为镜像下面将这些情形及相应的处理方式列出这些情形从上至下和上述情形从上至下保持对应和对称p为黑色已平衡结束p为红色,由原红黑树的特性知p有父节点g,p为g的右子女g为黑色,若g的左子女r为红色则交换g和p,r颜色,若g已为执行插入操作的红黑树的根节点则将g染黑结束平衡化过程 。若g不为执行插入操作的红黑树的根节点令ug pg的父节点回溯至上一层按所列各情形进行相同的平衡化处理p为红色,由原红黑树的特性知p有父节点g,p为g的左子女g为黑色,若g的右子女r为红色则同样交换g和p,r颜色然后若g已为执行插入操作的红黑树的根节点则将g染黑结束。若g不为执行插入操作的红黑树的根节点,则令ug pg的父节点回溯至上一层按所列各情形进行相同的平衡化处理p为红色,由原红黑树的特性知p有父节点g,p为g的右子女g为黑色,g的左子女r为黑色此时g做左单旋转并交换p,g颜色然后已平衡结束平衡化过程。p为红色,p有父节点g,p为g的左子女g为黑色,g的右子女r为黑色此时对g先左后右双旋转并交换v,g颜色然后结束平衡化过程。从以上讨论就可以看出循环不变量就是u子树满足的条件B由此可总结出红黑树的插入算法这里省略可自行分析。红黑树插入算法的具体实现请参考下方代码。下面是实现红黑树插入与删除操作的具体代码(c),代码中加入了判断节点颜色非红即黑的二叉树是否为红黑树的函数用其在每次插入删除成功后检验插入删除后的二叉树是否仍为红黑树以判断插入删除算法的正确性#include string #include vector #include iostream #include stack #include random #include ctime using namespace std; #define TYPE int enum ColorFlag { RED, BLACK }; template typename T struct RBTreeNode { T data; //节点数据域 ColorFlag color; //节点颜色 RBTreeNode* left; RBTreeNode* right; RBTreeNode(T d, ColorFlag c) :data(d), color(c), left(nullptr), right(nullptr) {} }; template typename T void RotateLR(RBTreeNodeT* ptr) //对以ptr为根的子树执行先左后右双旋转,ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-left; RBTreeNodeT* q p-right; p-right q-left; q-left p; ptr-left q-right; q-right ptr; ptr q; } template typename T void RotateRL(RBTreeNodeT* ptr) //对以ptr为根的子树执行先右后左双旋转,ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-right; RBTreeNodeT* q p-left; p-left q-right; q-right p; ptr-right q-left; q-left ptr; ptr q; } template typename T void RotateR(RBTreeNodeT* ptr) //对以ptr为根的子树执行右单旋转,ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-left; ptr-left p-right; p-right ptr; ptr p; } template typename T void RotateL(RBTreeNodeT* ptr) ////对以ptr为根的子树执行左单旋转,ptr成为旋转后新树根节点指针 { RBTreeNodeT* p ptr-right; ptr-right p-left; p-left ptr; ptr p; } bool examineBlackHeight(bool TF, int preroadblacknum, const int blacknum) { if (TF false) { TF true; preroadblacknum blacknum; } else { if (preroadblacknum ! blacknum) { cout 从根节点到外节点的路径上黑节点数目不等,非红黑树 endl; return false; } } return true; } template typename T void addBlackNum(RBTreeNodeT* ptr, int blacknum) { if (ptr-color ColorFlag::BLACK) blacknum; } template typename T void reduceBlackNum(RBTreeNodeT* ptr, int blacknum) { if (ptr-color ColorFlag::BLACK) --blacknum; } template typename T bool isRB(RBTreeNodeT* root) //判断以root为根的二叉树是否为红黑树(已假定节点颜色不是为红色就是为黑色) { if (root-color ColorFlag::RED) { cout 根节点不为黑色,非红黑树 endl; return false; } struct memory { RBTreeNodeT* p; int direction; T lmin; memory(RBTreeNodeT* p, int d) :p(p), direction(d) {} }; T lmax; T rmin; T rmax; int d 0; RBTreeNodeT* ptr root; RBTreeNodeT* const dest ptr; stackmemory arrange; bool TF false; int blacknum 0; //统计路径上黑节点个数的变量 int preroadblacknum 0; //当前路径的前一路径上黑节点数目 while (true) { int result; if ((result Searchd(ptr, d)) 0) { if (ptr dest) { if (d 0) return true; } if (d 0) { addBlackNum(ptr, blacknum); if (examineBlackHeight(TF, preroadblacknum, blacknum) false) return false; if (arrange.top().direction 1) { arrange.top().lmin ptr-data; lmax ptr-data; } else { rmin ptr-data; rmax ptr-data; } } else { if (d 1) { if (lmax ptr-data) { cout 当前树非二叉搜索树,也非红黑树 endl; return false; } if (ptr dest) return true; T lmin arrange.top().lmin; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; lmax ptr-data; } else { rmin lmin; rmax ptr-data; } } else { if (rmin ptr-data) { cout 当前树非二叉搜索树,也非红黑树 endl; return false; } if (ptr dest) return true; if (ptr-left nullptr) { arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin ptr-data; lmax rmax; } else rmin ptr-data; } else { T lmin arrange.top().lmin; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; lmax rmax; } else rmin lmin; } } } reduceBlackNum(ptr, blacknum); ptr arrange.top().p; d arrange.top().direction; } else { RBTreeNodeT* interval nullptr; if (d 0) { if (ptr-color ColorFlag::RED) { if (result 2) { if (ptr-right-color ColorFlag::RED) { cout 在根节点到外节点的路径上存在两个连续红色节点,非红黑树 endl; return false; } } else { if (ptr-left-color ColorFlag::RED || ptr-right ! nullptr ptr-right-color ColorFlag::RED) { cout 在根节点到外节点的路径上存在两个连续红色节点,非红黑树 endl; return false; } } } else blacknum; if (ptr-left nullptr || ptr-right nullptr) { if (examineBlackHeight(TF, preroadblacknum, blacknum) false) return false; } arrange.push(memory(ptr, result)); if (arrange.top().direction 1) ptr ptr-left; else ptr ptr-right; } else { if (ptr-data lmax) { cout 当前树非二叉搜索树,也非红黑树 endl; return false; } arrange.top().direction 2; ptr ptr-right; } d 0; } } } template typename T void linkWithUpper(RBTreeNodeT* parent, RBTreeNodeT* original, RBTreeNodeT* _new) { if (original parent-left) { parent-left _new; } else { parent-right _new; } } template typename T bool executeDelete(RBTreeNodeT* p, RBTreeNodeT* q) { p-data q-data; if (q-color ColorFlag::RED) //如果被删节点为红色,直接删除即可 { delete q; return true; //已平衡返回根节点 } if (q-right ! nullptr q-right-color ColorFlag::RED) //被删节点右子树根节点为红色 //右子树根节点染黑,删除被删节点,红黑树恢复平衡,结束 { q-right-color ColorFlag::BLACK; delete q; return true; } //或被删节点及其右子女均为黑色,直接删除被删节点//被删节点为叶子黑节点,直接删除,子树q满足循环不变条件,向下进入do-while循环 delete q; return false; } template typename T RBTreeNodeT* executeDelete(RBTreeNodeT*p, RBTreeNodeT* root, RBTreeNodeT* stackforflashback_top, RBTreeNodeT* p_left_or_right) { if (stackforflashback_top ! nullptr) //被删节点有父节点 { if (stackforflashback_top-left p) stackforflashback_top-left p_left_or_right; //将被删节点左子树或右子树链接至被删节点父节点相应链指针 else stackforflashback_top-right p_left_or_right; //被删节点一定为黑其左子女一定为红,左子女染黑,删除被删节点,已平衡返回根节点 } else //被删节点为根节点且只有左子树或只有右子树 root p_left_or_right; //直接删除被删节点,左子女直接染黑,这样左子树为红黑树,结束 p_left_or_right-color ColorFlag::BLACK; delete p; return root; } template typename T RBTreeNodeT* DelRB(RBTreeNodeT* root, T key) { //红黑树删除 RBTreeNodeT* p root; stackRBTreeNodeT* stackforflashback; while (p ! nullptr) //搜索被删除节点,同时将回溯路径记录在栈中 { if (p-data key) break; else { stackforflashback.push(p); if (key p-data) { p p-left; } else { p p-right; } } } if (p ! nullptr) //被删除节点存在,被p指向 { RBTreeNodeT* parent nullptr; RBTreeNodeT* q nullptr; if (p-left ! nullptr p-right ! nullptr) //被删节点左右子树均存在 { q p-right; parent p; if (q-left ! nullptr) //被删节点右子树根节点有左子树 { while (q-left ! nullptr) //在被删节点右子树根节点左子树中搜索中序遍历的第一个节点,同时用栈记录回溯路径 { stackforflashback.push(parent); parent q; q q-left; } parent-left q-right; //用该节点数据域替换被删节点数据域,将其右子树链接至其父节点左链指针 if (executeDelete(p, q)) return root; q parent-left; //parent为需要做或不做平衡化旋转及颜色调整的第一棵子树根节点指针,q为该子树左子树根节点指针 } else { p-right q-right; //用被删节点右子女数据域替换被删节点指针域,将右子女右子树链接至被删节点右链指针 if (executeDelete(p, q)) return root; q p-right; //parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树根节点指针 } } else { if (p-left ! nullptr) //被删节点左子树不空,右子树空 return executeDelete(p, root, stackforflashback.empty() ? nullptr : stackforflashback.top(), p-left); if (p-right ! nullptr) //处理过程和以上情形完全对称{ return executeDelete(p, root, stackforflashback.empty() ? nullptr : stackforflashback.top(), p-right); //被删节点为叶节点 if (stackforflashback.empty()) { delete p; //被删叶节点为根节点,直接删除,结束 return nullptr; } parent stackforflashback.top(); //被删叶节点有父节点 stackforflashback.pop(); if (parent-left p) parent-left nullptr; else //将叶节点的父节点对应指针域置空 parent-right nullptr; q nullptr; if (p-color ColorFlag::RED) { delete p; return root; } delete p; //被删叶节点为黑,直接删除,此时q为需要做或不做平衡化旋转和颜色调整的第一棵子树根节点指针,q子树满足循环不变条件,向下进入do-while循环 } enum class condition_be_processed {C1, C2, C3, C4, C5, C6, C7, C8, C9, _C1, _C10, _C3, _C4, _C5, _C6, _C7, _C8, _C9} distinguish; bool TF false; do //do-while循环所做工作是,从满足循环不变条件的第一棵子树起,沿父节点到第一棵子树根节点的路径向上平衡化旋转或调整颜色,直到原红黑树重新恢复平衡为止 { if (TF true) { linkWithUpper(stackforflashback.top(), q, parent); if (q-color ! ColorFlag::RED) return root; q parent; parent stackforflashback.top(); stackforflashback.pop(); } else TF true; if (parent-right q) { p parent-left; if (parent-color ColorFlag::RED) { if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::C1; else if(p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::C2; else distinguish condition_be_processed::C3; } else { if (p-color ColorFlag::BLACK) { if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::C4; else if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::C5; else distinguish condition_be_processed::C6; } else { q p-right; if (q-left ! nullptr q-left-color ColorFlag::RED) distinguish condition_be_processed::C7; else if (q-right ! nullptr q-right-color ColorFlag::RED) distinguish condition_be_processed::C8; else distinguish condition_be_processed::C9; } } } else { p parent-right; if (parent-color ColorFlag::RED) { if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::_C1; else if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::_C10; else distinguish condition_be_processed::_C3; } else { if (p-color ColorFlag::BLACK) { if (p-right ! nullptr p-right-color ColorFlag::RED) distinguish condition_be_processed::_C4; else if (p-left ! nullptr p-left-color ColorFlag::RED) distinguish condition_be_processed::_C5; else distinguish condition_be_processed::_C6; } else { q p-left; if (q-right ! nullptr q-right-color ColorFlag::RED) distinguish condition_be_processed::_C7; else if (q-left ! nullptr q-left-color ColorFlag::RED) distinguish condition_be_processed::_C8; else distinguish condition_be_processed::_C9; } } } if (distinguish condition_be_processed::C1 || distinguish condition_be_processed::_C1 || distinguish condition_be_processed::C2 || distinguish condition_be_processed::_C10) { q parent; parent-color ColorFlag::BLACK; if (distinguish condition_be_processed::C1 || distinguish condition_be_processed::_C1) { p-color ColorFlag::RED; if (distinguish condition_be_processed::C1) { p-left-color ColorFlag::BLACK; RotateR(parent); } else { p-right-color ColorFlag::BLACK; RotateL(parent); } } else { if (distinguish condition_be_processed::C2) RotateLR(parent); else RotateRL(parent); } } else if (distinguish condition_be_processed::C3 || distinguish condition_be_processed::_C3) { parent-color ColorFlag::BLACK; p-color ColorFlag::RED; return root; } else if (distinguish condition_be_processed::C4 || distinguish condition_be_processed::_C4) { q parent; if (distinguish condition_be_processed::C4) { p-left-color ColorFlag::BLACK; RotateR(parent); } else { p-right-color ColorFlag::BLACK; RotateL(parent); } } else if (distinguish condition_be_processed::C5 || distinguish condition_be_processed::_C5) { q parent; if (distinguish condition_be_processed::C5) { p-right-color ColorFlag::BLACK; RotateLR(parent); } else { p-left-color ColorFlag::BLACK; RotateRL(parent); } } else if (distinguish condition_be_processed::C6 || distinguish condition_be_processed::_C6) { q parent; parent-color ColorFlag::RED; if (distinguish condition_be_processed::C6) RotateR(parent); else RotateL(parent); } else if (distinguish condition_be_processed::C7 || distinguish condition_be_processed::_C8) { q-left-color ColorFlag::BLACK; q parent; if (distinguish condition_be_processed::C7) RotateLR(parent); else { RotateR(p-left); RotateRL(parent); } } else if (distinguish condition_be_processed::_C7 || distinguish condition_be_processed::C8) { q-right-color ColorFlag::BLACK; q parent; if (distinguish condition_be_processed::_C7) RotateRL(parent); else { RotateL(p-right); RotateLR(parent); } } else if (distinguish condition_be_processed::C9 || distinguish condition_be_processed::_C9) { p-color ColorFlag::BLACK; q-color ColorFlag::RED; q parent; if (distinguish condition_be_processed::C9) RotateR(parent); else RotateL(parent); } } while (stackforflashback.empty() false); parent-color ColorFlag::BLACK; return parent; } else { cout 红黑树中不存在要删除的数据元素,删除失败 endl; return nullptr; } } template typename T RBTreeNodeT* InsertRB(RBTreeNodeT* root, T key) { //红黑树插入 if (root nullptr) return new RBTreeNodeT(key, ColorFlag::BLACK); else { stackRBTreeNodeT* stackforflashback; RBTreeNodeT* p root; while (p ! nullptr) //搜索插入位置 { stackforflashback.push(p); if (key p-data) p p-left; else if (key p-data) p p-right; else { cout 要插入的关键字在AVL树中已存在,插入失败 endl; return nullptr; } } if (key stackforflashback.top()-data) { p stackforflashback.top()-left new RBTreeNodeT(key, ColorFlag::RED); } else { p stackforflashback.top()-right new RBTreeNodeT(key, ColorFlag::RED); } enum class condition_be_processed {L1, L2, L3, _L1, _L2, _L3}distinguish; RBTreeNodeT* q nullptr; RBTreeNodeT* g nullptr; while (stackforflashback.empty() false) //从第一棵满足循环不变条件的子树(就是新插入的节点)开始逐步向上调整颜色或进行平衡化旋转,直到原红黑树重新恢复平衡为止 { if (g ! nullptr) { if (g-color ColorFlag::BLACK) { linkWithUpper(stackforflashback.top(), p, g); return root; } else p g; } q stackforflashback.top(); //进入新一轮循环后p为满足循环不变条件的子树的根节点,stackforflashback栈顶指针为其父节点指针 stackforflashback.pop(); if (q-color ColorFlag::BLACK) return root; g stackforflashback.top(); stackforflashback.pop(); if (q g-left) { if (g-right ! nullptr g-right-color ColorFlag::RED) distinguish condition_be_processed::L1; else if (p q-left) distinguish condition_be_processed::L2; else distinguish condition_be_processed::L3; } else if (g-left ! nullptr g-left-color ColorFlag::RED) distinguish condition_be_processed::_L1; else if (p q-left) distinguish condition_be_processed::_L2; else distinguish condition_be_processed::_L3; g-color ColorFlag::RED; if (distinguish condition_be_processed::L1 || distinguish condition_be_processed::_L1) { q-color ColorFlag::BLACK; if (distinguish condition_be_processed::L1) g-right-color ColorFlag::BLACK; else g-left-color ColorFlag::BLACK; } else if (distinguish condition_be_processed::L2 || distinguish condition_be_processed::_L3) { q-color ColorFlag::BLACK; p g; if (distinguish condition_be_processed::L2) RotateR(g); else RotateL(g); } else if (distinguish condition_be_processed::_L2 || distinguish condition_be_processed::L3) { p-color ColorFlag::BLACK; p g; if (distinguish condition_be_processed::_L2) RotateRL(g); else RotateLR(g); } } g-color ColorFlag::BLACK; return g; } } template typename T int Searchd(RBTreeNodeT* ptr, int d) { if (d 2) return 0; else { if (d 1) { if (ptr-right nullptr) return 0; else return 2; } else { if (ptr-left ! nullptr) return 1; else { if (ptr-right ! nullptr) return 2; else return 0; } } } } template typename T void output(RBTreeNodeT* ptr) //输出以ptr为根的红黑树对应的广义表形式 { struct memory { RBTreeNodeT* p; int direction; int last; memory(RBTreeNodeT* p, int d, int l) :p(p), direction(d), last(l) {} }; int d 0; RBTreeNodeT* const dest ptr; stackmemory arrange; while (true) { if (Searchd(ptr, d) 0) { if (ptr dest) { if (d 0) cout ptr-data (; else { if (arrange.top().last 1) cout , ; } cout ); break; } else { if (d 0) { if (arrange.top().last 0) { if (arrange.top().direction 1) { cout ptr-data; arrange.top().last 1; } else { cout , ptr-data; arrange.top().last 2; } } else { cout ,; cout ptr-data; arrange.top().last 2; } } else { if (arrange.top().last 2) cout ); else { cout , ); } arrange.pop(); } ptr arrange.top().p; d arrange.top().direction; } } else { RBTreeNodeT* interval nullptr; if (d 0) { if (arrange.empty() false) { if (arrange.top().last 0) { if (arrange.top().direction 1) { cout ptr-data (; arrange.top().last 1; } else { cout , ptr-data (; arrange.top().last 2; } } else { cout ,; cout ptr-data (; arrange.top().last 2; } } else { cout ptr-data (; } arrange.push(memory(ptr, Searchd(ptr, d), 0)); if (arrange.top().direction 1) interval ptr-left; else interval ptr-right; } else { arrange.top().direction 2; interval ptr-right; } d 0; ptr interval; } } } int main() { const int N 1000; //vectorTYPE insertvalue{ 13, 2}; vectorTYPE insertvalue; for (int i 1; i N; i) { insertvalue.push_back(i); } shuffle(insertvalue.begin(), insertvalue.end(), default_random_engine()); RBTreeNodeTYPE* root nullptr; for (vectorTYPE::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { root InsertRB(root, *p); cout 插入 *p endl; //output(root); cout endl; if (isRB(root) true) { cout 当前树是红黑树; cout endl; } else { cerr 错误当前树不是红黑树! endl; exit(0); } } cout endl; //cout 插入完成后删除前红黑树对应的广义表形式为: endl; //output(root); cout endl; cout endl; for (vectorTYPE::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { cout 删除节点 *p endl; root DelRB(root, *p); if (root ! nullptr) { //output(root); cout endl; if (isRB(root) true) { cout 当前树是红黑树; cout endl; } else { cerr 错误当前树不是红黑树! endl; exit(0); } } else cout NULL; cout endl; } return 0; }
