活动介绍
file-type

C++枚举集库:类型安全地管理固定集合

ZIP文件

下载需积分: 5 | 34KB | 更新于2025-01-08 | 40 浏览量 | 0 下载量 举报 收藏
download 立即下载
该库支持对集合进行访问、修改、添加、删除操作,同时还包括迭代集合中的所有元素的方法。它解决了一个常见的问题:在使用枚举表示一组选项时,通常会使用位运算将枚举值合并,从而失去类型安全特性。cpp_enum_set通过提供一个类型安全的枚举集容器,使得程序员可以安全且方便地操作枚举值的集合。" 知识点详解: 1. 枚举类型与位运算 枚举(enum)在C++中被广泛用于定义一组命名的整型常量。在表示一组选项时,通常利用整型的位运算特性,将枚举值定义为2的幂次方,以便使用位运算符“或”(|)将它们组合成一个整数值。例如,有三个选项A、B、C,可以定义为enum class option { A = 1, B = 2, C = 4 }; 然后可以组合为 option = option::A | option::C。这种方式虽然简洁,但其缺点在于丢失了类型信息,使得操作变得不那么安全。 2. 类型安全与类型安全的枚举集 类型安全是指在编译时能够检查到的错误,从而避免运行时错误。传统的枚举类型与位运算结合使用时,虽然在数值上可以区分不同的组合,但是从类型系统角度来看,它们仅仅是整数,没有任何方式可以保证操作的正确性,例如将一个整数错误地当作枚举类型来处理。cpp_enum_set库的目标是提供一个类型安全的环境,即使在使用位运算时也能确保类型信息不会丢失,所有的操作都限制在特定的枚举类型范围内。 3. cpp_enum_set库的功能 - 访问:提供方法允许用户安全地访问集合中的元素,无论是一次访问一个元素还是访问整个集合。 - 修改:允许用户安全地修改集合中的元素,包括添加或删除特定的枚举值。 - 迭代:为用户提供迭代集合中所有元素的能力,确保在迭代过程中始终保持类型安全。 - 集合操作:包括集合的并集、交集等基本操作,以及集合的比较操作等。 4. 库的设计原理 该库的设计利用了模板和类的特性,将枚举类型封装起来,使得整个集合的操作都围绕这个封装的类型进行。通过这种方式,即使进行位运算操作,也不会将枚举值与整数混合起来,从而保持了操作的类型安全。此外,通过访问器、修改器和迭代器等设计模式的使用,使得库的接口更加清晰、易于使用。 5. 应用场景 cpp_enum_set库特别适合用于那些需要处理固定选项集合的场景,如状态机、配置选项、权限管理等。通过这个库,可以减少错误的发生,同时提高代码的可读性和可维护性。 6. 实现技术细节 - 通过模板编程实现对任意枚举类型的支持。 - 使用位操作来处理枚举值的集合,但封装在类型安全的类中。 - 提供迭代器模式实现集合元素的迭代。 - 使用STL容器(如std::set或std::vector)作为底层存储结构。 在实际应用中,使用cpp_enum_set库时,首先需要包含相应的头文件。定义枚举类型后,可以创建cpp_enum_set类型的对象,并使用提供的方法来管理枚举值的集合。由于库的实现细节未完全公开,具体的使用方法需要参考库提供的示例和文档。 从cpp_enum_set-master的文件名称列表可以推测,该库的源代码可能被组织在不同的目录和文件中,以便于管理和维护。具体的目录结构和文件内容需要进一步查阅压缩包内的文件来获取。

相关推荐

filetype

#ifndef _RBTREE_H_ #define _RBTREE_H_ /* 红黑树性质 验证方法 1. 节点为红或黑 无需显式检查(由颜色枚举保证) 2. 根节点为黑 在入口函数检查 root->_col == BLACK 3. 叶子节点(NIL)为黑 通过 nullptr 隐式处理(到达空节点时统计) 4. 红色节点不能有红子节点 递归检查父子节点颜色 5. 黑高一致性 对比每条路径的黑色节点数是否等于 refNum */ /* 性质: 1.每个节点要么是红色, 要么就是黑色. 2.根节点必为黑色。 3.叶子节点(NIL)都为黑色,数据key和value且为null。 4.红色节点的两个子节点都为黑色(红黑树不会出现相邻的红色节点)(即父与子节点不可能都是红色) 5.从任意节点出发,到其每个叶子节点(NIL)的路径中包含相同数量的黑色节点 衍生特性: 1.新加入到红黑树的节点为红色节点,如果新加入节点是黑色,会影响性质4。所以新节点是红色影响最小 2.根据性质3判断: 叶子节点(NIL)虽然是null, 但也算是一个有效的颜色节点 3.根据性质4判断: 黑色节点的2个子节点可以为2个红色节点; 也可以是2个黑色节点; 也可以是1红1黑的节点 5.根据性质5判断: 确保没有一条路径会比其他路径长出俩倍 */ #include <type_traits> namespace RBTREE { //红黑树的颜色类型 typedef enum class tagCOLOR : unsigned char//给枚举类型限定字节数,C++11开始支持 sizeof(Color) = 1byte { RED, BLACK }COLOR; /****************************************************************************************************************************/ //红黑树左右孩子的位置类型,主要用作判断当前节点是属于父节点的左孩子还是右孩子 //这样就不用疯狂使用父节点寻址才能得到当前节点的分支方向(左右) typedef enum class tagBELONG : unsigned char//给枚举类型限定字节数,C++11开始支持 sizeof(BELONG) = 1byte { ROOT, LEFT, RIGHT, NIL }BELONG; /****************************************************************************************************************************/ //红黑树节点类 template<class KEY, class VALUE> class RBTreeNode { public: COLOR m_Color; //节点颜色,不是红就是黑. 默认色是红色,黑色会影响性质5 KEY m_Key; //关键值: 查找;比较... 都依靠它 VALUE m_Value; //目标元素 RBTreeNode* m_pParent; //父节点 RBTreeNode* m_pLeft; //左孩子 RBTreeNode* m_pRight; //右孩子 BELONG m_beLong; //节点是属于父节点的左孩子还是右孩子。 bool m_bIsDeleted; //标记节点是否被删除 static RBTreeNode<KEY, VALUE> NIL; // 静态NIL声明 //默认构造函数:仅供NIL叶子节点创建时使用 RBTreeNode() : m_Color(COLOR::BLACK), //NIL节点默认颜色是: 黑色 m_Key(), //KEY默认构造 m_Value(), //VALUE默认构造 m_pParent(nullptr), //父指针置空 m_pLeft(nullptr), //左指针置空 m_pRight(nullptr), //右指针置空 m_beLong(BELONG::NIL), //设置为叶子节点NIL m_bIsDeleted(false) //标记节点没有被删除 { } //初始化节点数据 RBTreeNode(const KEY& _Key, const VALUE& _Value) : m_Color(COLOR::RED), //新节点默认颜色是: 红色 m_Key(_Key), //启动KEY的复制构造函数 m_Value(_Value), //启动VALUE的复制构造函数 m_pParent(nullptr), //父指针置空 m_pLeft(nullptr), //左指针置空 m_pRight(nullptr), //右指针置空 m_beLong(BELONG::ROOT), //设置为根节点,插入/删除后会调整 m_bIsDeleted(false) //标记节点没有被删除 { //强制定义叶子节点为的就是维护红黑树的性质: 2.根据性质3判断: 叶子节点(NIL)虽然是null, 但也算是一个有效的颜色节点 m_pRight = &NIL; //新节点的右边指向叶子节点 m_pLeft = &NIL; //新节点的左边指向叶子节点 NIL.m_pLeft = NIL.m_pRight = NIL.m_pParent = &NIL; //完全自引用 //其实可以直接用nullptr去模拟成NIL节点,下面有2个方案的解析说明: 推荐方案:优先使用实质NIL节点 /* 方案一:使用nullptr表示NIL节点 实现方式 优点 内存效率高 不需要为NIL节点分配额外内存,节省空间。 适合内存敏感场景(如嵌入式系统)。 代码简洁 直接使用nullptr判断,减少间接访问。 例如:if(node->m_pLeft == nullptr) 比 if (node->m_pLeft == m_NIL) 更直观。 性能略优 避免指针解引用(访问实质NIL节点需要一次内存访问)。 缺点 边界条件处理复杂 旋转、删除等操作需要频繁检查nullptr,容易遗漏边界条件。 例如:左旋时需确保node->m_pRight != nullptr。 代码重复 每个操作需重复nullptr检查,可能违反DRY原则。 调试困难 nullptr无法提供调试信息(如NIL节点的颜色、父节点等)。 方案二:使用实质NIL节点 实现方式 优点 统一边界条件处理 所有叶子节点均为m_NIL,简化旋转、删除等操作的逻辑。 例如:左旋时无需检查node->m_pRight是否为空。 代码可维护性强 通过isNIL()方法封装判断逻辑,减少重复代码。 调试时可打印NIL节点的信息(如颜色、父节点)。 符合红黑树理论定义 明确区分内部节点和叶子节点,便于验证红黑树性质。 支持复杂自定义类型 自定义类型的NIL节点可初始化默认值,避免未定义行为。 缺点 内存开销 每个红黑树实例需分配一个NIL节点(通常可忽略)。 初始化复杂度 需确保NIL节点的指针自洽(如m_pLeft = m_pRight = m_pParent = this)。 推荐方案:优先使用实质NIL节点 理由 安全性:避免因nullptr检查遗漏导致的未定义行为(如空指针解引用)。 可维护性:统一处理边界条件,减少代码错误。 调试友好:NIL节点可附加调试信息(如颜色、父节点)。 性能差异极小:现代CPU的缓存机制会抵消单次指针解引用的开销。 */ } //判断当前是否叶子节点 inline bool isNIL()const { return m_beLong == BELONG::NIL; } }; // 类外静态成员定义 template<class KEY, class VALUE> RBTreeNode<KEY, VALUE> RBTreeNode<KEY, VALUE>::NIL; /****************************************************************************************************************************/ //红黑树类 template<class KEY, class VALUE> class RBTree { private: RBTreeNode<KEY, VALUE>* m_pRoot;//红黑树根节点, 性质: 必须为黑色 int m_iSize; //红黑树大小 public: //默认构造函数 RBTree() : m_pRoot(nullptr) //新创建的树,根节点置为空 { } //默认析构函数 ~RBTree() { } //判断是否空树 inline bool IsEmpty()const { return m_pRoot == nullptr; } //向红黑树插入元素 bool Insert(const KEY& _Key, const VALUE& _Value) { RBTreeNode<KEY, VALUE>* pNewNode = new RBTreeNode<KEY, VALUE>(_Key, _Value);//创建一个新节点 //printf("创建节点:%#x key<%d>\n", pNewNode, _Key); if (insert(m_pRoot, pNewNode)) //接入内部insert函数 { m_iSize++;//插入成功,树大小+1 return true;//返回true } //printf("插入失败,删除节点:%#x key<%d>完成\n", pNewNode, pNewNode->m_Key); delete pNewNode;//插入失败,删除新节点 pNewNode = NULL; return false; } //精确查找 VALUE* Find(const KEY& _Key) { RBTreeNode<KEY, VALUE>* pResult = find(_Key); return pResult ? &pResult->m_Value : nullptr; } bool Erase(const KEY& _Key) { RBTreeNode<KEY, VALUE>* pTarget = find(_Key);//查找目标节点 RBTreeNode<KEY, VALUE>* pTmp = nullptr; if (pTarget) { //成功查找到目标节点 if (pTarget->m_pRight->isNIL() == false && pTarget->m_pLeft->isNIL() == false)//如果2个孩子都不是NIL { //我个人优先采用后继节点替换方案 //据说优先采用后继节点替换, 删除目标后能减少调整红黑树的机率,是不是真的不知道. //但对于正常用右脑的我来说,思维视图方面相对方便一点的:查找后继过程思维视图类似写了个大于号: > //当然,对于用左脑的大佬来说, 使用前驱节点替换方案也就只写了个小于号: < //找出后继节点,2个节点交换 //pTmp = sucessor(pTarget->m_pRight);//最坏情况:后继节点就是右孩子,正常情况:后继节点就是右孩子的最左节点 pTmp = predecessor(pTarget->m_pLeft); //最坏情况:前驱节点就是左孩子,正常情况:前驱节点就是左孩子的最右节点 swapKeys(pTarget, pTmp);//交换2个节点的数据 //数据交换成功,此时pTmp节点才是我们的删除目标了,因为数据已经交替过来了,并且确保pTmp的俩孩子都是NIL pTmp->m_bIsDeleted = true; //标记节点为删除状态 return erase(pTmp);//接入内部函数: 删除操作过程修复树 } else { pTarget->m_bIsDeleted = true; //标记节点为删除状态 return erase(pTarget);//说明删除目标的2个孩子都是NIL空, 修复树 } } else { //要查找的key不存在 return false; } } private: //红黑树的内部函数 // 1. 将红黑树当作一颗二叉查找树,将新节点插入到红黑树中。 // 2. 插入完成后再调整树状态,使其能成为一棵合法的红黑树 bool insert(RBTreeNode<KEY, VALUE>* &_pRoot, RBTreeNode<KEY, VALUE>* _pNewNode) //&_pRoot能够使函数内部直接读写m_pRoot { if (_pNewNode == nullptr)return false; RBTreeNode<KEY, VALUE>* pCursor = _pRoot;//操作游标,一般指当前节点 RBTreeNode<KEY, VALUE>* pPreNode = nullptr;//用作 备份上一级节点.当游标指向NIL叶子节点时,此指针就能直接向上回溯出父节点 BELONG blNIL = BELONG::NIL; //用来判断找到的叶子节点是左孩子或者是右孩子 while (pCursor != nullptr && !pCursor->isNIL())//如果当前节点不为空, 并且不是叶子节点 { pPreNode = pCursor;//备份上一个节点,游标将指向下个节点 if (_pNewNode->m_Key < pCursor->m_Key)//如果新节点的key小于当前节点的key { pCursor = pCursor->m_pLeft;//把左孩子赋值给游标 blNIL = BELONG::LEFT;//最后比较是: 向左操作 continue;//重新循环比较 } else if (_pNewNode->m_Key > pCursor->m_Key)//如果新节点的key大于当前节点的key { pCursor = pCursor->m_pRight;//把右孩子赋值给游标 blNIL = BELONG::RIGHT;//最后比较是: 向右操作 continue;//重新循环比较 } else //那么说明插入的节点已经存在 { return false;//插入失败 } } /*代码执行到此, 只有以下2种情况: 1. m_pRoot是空的 2. 说明游标节点已经指向到: 叶子节点*/ if (pCursor == nullptr)//m_pRoot是空的 { _pRoot = _pNewNode; //当前节点为根节点 _pRoot->m_Color = COLOR::BLACK; //根节点要求绝对黑色 _pRoot->m_beLong = BELONG::ROOT; //设置为根节点 return true; } else if(pCursor->isNIL() && pPreNode)//2.游标指向NIL, 说明已经找到适合插入的节点, 并且父节点不为空 { //判断最后的比较操作 if (blNIL == BELONG::LEFT)//叶子节点是位于左边 { //开始与左节点进行联结 pPreNode->m_pLeft = _pNewNode;//父节点的左孩子设置成这个新节点 _pNewNode->m_pParent = pPreNode;//设置这个新节点的父亲 _pNewNode->m_beLong = BELONG::LEFT;//这新节点是父亲的左孩子 //调整颜色不在此处调整 //联结完成 } else if (blNIL == BELONG::RIGHT)//叶子节点是位于右边 { //开始与右节点进行联结 pPreNode->m_pRight = _pNewNode;//父节点的右孩子设置成这个新节点 _pNewNode->m_pParent = pPreNode;//设置这个新节点的父亲 _pNewNode->m_beLong = BELONG::RIGHT;//这新节点是父亲的右孩子 //调整颜色不在此处调整 //联结完成 } else { //不应该也不可能来到此处,属于异常: 不是左操作,也不是右操作,等于操作已经返回false了 return false; } } else { //不应该来到此处,属于异常: 游标指向是叶子节点, 但pPreNode是空,这并不可能发生的事 return false; } //代码执行到此: 需要调整颜色调整树结构了, 审查当前结构的合法性 //设置插入目标节点的颜色为: 红色. 插入新节点为红色对红黑树的性质5影响最小 //_pNewNode->m_Color = Color::RED;//节点初始化已经是红色,无须重复设置 //插入新节点后, 重新修正为一颗平衡二叉树 insert_fix(_pNewNode); ////////// //修正完成后就是一棵标准的: 红黑树 // // return true; // } // // /******************************************开始解析说明 insert_fix() 函数修复红黑树过程******************************** * 红黑树插入修正函数 * * 在向红黑树中插入节点之后(失去平衡),再调用该函数; * 目的是将它根据颜色调整重新塑造成一颗红黑树。 * * 参数说明: * _pRoot 红黑树的根节点 * _pNewNode 插入的新节点 */ /* 修正原理 回忆下红黑树的性质: 性质: 1.每个节点要么是红色, 要么就是黑色。 2.根节点必为黑色。 3.叶子节点(NIL)都为黑色,数据key和value且为null。 4.红色节点的两个子节点都为黑色(红黑树不会出现相邻的红色节点)(即父与子节点不可能都是红色) 5.从任意节点出发,到其每个叶子节点(NIL)的路径中包含相同数量的黑色节点 衍生特性: 1.新加入到红黑树的节点为红色节点,如果新加入节点是黑色,会影响性质4。所以新节点是红色影响最小 2.根据性质3判断: 叶子节点(NIL)虽然key和value是null, 但也算是一个有效的颜色节点 3.根据性质4判断: 黑色节点的2个子节点可以为2个红色节点。也可以是2个黑色节点,但必须是叶子节点(NIL)(左右树不可能存在有效的黑色节点) 4.根据性质4判断: 黑色节点的2个子点也可以是1个红色节点,一个黑色节点(叶子节点NIL)(左右树不可能存在有效的黑色节点) 5.根据性质5判断: 确保没有一条路径会比其他路径长出俩倍 ************************************************************************** 总结插入新节点可能出现的情景,并给出处理方案: 情景1: 插入的节点的父节点是黑色 情景1处理方案:无需任何处理 情景2:插入的节点的父节点是红色(父子节点均为红色,需修正) 根据叔叔节点去拆分3种分支情景: 情景2.1: 叔叔节点是存在,并且是红色 情景2.1处理方案: 将父节点设置成黑色; 将叔叔节点设置成黑色; 将祖父节点设置成红色; 将祖父节点设置成当前节点,继续while循环向上修正 情景2.2: 叔叔节点不存在或者叔叔节点是黑色, 并且插入的节点的父节点是属于其祖父节点的左孩子(叔叔是右孩子) 根据情景2.2去拆分2种分支情景: 情景2.2.1: 插入节点是其父节点的右孩子(内侧插入) 情景2.2.1处理方案: 将当前节点的父节点左旋操作后得到情景2.2.2 处理情景2.2.2 情景2.2.2: 插入节点是其父节点的左孩子(外侧插入) 情景2.2.2处理方案: 将父亲节点设置为黑色 将祖父节点设置成红色 将祖父节点进行右旋操作 情景2.3: 叔叔节点不存在或者叔叔节点是黑色, 并且插入节点的父节点是属于其祖父节点的右孩子(叔叔是左孩子) 根据情景2.3去拆分2种分支情景: 情景2.3.1: 插入的节点是其父节点的左孩子(外侧插入) 情景2.3.1处理方案: 将当前节点的父节点右旋操作后得到情景2.3.2 处理情景2.3.2 情景2.3.2: 插入的节点是其父节点的右孩子(内侧插入) 情景2.3.2处理方案: 将父新节点设置成黑色 将祖父节点设置成红色 将祖父节点进行左旋操作 */ bool insert_fix(RBTreeNode<KEY, VALUE>* _pNewNode) { if (!_pNewNode)return false; RBTreeNode<KEY, VALUE>* pParent = _pNewNode->m_pParent; //取得父节点 RBTreeNode<KEY, VALUE>* pGrandfather = nullptr;//取出祖父节点 RBTreeNode<KEY, VALUE>* pUncle = nullptr; //用作储存叔叔节点 // 情景1: 插入的节点的父节点是黑色 // 情景1处理方案:无需任何处理 if (pParent && pParent->m_Color == COLOR::BLACK)return true;//情景1处理完成 if (!pParent)//说明已经到达根节点了 { if (_pNewNode->m_beLong == BELONG::ROOT) { _pNewNode->m_Color = COLOR::BLACK;//根节点强制黑色 return true; } return false; } do { //这是情景2: 插入的新节点的父亲是红色的,违反红黑树性质4: //4. 红色节点的两个子节点都为黑色(红黑树不会出现相邻的红色节点)(即父与子节点不可能都是红色) pGrandfather = pParent->m_pParent;//取出祖父节点 if (pGrandfather)//祖父节点是有效的 { //如果父亲是左孩子,那么叔叔肯定是祖父的右孩子。否则父亲是右孩子,那么叔叔就是左孩子 pUncle = pParent->m_beLong == BELONG::LEFT ? pGrandfather->m_pRight : pParent->m_beLong == BELONG::RIGHT ? pGrandfather->m_pLeft : nullptr;//取出叔叔节点 if (pUncle == nullptr) { //叔叔节点居然提取不到,不可能的,说明结构有异常 throw("红黑树结构异常: 颜色持衡过程发现->取得叔叔节点失败, 父亲节点居然是NIL"); } //开始检查叔叔节点颜色 if (pUncle->m_Color == COLOR::RED)//叔叔节点是红色: 这是情景2.1 { //情景2.1修正方案: 颜色持衡 //将P设置为黑色 //将U设置为黑色 //将G设置为红色 //将G设置成当前节点继续while循环向上修正 pParent->m_Color = COLOR::BLACK;//将P设置为黑色 pUncle->m_Color = COLOR::BLACK; //将U设置为黑色 pGrandfather->m_Color = COLOR::RED;//将G设置为红色 return insert_fix(pGrandfather);//将G设置成当前节点继续递归循环向上判断 } else if(pUncle->m_Color == COLOR::BLACK)//叔叔节点是黑色: 这是情景2.2或者情景2.3 { if (pParent->m_beLong == BELONG::LEFT)//父亲是个左孩子,触发情景2.2 { if (!_pNewNode) { throw("触发情景2.2: 插入节点为空"); } if (_pNewNode->m_beLong == BELONG::RIGHT)//如果插入节点是其父亲的右孩子: 触发情景 2.2.1 { pParent = left_rotate(pParent);//对父亲进行左旋操作得到情景2.2.2 if (!pParent)throw("红黑树结构异常: 触发情景2.2.1时左旋失败"); _pNewNode = pParent->m_pLeft; //左旋后, 插入节点和父亲交换成功了。 return insert_fix(_pNewNode);//重新递归进入情景: 2.2.2 } else if (_pNewNode->m_beLong == BELONG::LEFT)//如果插入节点是其父亲的左孩子: 触发情景2.2.2 { pParent->m_Color = COLOR::BLACK;//将P设置成黑色 pGrandfather->m_Color = COLOR::RED;//将G设置成红色 pParent = right_rotate(pGrandfather);//对G进行右旋操作 return true;//情景2.2的所有场景解析完成 } //进入到此处代码说明 新插入节点是ROOT,NIL, else已经不可能了,因为insert_fix的上层是insert对pNewNode封装好了 } else if (pParent->m_beLong == BELONG::RIGHT)//父亲是个右孩子,触发情景2.3 { if (!_pNewNode) { throw("触发情景2.3: 插入节点为空"); } if (_pNewNode->m_beLong == BELONG::LEFT)//如果插入的节点是其父亲的左孩子: 触发情景2.3.1 { pParent = right_rotate(pParent);//对父亲进行右旋操作得到情景2.3.2 if(!pParent)throw("红黑树结构异常: 触发情景2.3.1时右旋失败"); _pNewNode = pParent->m_pRight; //右旋后,插入节点和父亲交换成功了 return insert_fix(_pNewNode);//递归 进入情景: 2.3.2 } else if (_pNewNode->m_beLong == BELONG::RIGHT)//如果插入节点是其父亲的右孩子: 触发情景2.3.2 { pParent->m_Color = COLOR::BLACK;//将P设置成黑色 pGrandfather->m_Color = COLOR::RED;//将G设置成红色 pParent = left_rotate(pGrandfather);//对G进行左旋操作 return true;//情景2.3的所有场景解析完成 } //进入到此处代码说明 新插入节点是ROOT,NIL, else已经不可能了,因为insert_fix的上层是insert对pNewNode封装好了 } else if (pParent->m_beLong == BELONG::ROOT) { //插入节点红色,父节点红色才会进入情景2.2-2.3,但父亲如果是根节点Root,那么之前这个红黑树就是不合法了 //因为根节点永远是黑色,所以其实能进入到此处也是异常了。 //pParent->m_Color = COLOR::BLACK;//无条件把根节点设置为黑色 //return true;//已经while到根节点Root了 throw("红黑树结构异常: 插入红色新节点,父节点也是红色,但父节点居然是个根节点,红色的根节点是异常的"); } else { //基本不可能进入到此处,因为叶子节点永远是黑色的 throw("红黑树结构异常: 插入红色新节点,父节点也是红色,但父节点居然是个叶子节点"); } } //else 基本不可能的,因为红黑树性质: 节点不是红就是黑, 不可能进入else了 } else//祖父节点是无效的: 说明只有一种情况:当前的_pParent节点是根节点Root { if (pParent->m_beLong == BELONG::ROOT)//当前父节点是根节点Root { pParent->m_Color = COLOR::BLACK;//无条件把根节点设置为黑色 return true;//已经while到根节点Root了 } else { //祖父节点不存在, 父节点又不是根节点,说明结构异常了 throw("红黑树结构异常: 颜色持衡过程发现->祖父节点为空, 但父节点又不是根节点Root,这情况不应该发生."); } } } while (pParent); return false; } //进行左旋操作 RBTreeNode<KEY, VALUE>* left_rotate(RBTreeNode<KEY, VALUE>* _pTarget) { if (!_pTarget)return nullptr; if (_pTarget->isNIL()) { throw("左旋异常: 目标是个NIL, 叶子节点不能左旋操作"); } RBTreeNode<KEY, VALUE>* pParent = _pTarget->m_pParent; //取出目标的父节点 RBTreeNode<KEY, VALUE>* pRight = _pTarget->m_pRight;//备份目标的右孩子 RBTreeNode<KEY, VALUE>* pTmp = nullptr;//临时操作使用 BELONG beLong = _pTarget->m_beLong;//备份目标的 左/右孩子属性 if (pRight->isNIL()) { throw("左旋异常: 目标的右孩子是NIL, NIL不可能作为父节点的"); } pTmp = _pTarget->m_pRight = pRight->m_pLeft;//重定向右孩子到备份pRight的左孩子 pRight->m_pLeft = nullptr;//把备份的pRight的左孩子断开,因为左孩子已经被目标节点重定向占用了 if (pTmp->isNIL() == false)//如果新定向的右孩子不是NIL叶子节点 { pTmp->m_beLong = BELONG::RIGHT;//这个新孩子是从备份的pRight左边取过来的变成右孩子 pTmp->m_pParent = _pTarget;//把这个新右孩子的父亲设置是目标节点 } //else //新的右孩子是个NIL叶子节点,不用设置NIL属性 pTmp = nullptr;//置空,避免后面误操作 pRight->m_pLeft = _pTarget;//重新设置备份pRight的左孩子为目标节点 _pTarget->m_pParent = pRight;//重设置目标的父亲为pRight _pTarget->m_beLong = BELONG::LEFT;//此时目标就是pRight的左孩子 if (pParent == nullptr)//左旋的目标没有父节点,说明左旋的目标是一个根节点 { if (beLong != BELONG::ROOT)//如果成立,说明之前红黑树结构异常 { //左旋目标没有父节点并且不是根节点,异常了 throw("左旋异常: 目标没有父节点并且也没有根节点的标记"); } pRight->m_beLong = beLong;//设置Root pRight->m_Color = COLOR::BLACK;//根节点必然为黑 pRight->m_pParent = nullptr;//根节点没有父亲 m_pRoot = pRight;//根节点已经发生变化 } else { pRight->m_beLong = beLong;//设置备份pRight的孩子属性 pRight->m_pParent = pParent;//设置备份pRight的父亲 if (beLong == BELONG::LEFT)//左旋目标原来是一个左孩子 { pParent->m_pLeft = pRight; } else//左旋目标原来是一个右孩子 { pParent->m_pRight = pRight; } } return pRight; } //进行左旋操作 RBTreeNode<KEY, VALUE>* right_rotate(RBTreeNode<KEY, VALUE>* _pTarget) { if (!_pTarget)return nullptr; if (_pTarget->isNIL()) { throw("右旋异常: 目标是个NIL, 叶子节点不能右旋操作"); } RBTreeNode<KEY, VALUE>* pParent = _pTarget->m_pParent; //取出目标的父节点 RBTreeNode<KEY, VALUE>* pLeft = _pTarget->m_pLeft;//备份目标的左孩子 RBTreeNode<KEY, VALUE>* pTmp = nullptr;//临时操作使用 BELONG beLong = _pTarget->m_beLong;//备份目标的 左/右孩子属性 if (pLeft->isNIL()) { throw("右旋异常: 目标的左孩子是NIL, NIL不可能作为父节点的"); } pTmp = _pTarget->m_pLeft = pLeft->m_pRight;//重定向左孩子到备份pLeft的右孩子 pLeft->m_pRight = nullptr;//把备份的pLeft的右孩子断开,因为该右孩子已经被目标节点重定向占用了 if (pTmp->isNIL() == false)//如果新定向的左孩子不是NIL叶子节点 { pTmp->m_beLong = BELONG::LEFT;//这个新孩子是从备份的pLeft右边取过来的变成左孩子的 pTmp->m_pParent = _pTarget;//把这个新左孩子的父亲设置是目标节点 } //else //新的左孩子是个NIL叶子节点,不用设置NIL属性 pTmp = nullptr;//置空,避免后面误操作 pLeft->m_pRight = _pTarget;//重新设置备份pLeft的右孩子为目标节点 _pTarget->m_pParent = pLeft;//重设置目标的父亲为pLeft _pTarget->m_beLong = BELONG::RIGHT;//此时目标就是pLeft的右孩子 if (pParent == nullptr)//右旋的目标没有父节点,说明右旋的目标是一个根节点 { if (beLong != BELONG::ROOT)//如果成立,说明之前红黑树结构异常 { //右旋目标没有父节点并且不是根节点,异常了 throw("右旋异常: 目标没有父节点并且也没有根节点的标记"); } pLeft->m_beLong = beLong;//设置Root pLeft->m_Color = COLOR::BLACK;//根节点必然为黑 pLeft->m_pParent = nullptr;//根节点没有父亲 m_pRoot = pLeft;//根节点已经发生变化 } else { pLeft->m_beLong = beLong;//设置备份pLeft的孩子属性 pLeft->m_pParent = pParent;//设置备份pLeft的父亲 if (beLong == BELONG::LEFT)//右旋目标原来是一个左孩子 { pParent->m_pLeft = pLeft; } else//左旋目标原来是一个右孩子 { pParent->m_pRight = pLeft; } } return pLeft; } // 精确查找(返回节点指针,未找到返回nullptr) RBTreeNode<KEY, VALUE>* find(const KEY& key) const { RBTreeNode<KEY, VALUE>* pCurrent = m_pRoot; while (pCurrent && !pCurrent->isNIL()) { if (key == pCurrent->m_Key) { return pCurrent; } else if (key < pCurrent->m_Key) { pCurrent = pCurrent->m_pLeft; } else { pCurrent = pCurrent->m_pRight; } } return nullptr; } //删除操作 bool erase(RBTreeNode<KEY, VALUE>* _pTarget) { RBTreeNode<KEY, VALUE>* pTarget = _pTarget; //目标节点 RBTreeNode<KEY, VALUE>* pParent = nullptr; //父亲节点 RBTreeNode<KEY, VALUE>* pBrother = nullptr; //兄弟节点 RBTreeNode<KEY, VALUE>* pChild = nullptr; //孩子节点 do { pParent = pTarget->m_pParent; //找出兄弟节点 pBrother = (pTarget->m_beLong == BELONG::LEFT) ? pParent->m_pRight : (pTarget->m_beLong ==BELONG::RIGHT) ? pParent->m_pLeft : nullptr; //该如何判断肯定pBrother节点的存在性? 这已经给红黑树性质约束了: // 除根节点外,每个黑色节点都必须有非NIL的兄弟节点。这是由红黑树的性质5(黑色高度一致) //所以:每个黑色节点,除了根节点外,这个黑色节点必定会存在一个非NIL的兄弟 //这个兄弟节点是绝对存在的 if (pTarget->m_Color == COLOR::RED) { //场景1:被删除节点是红色********************************************* pTarget = remove_node_red(pTarget);//接入场景1的函数 //if(pTarget == nullptr) 如果返回的目标是空,则说明红黑树不用向上调整修复 } else//被删除的节点是黑色 { pChild = pTarget->m_pLeft->isNIL() == false ? pTarget->m_pLeft : pTarget->m_pRight;//取出孩子 if (pChild->isNIL() == false && pTarget->m_bIsDeleted)//如果有子节点, { pTarget = remove_node_black_3_1_1(pTarget); } else { if (pBrother && pBrother->m_Color == COLOR::RED) { //场景2:被删除节点是黑色,并且兄弟是红色********************************************* pTarget = remove_node_black_2(pTarget); //if(pTarget == nullptr) 如果返回的目标是空,则说明红黑树不用向上调整修复 if (pTarget)continue;//迭代进入场景3 } else if(pBrother && pBrother->m_Color == COLOR::BLACK) { //场景3:被删除节点是黑色,并且兄弟是黑色********************************************* pTarget = remove_node_black_3(pTarget); //if(pTarget == nullptr) 如果返回的目标是空,则说明红黑树不用向上调整修复 if (pTarget)continue;//迭代进入其它场景 } else { //被删除节点是根节点,并且2个子节点都是NIL m_pRoot = nullptr; break; } } } } while (pTarget);//采用迭代方案 //printf("删除节点:%#x key<%d>完成\n", _pTarget, _pTarget->m_Key); delete _pTarget;//删除目标节点 m_iSize--;//删除节点计数器减1 return true; } //场景1单独处理函数 //场景1:被删除节点是红色 //场景1.1:被删除节点是叶子节点(2个孩子都是NIL) //场景1.2:被删除节点有两个黑色子节点(非NIL) RBTreeNode<KEY, VALUE>* remove_node_red(RBTreeNode<KEY, VALUE>* _pTarget) { RBTreeNode<KEY, VALUE>* pParent = _pTarget->m_pParent;//删除目标红色必然拥有父节点的,没有父亲说明是根节点,不可能存在红色根节点 if (_pTarget->m_pLeft->isNIL() && _pTarget->m_pRight->isNIL())//如果2个孩子都是NIL: 进入场景1.1 { //场景1.1, 可以直接删除,但删除操作不在此,我们只管把删除目标从红黑树中剥离出来 _pTarget->m_pParent = nullptr;//断开目标节点与父亲的联结 if (_pTarget->m_beLong == BELONG::LEFT)//如果删除目标是左孩子 { if (_pTarget->m_bIsDeleted)//如果已经被标记删除, 那么左孩子已经是NIL了 { pParent->m_pLeft = _pTarget->m_pLeft;//把父亲的左孩子重定向到NIL } } else//删除目标是右孩子 { if (_pTarget->m_bIsDeleted)//如果已经被标记删除, 那么右孩子已经是NIL了 { pParent->m_pRight = _pTarget->m_pRight;//把父亲的右孩子重定向到NIL } } } //else//2个孩子都是黑色, 为什么不能只有一个节点?删除目标是红色,如果只有一个孩子,无论这个孩子是黑色还是红色都违反红黑树性质 //{ //这个场景1.2不可能进入到此了,因为Erase内已经经过前驱/后继调整过 //直接以1个NIL孩子条件跳转到了场景2或场景3 //} return nullptr;//告诉上级函数, 目标已经从红黑树剥离,不用向上修复树结构 } //场景2单独处理函数 //场景2:被删除节点是黑色, 且其兄弟是红色 RBTreeNode<KEY, VALUE>* remove_node_black_2(RBTreeNode<KEY, VALUE>* _pTarget) { //兄弟设置为黑, 父亲设置为红, 然后 左左 或者 右右, 递归给场景3 RBTreeNode<KEY, VALUE>* pParent = _pTarget->m_pParent;//取出父亲 RBTreeNode<KEY, VALUE>* pBrother = _pTarget->m_beLong == BELONG::LEFT ? pParent->m_pRight : pParent->m_pLeft;//取出兄弟 //该如何判断肯定pBrother节点的存在性? 这已经给红黑树性质约束了: // 除根节点外,每个黑色节点都必须有非NIL的兄弟节点。这是由红黑树的性质5(黑色高度一致) //所以:每个黑色节点,除了根节点外,这个黑色节点必定会存在一个非NIL的兄弟 //这个兄弟节点是绝对存在的 //如果拥有一个红色孩子,不可能只拥有一个黑色孩子(非NIL) //if (_pTarget->m_pLeft->isNIL() == false || _pTarget->m_pRight->isNIL() == false) //{ //return remove_node_black_3_1_1(_pTarget); //} //否则删除目标2个孩子都是NIL //父兄颜色交换 pBrother->m_Color = COLOR::BLACK; pParent->m_Color = COLOR::RED; if (_pTarget->m_beLong == BELONG::LEFT)//如果目标是左孩子 { if (left_rotate(pParent))//父亲左旋 { return _pTarget;//迭代给场景3 } //else左旋失败 } else//不然就是右孩子,一个有父亲的,不可能是根节点ROOT { if (right_rotate(pParent))//父亲右旋 { return _pTarget;//迭代给场景3 } //else 右旋失败 } return nullptr; } //交换2个节点的key和value,不交换颜色,采用std::swap, 触发std::move, 不执行对象的复制构造函数 void swapKeys(RBTreeNode<KEY, VALUE>* node1, RBTreeNode<KEY, VALUE>* node2) { if (!node1 || !node2 || node1->isNIL() || node2->isNIL()) return; // 交换键值 std::swap(node1->m_Key, node2->m_Key); // 交换值 std::swap(node1->m_Value, node2->m_Value); } //查找前驱 //左的最右 RBTreeNode<KEY, VALUE>* predecessor(RBTreeNode<KEY, VALUE>* _pLeft) { RBTreeNode<KEY, VALUE>* pCurrent = _pLeft; RBTreeNode<KEY, VALUE>* pPre = nullptr; while (pCurrent->isNIL() == false) { pPre = pCurrent; pCurrent = pCurrent->m_pRight; } return pPre; } //查找后继节点 //右的最左 RBTreeNode<KEY, VALUE>* sucessor(RBTreeNode<KEY, VALUE>* _pRight) { RBTreeNode<KEY, VALUE>* pCurrent = _pRight; RBTreeNode<KEY, VALUE>* pPre = nullptr; while (pCurrent->isNIL() == false) { pPre = pCurrent; pCurrent = pCurrent->m_pLeft; } return pPre; } //场景3单独处理函数 //被删除节点是黑色,并且兄弟是黑色 RBTreeNode<KEY, VALUE>* remove_node_black_3(RBTreeNode<KEY, VALUE>* _pTarget) { RBTreeNode<KEY, VALUE>* pParent = _pTarget->m_pParent; RBTreeNode<KEY, VALUE>* pBrother = _pTarget->m_beLong == BELONG::LEFT ? pParent->m_pRight : pParent->m_pLeft;//取出兄弟 //该如何判断肯定pBrother节点的存在性? 这已经给红黑树性质约束了: 除根节点外,每个黑色节点都必须有非NIL的兄弟节点。这是由红黑树的性质5(黑色高度一致) //所以:每个黑色节点,除了根节点外,这个黑色节点必定会存在一个非NIL的兄弟 //当前目标是黑色, 所以这个兄弟节点是绝对存在的 //取得侄子节点,侄子是近侄还是远侄取决于删除目标在左边还是右边了 //快速判断: 近远侄子。如果删除目标是右孩子,那么右侄子必然就是近侄子了 //如果删除目标是左孩子,那么左侄子必然就是近侄子了 //取得近侄子 RBTreeNode<KEY, VALUE>* pNear = _pTarget->m_beLong==BELONG::RIGHT ? pBrother->m_pRight : pBrother->m_pLeft; //取得远侄子 RBTreeNode<KEY, VALUE>* pFar = _pTarget->m_beLong==BELONG::RIGHT ? pBrother->m_pLeft : pBrother->m_pRight; //场景3.1 - 兄弟2个子节点都是黑色(可以是NIL颜色占位判断) if (pNear->m_Color == COLOR::BLACK && pFar->m_Color == COLOR::BLACK) { return remove_node_black_3_1(_pTarget);//场景3.1单独分支处理 } //场景3.2 - 近侄子是红色,远侄子是黑色(黑色可以是NIL) else if (pNear->m_Color == COLOR::RED && pFar->m_Color == COLOR::BLACK) { return remove_node_black_3_2(_pTarget);//场景3.2单独分支处理 } //场景3.3 - 远侄子是红色 //场景3.4 - 兄弟节点的两个子节点都是红色 -- 如果2个节点都是红,说明远侄必然也是红了,所以合并场景 else { return remove_node_black_3_3(_pTarget);//进入场景3.3 } return nullptr; } //场景3:被删除节点是黑色, 且其兄弟是黑色 //场景3.1:兄弟节点的两个子节点都是黑色 //场景3.1.1:如果删除目标有1个孩子,那么这孩子必然是红色, 不可能是黑(非NIL) RBTreeNode<KEY, VALUE>* remove_node_black_3_1(RBTreeNode<KEY, VALUE>* _pTarget) { //场景3.1.1:如果删除目标有1个孩子,那么这孩子必然是红色, 不可能是黑(非NIL) //if (_pTarget->m_pLeft->isNIL() == false || _pTarget->m_pRight->isNIL() == false)//删除目标拥有一个红色的孩子 //{ //return remove_node_black_3_1_1(_pTarget);//迭代给上层 //} //场景3.1.2:如果删除目标有2个孩子,已经不可能,前期已经进行前驱/后继调整过 //直接以1个NIL孩子条件跳转到了场景2或场景3 //场景3.1.3:如果删除目标没有孩子,则去审查父亲节点 //else //{ return remove_node_black_3_1_3(_pTarget);//迭代给上层 //} return nullptr; } //场景3:被删除节点是黑色, 且其兄弟是黑色 //场景3.1:兄弟节点的两个子节点都是黑色 //场景3.1.1:如果删除目标有1个孩子,那么这孩子必然是红色, 不可能是黑(非NIL) RBTreeNode<KEY, VALUE>* remove_node_black_3_1_1(RBTreeNode<KEY, VALUE>* _pTarget) { /* * 处理过程: 1.把目标正常删除 2.把唯一的红色子节点和父节点连接 3.然后把红色染黑,完成节点删除 */ RBTreeNode<KEY, VALUE>* pParent = _pTarget->m_pParent;//取出父节点 RBTreeNode<KEY, VALUE>* pChild = _pTarget->m_pLeft->isNIL() == false ? _pTarget->m_pLeft : _pTarget->m_pRight;//取出孩子 //把删除目标剥离出来 _pTarget->m_pParent = nullptr;//断开与父亲的联结 _pTarget->m_pLeft = nullptr;//断开左孩子的联结 _pTarget->m_pRight = nullptr;//断开右孩子的联结 pChild->m_pParent = pParent;//唯一的红孩子重定向父亲 if (!pParent)//如果父节点不存在,说明删除目标就是根节点 { m_pRoot = pChild;//重定向根节点 pChild->m_beLong = BELONG::ROOT;//设置成根节点 pChild->m_Color = COLOR::BLACK;//设置成黑色 return nullptr;//不用迭代修复, 上层退出迭代 } if (_pTarget->m_beLong == BELONG::LEFT)//如果删除目标是左孩子 { pParent->m_pLeft = pChild;//重定向删除目标的左孩子 pChild->m_beLong = BELONG::LEFT;//设置成父亲的左孩子 } else//否则删除目标是右孩子 { pParent->m_pRight = pChild;//重定向删除目标的右孩子 pChild->m_beLong = BELONG::RIGHT;//设置成父亲的右孩子 } pChild->m_Color = COLOR::BLACK;//把唯一的红孩子设置成黑色 return nullptr;//不用迭代修复, 告诉上层正常删除目标 } //场景3:被删除节点是黑色, 且其兄弟是黑色 //场景3.1:兄弟节点的两个子节点都是黑色 //场景3.1.3:如果删除目标没有孩子,则去审查父亲节点 RBTreeNode<KEY, VALUE>* remove_node_black_3_1_3(RBTreeNode<KEY, VALUE>* _pTarget) { RBTreeNode<KEY, VALUE>* pParent = _pTarget->m_pParent;//取出父节点 RBTreeNode<KEY, VALUE>* pBrother = _pTarget->m_beLong == BELONG::LEFT ? pParent->m_pRight : pParent->m_pLeft;//取出兄弟 /* 分支1: 如果父亲节点是红色 处理步骤: 1.正常删除节点 2.把兄弟节点染红,父亲染黑(父兄交换颜色) 3.完成删除 */ if (pParent->m_Color == COLOR::RED) { if(_pTarget->m_bIsDeleted)_pTarget->m_pParent = nullptr;//断开与父亲的联结 if (_pTarget->m_beLong == BELONG::LEFT)//如果删除目标是左孩子 { if (_pTarget->m_bIsDeleted)//如果已经被标记删除, 那么左孩子已经是NIL了 { pParent->m_pLeft = _pTarget->m_pLeft;//把父亲的左孩子重定向到NIL } } else//删除目标是右孩子 { if (_pTarget->m_bIsDeleted)//如果已经被标记删除, 那么左孩子已经是NIL了 { pParent->m_pRight = _pTarget->m_pRight;//把父亲的右孩子重定向到NIL } } pParent->m_Color = COLOR::BLACK; //父亲设置为黑色 pBrother->m_Color = COLOR::RED; //兄弟设置为红色 return nullptr;//不用迭代修复, 上层退出迭代 } /* 分支2: 如果父亲节点是黑色 处理步骤: 1.正常删除节点 2.将兄弟节点设为红色 3.将当前节点上移到父节点 4.把父亲当成删除目标, 迭代继续修复过程 */ else { if(_pTarget->m_bIsDeleted)_pTarget->m_pParent = nullptr;//断开与父亲的联结 if (_pTarget->m_beLong == BELONG::LEFT)//如果删除目标是左孩子 { if (_pTarget->m_bIsDeleted)//如果已经被标记删除, 那么左孩子已经是NIL了 { pParent->m_pLeft = _pTarget->m_pLeft;//重定向左路孩子到NIL } } else//否则删除目标是右孩子 { if (_pTarget->m_bIsDeleted)//如果已经被标记删除, 那么右孩子已经是NIL了 { pParent->m_pRight = _pTarget->m_pRight;//重定向右孩子到NIL } } pBrother->m_Color = COLOR::RED; //兄弟设置为红色 return pParent->m_beLong!=BELONG::ROOT ? pParent : nullptr;//把父亲当删除目标进行迭代修复树,如果是根节点,则上层退出迭代 } } // 场景3.2:近侄子是红色,远侄子是黑色(黑色可以是NIL) // 场景3.2.1:如果删除目标有1个孩子, 那么这孩子必然是红色,不可能是黑(非NIL) // 场景3.2.2:如果删除目标有2个孩子, 已经不可能,前期已经进行前驱/后继调整 // 场景3.2.3:如果删除目标没有孩子,则去审查父亲节点-父亲节点必定是红色 RBTreeNode<KEY, VALUE>* remove_node_black_3_2(RBTreeNode<KEY, VALUE>* _pTarget) { RBTreeNode<KEY, VALUE>* pParent = _pTarget->m_pParent;//取出父节点 RBTreeNode<KEY, VALUE>* pBrother = _pTarget->m_beLong == BELONG::LEFT ? pParent->m_pRight : pParent->m_pLeft;//取出兄弟 RBTreeNode<KEY, VALUE>* pNear = _pTarget->m_beLong == BELONG::RIGHT ? pBrother->m_pRight : pBrother->m_pLeft;//取得近侄子 //场景3.2.1:如果删除目标有1个孩子,那么这孩子必然是红色, 不可能是黑(非NIL) //if (_pTarget->m_pLeft->isNIL() == false || _pTarget->m_pRight->isNIL() == false)//删除目标拥有一个红色的孩子 //{ //return remove_node_black_3_1_1(_pTarget);//迭代给上层,因为场景3.1.1和场景3.2.1处理过程是一样的 //} //else //{ //场景3.2.3 //父亲必定是红色,所以不用重复审查,直接进行处理过程 //执行过程: //1.不要剥离目标, 只把兄弟进入旋转操作 //2.把兄弟设置红色, 近侄子设置黑色 //3.如果删除目标是左孩子,对父节点执行左旋 //如果删除目标是右孩子,对父节点执行右旋 //4.修复完成,退出循环 pBrother->m_Color = COLOR::RED; //兄弟设置为红色 pNear->m_Color = COLOR::BLACK; //近侄子设置为黑色 if (_pTarget->m_beLong == BELONG::LEFT)//如果删除目标是左孩子 { if (right_rotate(pBrother))//兄弟右旋,得到场景3.3 { return _pTarget;//迭代执行删除目标节点 - 进入场景3.3 } } else//否则删除目标是右孩子 { if (left_rotate(pBrother))//兄弟左旋,得到场景3.3 { return _pTarget;//迭代执行删除目标节点 - 进入场景3.3 } } //} return nullptr; } //场景3:被删除节点是黑色, 且其兄弟是黑色 //场景3.3:远侄子是红色,近侄子是黑色(黑色可以是NIL)或者红色都可以 //场景3.3没有其它分支 RBTreeNode<KEY, VALUE>* remove_node_black_3_3(RBTreeNode<KEY, VALUE>* _pTarget) { RBTreeNode<KEY, VALUE>* pParent = _pTarget->m_pParent;//取出父节点 RBTreeNode<KEY, VALUE>* pBrother = _pTarget->m_beLong == BELONG::LEFT ? pParent->m_pRight : pParent->m_pLeft;//取出兄弟 RBTreeNode<KEY, VALUE>* pFar = _pTarget->m_beLong == BELONG::RIGHT ? pBrother->m_pLeft : pBrother->m_pRight;//取得远侄子 //剥离删除目标 if(_pTarget->m_bIsDeleted)_pTarget->m_pParent = nullptr;//断开与父亲的联结 //处理步骤: //1.将兄弟设为红色 //2.将父亲设为黑色 //3.将远侄子设为黑色 //4.如果删除目标是左孩子,对父节点执行左旋 //如果删除目标是右孩子,对父节点执行右旋 //5.修复完成,退出循环 COLOR clrTmp = pParent->m_Color; pParent->m_Color = pBrother->m_Color;//父亲设置黑色 pBrother->m_Color = clrTmp;//兄弟设置红色 pFar->m_Color = COLOR::BLACK;//远侄子设置黑色 if (_pTarget->m_beLong == BELONG::LEFT)//如果删除目标是左孩子 { if (_pTarget->m_bIsDeleted)//如果删除目标已经被标记为删除 { pParent->m_pLeft = _pTarget->m_pLeft;//重定向父亲的左孩子到NIL } if (left_rotate(pParent))//父节点左旋, 完成修复 { return nullptr; } } else//不然就是右孩子,一个有父亲的,不可能是根节点ROOT { if (_pTarget->m_bIsDeleted)//如果删除目标已经被标记为删除 { pParent->m_pRight = _pTarget->m_pRight;//重定向父亲的右孩子到NIL } if (right_rotate(pParent))//父亲右旋,完成修复 { return nullptr; } } return nullptr;//修复完成 } public: bool Validate() const { if (!m_pRoot) return true; // 性质2: 根节点必须为黑 if (m_pRoot->m_Color != COLOR::BLACK) { std::cerr << "Violation: Root is not black" << std::endl; return false; } int refBlackCount = -1; // 参考黑高 return CheckProperties(m_pRoot, 0, refBlackCount); } private: bool CheckProperties(RBTreeNode<KEY, VALUE>* node, int currentBlack, int& refBlackCount) const { // 到达NIL节点(视为黑色) if (node->isNIL()) { // 首次设置参考黑高 if (refBlackCount == -1) { refBlackCount = currentBlack; return true; } // 性质5: 验证黑高一致 if (currentBlack != refBlackCount) { std::cerr << "Black height violation: " << currentBlack << " vs " << refBlackCount << std::endl; return false; } return true; } // 性质4: 红色节点不能有红子节点 if (node->m_Color == COLOR::RED) { if ((!node->m_pLeft->isNIL() && node->m_pLeft->m_Color == COLOR::RED) || (!node->m_pRight->isNIL() && node->m_pRight->m_Color == COLOR::RED)) { std::cerr << "Red violation at node: " << node->m_Key << std::endl; return false; } } // 更新当前黑高 int newBlack = currentBlack + (node->m_Color == COLOR::BLACK ? 1 : 0); // 递归检查左右子树 return CheckProperties(node->m_pLeft, newBlack, refBlackCount) && CheckProperties(node->m_pRight, newBlack, refBlackCount); } }; } #endif // !_RBTREE_H_ 先分析我的代码,再根据代码帮我设计一个迭代器