🦖 红黑树概念
红黑树是一棵较为复杂的树;
其与AVL树相同,也为一棵平衡搜索二叉树;
其与AVL树不同的是,在AVL树中依靠平衡因子bf(Balance Factor)来保证树的结构始终保持为一个高度平衡的状态(每个节点的左右子树高度差不超过1);
而对于红黑树来说,其在节点当中存储了一个颜色,颜色不为红则为黑,根据颜色制定了一系列的规则;
其最终的结果为,在红黑树当中其的最长路径不会超过最短路径的两倍;
可以从这个最终的结果看出,对于红黑树来说其并不是一棵高度平衡的二叉树,相对其只是一棵较为平衡的二叉树;
以该图为例,该图即为一棵红黑树,其具有搜索二叉树的属性;
在上文中提到,红黑树中存在一系列的规则,通过一系列的规则来约束树的结构使其最终能够达到一棵树的最长路径长度不会超过最短路径的二倍;
其规则如下:
- 红黑树的节点不是红色就是黑色;
- 根节点的颜色是黑色;
- 如果一个节点为红色,其两个孩子节点必定为黑色;
- 对于每一个节点,从该节点到所有后代叶节点的简单路径上,都包含相同数目的黑色节点;
- 每个叶子节点的颜色都是黑色;
在该处的叶子节点所指的并不是平时在树的结构中所说的最后一个非空节点,在红黑树当中所谓的叶子节点即为空节点,在此处以NIL表示;
根据上面的规则来看,上图中的树都符合这几条规则,上图中的树为一棵红黑树;
- 为什么当符合上面五条规则时,其树的结构的最终结果就能保证其最长路径中的节点个数不会超过最短路径节点个数的2倍?
以该图为例,该图为一棵红黑树,其符合上述的五条规则;
在该树当中绘出了两条路径,其中最左侧的黄色路径为其中一条的最长路径;最右侧的蓝色路径为其中一条最短路径;
对于5条规则中的第四条规则对于每一个节点,从该节点到所有后代叶节点的简单路径上,都包含相同数目的黑色节点,与最终的结果最长路径长度不会超过最短路径的二倍中的黑色节点都包含其中叶子节点的NIL节点;
如此所见,最长路径的长度为5,最短路径的长度为3;
可以得出问题中所提到的问题;
从上文可知,红黑树的平衡程度不比AVL树;
AVL树为高度平衡搜索二叉树,而红黑树只是近似平衡搜索二叉树,但在实际的使用场景当中,大多数情况都会使用红黑树而不是AVL树,原因如下:
- 插入删除操作的难易程度
当红黑树和AVL树都处于一种规则被破坏的情况下都要使用一些处理手段使其恢复平衡状态;
对于红黑树来说,红黑树的整体结构与规则处于一种近似平衡的状态而不是高度平衡的状态,这使得红黑树能够允许树在一些情况中不是那么的平衡(最长路径不超过最短路径的2倍);
而对于AVL树来说,其的平衡为高度平衡状态,虽然说在高度平衡的状态对于数据的读取效率要高于红黑树,但也暴露出来一些问题;
由于AVL树中节点的平衡因子的绝对值不能大于1,即每当平衡因子的绝对值为2时表示这棵树破坏了AVL树的高度平衡状态,需要对树进行一定的旋转操作使得恢复其本身的高度平衡状态;
但是就是因为每次在少次插入过后都要进行一次旋转从而降低了AVL树在插入数据情况中的效率; - 维护成本
在维护成本当中,由于AVL树中存在平衡因子,所以每次插入的时候都需要判断新插入节点是否影响其祖先节点的平衡因子致使其不平衡;
而对于红黑树而言,红黑树中判断是否符合规则的为节点的颜色;
由于默认插入节点的颜色都为红色,只需要判断这个红色的节点是否影响破坏红黑树本身的规则,若是新插入的节点破坏了其整棵树(子树)的规则结构则对树(子树)的结构进行处理即可;
两者相比较实际上AVL树的维护成本要高于红黑树,在特殊情况中AVL树的结构可能在实现过程中其可能因为平衡因子未正确更新从而可能导致整棵树的结构被破坏;
故AVL树的维护成本高于红黑树; - 综合性能
综上所述,红黑树的综合性能高于AVL树,其处于一种较为平衡的状态;
在极端情况当中,AVL树可能会因为插入大量数据而引发大量的旋转操作导致效率的下降,但红黑树可以很好的避免这个问题;
当然就算是查找一个数据的情况下红黑树只是略逊AVL树一点;
🦖 红黑树节点的定义
从上文可知,红黑树的节点与AVL树的节点设置的不同点为:
- AVL树
AVL树采用的是利用平衡因子来控制; - 红黑树
红黑树采用的是以颜色来判断树的结构;
由上文概念中几个规则可能引出一个问题:
- 红黑树中的新节点应该是什么颜色?
黑色?
红色?
从上文中的规则关于节点的颜色中有这么两条规则:
- 如果一个节点为红色,其两个孩子节点必定为黑色;
- 对于每一个节点,从该节点到所有后代叶节点的简单路径上,都包含相同数目的黑色节点;
根据这两个规则进行引入,权衡利弊可以发现新节点无论是黑色还是红色都有可能违反两条规则中的其中一条规则;
但是对于两条规则的违反代价来说,新节点为黑色的代价要高于新节点为红色的代价;
当新节点为黑色的时候由于每条简单路径的黑色节点数量要相同,所以当插入新节点为黑色节点时其他的简单路径上必须也插入同样的新黑色节点;
而若是新节点为红色时则只需要对树的结构进行处理即可;
故新节点的颜色应该为红色;
- 插入过程中宁可违反规则
3,也不违反规则4;
代码段:
enum COLOR{ //红黑树的颜色控制,采用枚举确保颜色只能是红或黑 RED, BLACK }; /* 红黑树是搜索二叉树; 同时红黑树利用颜色控制二叉树的平衡; 红黑树确保没有一条路径会比其他路径长出二倍; 不为高度平衡 而为近似平衡; */ /* 红黑树的规则: 1.每个节点不是红色就是黑色; 2.根节点是黑色; 3.如果一个节点是红色的,则它的两个孩子节点是黑色; 4.对于每个节点,从该节点到其所有后代节点的简单路径上,均包含相同数目的黑色节点 5.每个叶子节点都是黑色的(这里的叶子节点指的是空节点NIL) 为什么满足上面的性质红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍? 最短路径即为全黑路径 最长路径可以指的是红黑相接的路径 假设存在N个黑色节点的话(包括NIL空节点),则红黑相间的红色节点个数为N-1,则最终的节点个数为2N-1; */ template<class K,class V> struct RBTreeNode{ RBTreeNode<K, V> *_left; RBTreeNode<K, V> *_right; RBTreeNode<K, V> *_parent; std::pair<K,V> _kv; COLOR _col; RBTreeNode(const std::pair<K,V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_col(RED)//给定缺省值默认为红色 {} /* 节点颜色默认值为新增的节点为红色还是黑色的问题 这是选择违反红黑树规则中规则3和规则4的问题,权衡利弊宁可违反规则3也不违反规则4; */ }; template<class K,class V> class RBTree{ //红黑树整体模型 typedef RBTreeNode<K,V> Node; public: ~RBTree(); Node *Find(const K &key); bool Insert(const std::pair<K,V>& kv); bool IsBalance(); protected: void RotateL(Node *parent); void RotateR(Node *parent); void _Destory(Node* &root); private: Node* _root = nullptr; }
本文中的红黑树实现一样采用key value模型进行演示;
🦖 红黑树的插入
红黑树也是基于搜索二叉树后控制其平衡条件的一种二叉树;
其插入模式与逻辑与搜索二叉树相同;
与之不同的是由于红黑树的新节点插入为红色节点,所以插入过程当中可能违反红黑树五条规则中的第三条规则;
- 如果一个节点为红色,其两个孩子节点必定为黑色;
即可能发生红色节点的孩子节点也为红色节点,在这种情况当中就要对树的结构进行对应的调整更新使其恢复原来的近似平衡状态;
- 代码段
bool Insert(const std::pair<K,V>& kv){ if(_root == nullptr){ _root = new Node(kv); _root->_col = BLACK; return true; } Node *cur = _root; Node *parent = nullptr; while(cur){ if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right; } else if(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left; } else{ return false; } } cur = new Node(kv); if(parent->_kv.first < kv.first){ parent->_right = cur; cur->_parent = parent; } else{ parent->_left = cur; cur->_parent = parent; } //...... /* 判断与处理 */ return true; }
当插入的动作结束后应该及时判断新增节点是否影响整棵红黑树的结构;
由于新增节点为红色节点,所以只需判断节点是否破坏红黑树规则中的规则3即可;
即判断新增节点的父亲节点是否为红色:
- 不为红色
若是新增节点的父亲节点不为红色,则说明该次插入并不影响红黑树的规则,算是一次正常插入; - 为红色
若是新增节点的父亲节点为红色节点,说明该次插入违反了红黑树规则中的第三条规则,需要对树(子树)进行调整使其恢复原来的红黑树;
当红黑树的第三条规则被违反时将会出现几种情况;
下图为一张抽象图,其中uncle表示一棵子树;
以单边为例,该图即为单边(左边)可能出现的违反第三条规则的情况;
🦖 数据插入后的调整
在上文中提到了当数据插入结束后需要对插入的新节点进行判断,由于插入方式的问题(节点的颜色),所以需要对新节点的位置判断其是否存在违反第三条规则的情况;
从该图中可以看到,对于红黑树的处理方式与AVL的调整方式不同,因为对于红黑树而言主要是需要对节点进行重新着色;
同时在此基础上对树(子树)在需要的情况下对其进行旋转操作;
从图中可以发现在红黑树中重点看几个节点:
cur节点
新增节点parent节点
新增节点的父亲节点grandfather节点
新增节点的祖父节点uncle节点
新增节点的父亲节点的兄弟节点
而在红黑树当中,重点所看的节点就算所谓的uncle节点叔叔节点;
这个节点决定了红黑树在违反了规则之后需要使用哪种方式对树(子树)进行调整;
而红黑树的调整方法中uncle节点扮演着重要的作用,若是没有使用或者关注uncle节点,则可能使用错误的调整方案使得红黑树的结构变得更加的混乱;
下面的例子主要以单边为例,对于红黑树的调整来说不重点对节点的位置进行处理而是对于uncle节点来进行处理;
🦕 情况一:ucnle存在且为红
当出现这种情况时即cur新增节点与其父亲节点parent节点的颜色为红色;
且在这种情况当中uncle节点存在且该节点的颜色为红色;
以该图为例;
其中这种情况下对于树(子树)的处理情况是最简单的,只需要对节点进行重新着色即可,即:
parent节点变黑uncle节点变黑cur节点变红
根据上面三步的操作即可完成该情况的解决方式;
- 为什么说这个方式是最容易处理的情况?
出现这种情况时由于解决的方式只需要对节点进行重新着色即可,并不需要对节点的方向进行判断;
即cur节点在parent节点的左右方向,出现这种情况都可以使用该方式进行解决,可以对其进行单独的if条件语句判断; - 代码段
while(parent && parent->_col == RED){ //由于默认插入的节点为红色 所以当parent节点存在且为红色时表示需要进行调整 Node *grandfather = parent->_parent;//根节点必须为黑色 所以说明该节点上还有节点 if(grandfather->_left == parent){ Node *uncle = grandfather->_right; //插入时颜色的变化分三种情况 if(uncle && uncle->_col == RED){ /* uncle存在且为红 当uncle存在且为红的时候，说明cur节点为新增节点 这时候的处理方式只需要对节点进行变色处理即可 将parent节点与uncle节点变黑 uncle节点变红 */ parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else{//uncle节点不存在或者uncle节点为黑色 //...... } break; } } else{ // if(grandfather->_right == parent){ Node *uncle = grandfather->_left; if (uncle && uncle->_col == RED){ parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else{//uncle节点不存在或者uncle节点为黑色 //...... break; } } } _root->_col = BLACK; return true; }
当处理完之后应继续向上更新节点位置:
cur节点更新为当前的grandfather节点;parent节点更新为新的cur节点的_parent节点;
并按照循环来判断该处解决之后是否需要再向上进行解决
- 若是
parent节点不为空且parent节点为红色时则继续向上更新; - 若是
parent节点为空或是parent节点存在且为黑色时说明该树(子树)不存在问题,插入环节结束;
🦕 情况二:uncle不存在或uncle存在且为黑
当出现这种情况时,简单的对节点进行重新着色的方案就不予推荐;
因为出现这种情况时无论如何对节点进行重新着色都将不可能将树(子树)的结构恢复为原来的红黑树结构;
当出现这种情况时则说明树的结构已经趋于不平衡,需要借助到在AVL树种所提到的旋转方案;
且出现该情况后需要进行判断cur节点存在于parent节点的左边还是右边:
cur存在于parent节点的左边
当cur节点存在于parent节点的左侧时则需要进行单旋操作;cur存在于parent节点的右边
当cur节点存在于parent节点的右侧时则需要进行双旋操作;
根据cur节点所处的位置来判断需要进行单旋还是双旋操作;
当然若是需要进行双旋时双旋的顺序判断取决于是grandfather的左子树出现问题还是该节点的右子树出现问题;
- 为什么uncle不存在和uncle存在且为黑两种情况可以用同一种方案进行解决?
实际上在操作中uncle不存在 与uncle存在且为黑的情况可以用同一种方式进行解决是因为其构造是相同的,只不过一个具有节点一个没有节点;uncle节点不存在的情况下cur节点可能是新增节点;
而uncle节点存在且为黑的情况其一定是由情况一变化而来,即情况一解决后向上更新所发现的新情况;
该图即为单边情况下子树出现问题的解决办法的图例(具象图);
- 代码段
while(parent && parent->_col == RED){ //由于默认插入的节点为红色 所以当parent节点存在且为红色时表示需要进行调整 Node *grandfather = parent->_parent;//根节点必须为黑色 所以说明该节点上还有节点 if(grandfather->_left == parent){ Node *uncle = grandfather->_right; //插入时颜色的变化分三种情况 if(uncle && uncle->_col == RED){ /* uncle存在且为红 */ } else{// (uncle == nullptr || uncle->_col == BLACK) /* 另一种情况即为uncle节点不存在或者uncle节点存在且为黑色节点 当uncle节点不存在时说明cur节点为新增节点 当uncle节点存在但是节点颜色为黑色时说明cur节点不为新增节点 而是由情况1变化而来; 这两种情况虽然cur节点的状态不同但是真正意义上来说两者在处理方式可以以相同的方式进行处理 但是uncle节点不存在或是uncle存在且为黑的情况虽然统一采取同一种方式进行处理 但是还将这种处理方式进行两种情况的划分 分别为cur节点处于parent节点的左子树还是右子树 通过左子树或者是右子树取决于使用的措施是采用单选操作还是双旋操作 */ if(cur == parent->_left){ RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else{ // cur == parent->_left RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else{ // if(grandfather->_right == parent){ Node *uncle = grandfather->_left; if (uncle && uncle->_col == RED){ /* uncle存在且为红 */ } else{// (uncle == nullptr || uncle->_col == BLACK) if(cur == parent->_right){ RotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else{ RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; }
当 uncle不存在 或 是uncle存在且为黑 的两种情况处理后则可以直接break退出循环;
🦕 插入函数代码段(参考)
bool Insert(const std::pair<K,V>& kv){ if(_root == nullptr){ _root = new Node(kv); _root->_col = BLACK; return true; } Node *cur = _root; Node *parent = nullptr; while(cur){ if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right; } else if(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left; } else{ return false; } } cur = new Node(kv); if(parent->_kv.first < kv.first){ parent->_right = cur; cur->_parent = parent; } else{ parent->_left = cur; cur->_parent = parent; } while(parent && parent->_col == RED){ //由于默认插入的节点为红色 所以当parent节点存在且为红色时表示需要进行调整 Node *grandfather = parent->_parent;//根节点必须为黑色 所以说明该节点上还有节点 if(grandfather->_left == parent){ Node *uncle = grandfather->_right; //插入时颜色的变化分三种情况 if(uncle && uncle->_col == RED){ /* uncle存在且为红 当uncle存在且为红的时候，说明cur节点为新增节点 这时候的处理方式只需要对节点进行变色处理即可 将parent节点与uncle节点变黑 uncle节点变红 */ parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else{ // if(uncle == nullptr || uncle->_col == BLACK) /* 另一种情况即为uncle节点不存在或者uncle节点存在且为黑色节点 当uncle节点不存在时说明cur节点为新增节点 当uncle节点存在但是节点颜色为黑色时说明cur节点不为新增节点 而是由情况1变化而来; 这两种情况虽然cur节点的状态不同但是真正意义上来说两者在处理方式可以以相同的方式进行处理 但是uncle节点不存在或是uncle存在且为黑的情况虽然统一采取同一种方式进行处理 但是还将这种处理方式进行两种情况的划分 分别为cur节点处于parent节点的左子树还是右子树 通过左子树或者是右子树取决于使用的措施是采用单选操作还是双旋操作 */ if(cur == parent->_left){ RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else{ // cur == parent->_left RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else{ // if(grandfather->_right == parent){ Node *uncle = grandfather->_left; if (uncle && uncle->_col == RED){ parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else{ // if(uncle == nullptr || uncle->_col == BLACK) if(cur == parent->_right){ RotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else{ RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; }
🦕 旋转操作代码段(参考)
void RotateL(Node *parent){ Node *cur = parent->_right; Node *curleft = cur->_left; parent->_right = curleft; if (curleft) { curleft->_parent = parent; } cur->_left = parent; Node *ppnode = parent->_parent; parent->_parent = cur; if (parent == _root) { _root = cur; cur->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } cur->_parent = ppnode; } } void RotateR(Node *parent){ Node *cur = parent->_left; Node *curright = cur->_right; parent->_left = curright; if (curright) curright->_parent = parent; Node *ppnode = parent->_parent; cur->_right = parent; parent->_parent = cur; if (ppnode == nullptr) { _root = cur; cur->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } cur->_parent = ppnode; } }
旋转操作中无需像AVL树那样关心对应的平衡因子;
🦖 判断红黑树是否符合规则
与AVL树相同,当一棵红黑树被创建完毕之后若是只用中序遍历来判断的话只能判断出该树是否为搜索二叉树,但是不能保证出所创建出的树是一棵红黑树;
对于红黑树是否平衡的判断一样可以利用一个接口去是先解决;
当然判断红黑树是否平衡的方法多种多样;
其中在本文章的方法即为: 利用一个pair<bool,vector<int>>对象来存储结果,最终返回pair中的bool结果,当然该中方式也需要用到子函数来完成其他的判断:
bool IsBalance(){ //... }
- 判断根节点
_root节点的颜色是否为黑色:
若是该节点的颜色为红色则直接返回false; - 判断是否存在连续的红色节点与每条简单路径当中是否存在相同个数的黑色节点:
定义一个Check()子函数用来判断是否出现连续的红色节点;
传递一个blackNum变量用来记录每条简单路径的黑色节点个数;Check()函数传递了一个pair<bool,vector<int>>对象的引用,为了能在函数之中利用其中的vector<int>来判断每条简单路径上是否存在相同的黑色节点数量;bool则是用来判断是否存在连续相同的红色节点;
利用递归的思路,当节点为nullptr空时vector<int>部分添加对应的blackNum黑色节点个数;
void _Check(std::pair<bool,std::vector<int>> &ret,Node *root,size_t blackNum = 0){ if(root == nullptr){ ret.first = ret.first && true; ret.second.push_back(blackNum); return; } if(root->_col == RED && root->_parent->_col == RED){ ret.first = ret.first && false; return ; } if(root->_col == BLACK){ blackNum++; } _Check(ret, root->_left, blackNum); _Check(ret, root->_right, blackNum); }
- 最终对该
pair对象进行判断即可;
- 代码段
bool IsBalance(){ if(_root == nullptr){ return true; } if(_root && _root->_col == RED){ //头节点为红色节点说明树的插入或者某次旋转后的颜色变化出现问题 return false; } std::pair<bool,std::vector<int>> ret ; ret.first = true; _Check(ret,_root,0); if(!ret.first){ std::cout << "某一路径出现连续红色节点" << std::endl; } bool to_comp = true; size_t _comp = ret.second[0]; for(auto &it : ret.second){ if(it != _comp){ to_comp = false; break; } std::cout << it << std::endl; } return to_comp && ret.first; }
当然可以使用其他方法,并在对应的出现错误的位置根据条件使用assert(false)断言断死来排查问题所在;
🦖 红黑树的析构函数
红黑树的析构函数只需要写一个_Destroy()函数并在析构函数中进行调用即可;
当然_Destroy()函数采用后序遍历的方式对节点逐个进行释放;
void _Destory(Node* &root){ if(root == nullptr){ return ; } _Destory(root->_left); _Destory(root->_right); delete root; root = nullptr; }
🦖 完整代码(供参考)
该段代码中由于测试需要定义了一些非必要的函数;
#include<iostream> #include<vector> enum COLOR{ //红黑树的颜色控制,采用枚举确保颜色只能是红或黑 RED, BLACK }; /* 红黑树是搜索二叉树; 同时红黑树利用颜色控制二叉树的平衡; 红黑树确保没有一条路径会比其他路径长出二倍; 不为高度平衡 而为近似平衡; */ /* 红黑树的规则: 1.每个节点不是红色就是黑色; 2.根节点是黑色; 3.如果一个节点是红色的,则它的两个孩子节点是黑色; 4.对于每个节点,从该节点到其所有后代节点的简单路径上,均包含相同数目的黑色节点 5.每个叶子节点都是黑色的(这里的叶子节点指的是空节点NIL) 为什么满足上面的性质红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍? 最短路径即为全黑路径 最长路径可以指的是红黑相接的路径 假设存在N个黑色节点的话(包括NIL空节点),则红黑相间的红色节点个数为N-1,则最终的节点个数为2N-1; */ template<class K,class V> struct RBTreeNode{ RBTreeNode<K, V> *_left; RBTreeNode<K, V> *_right; RBTreeNode<K, V> *_parent; std::pair<K,V> _kv; COLOR _col; RBTreeNode(const std::pair<K,V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_col(RED)//给定缺省值默认为红色 {} /* 节点颜色默认值为新增的节点为红色还是黑色的问题 这是选择违反红黑树规则中规则3和规则4的问题,权衡利弊宁可违反规则3也不违反规则4; */ }; template<class K,class V> class RBTree{ typedef RBTreeNode<K,V> Node; public: ~RBTree(){ _Destory(_root); } void InOrder(){ _InOrder(_root); } Node *Find(const K &key){ Node* cur = _root; while(cur){ if(key>cur->_kv.first){ cur = cur->_right; } else if(key<cur->_kv.first){ cur = cur->_left; } else{ return cur; } } return nullptr; } bool Insert(const std::pair<K,V>& kv){ if(_root == nullptr){ _root = new Node(kv); _root->_col = BLACK; return true; } Node *cur = _root; Node *parent = nullptr; while(cur){ if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right; } else if(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left; } else{ return false; } } cur = new Node(kv); if(parent->_kv.first < kv.first){ parent->_right = cur; cur->_parent = parent; } else{ parent->_left = cur; cur->_parent = parent; } while(parent && parent->_col == RED){ //由于默认插入的节点为红色 所以当parent节点存在且为红色时表示需要进行调整 Node *grandfather = parent->_parent;//根节点必须为黑色 所以说明该节点上还有节点 if(grandfather->_left == parent){ Node *uncle = grandfather->_right; //插入时颜色的变化分三种情况 if(uncle && uncle->_col == RED){ /* uncle存在且为红 当uncle存在且为红的时候，说明cur节点为新增节点 这时候的处理方式只需要对节点进行变色处理即可 将parent节点与uncle节点变黑 uncle节点变红 */ parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else{ // if(uncle == nullptr || uncle->_col == BLACK) /* 另一种情况即为uncle节点不存在或者uncle节点存在且为黑色节点 当uncle节点不存在时说明cur节点为新增节点 当uncle节点存在但是节点颜色为黑色时说明cur节点不为新增节点 而是由情况1变化而来; 这两种情况虽然cur节点的状态不同但是真正意义上来说两者在处理方式可以以相同的方式进行处理 但是uncle节点不存在或是uncle存在且为黑的情况虽然统一采取同一种方式进行处理 但是还将这种处理方式进行两种情况的划分 分别为cur节点处于parent节点的左子树还是右子树 通过左子树或者是右子树取决于使用的措施是采用单选操作还是双旋操作 */ if(cur == parent->_left){ RotateR(grandfather); // parent->_col = RED; // grandfather->_col = cur->_col = BLACK; parent->_col = BLACK; grandfather->_col = RED; } else{ // cur == parent->_left RotateL(parent); RotateR(grandfather); // cur->_col = RED; // grandfather->_col = BLACK; // parent->_col = BLACK; cur->_col = BLACK; grandfather->_col = RED; } break; } } else{ // if(grandfather->_right == parent){ Node *uncle = grandfather->_left; if (uncle && uncle->_col == RED){ parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else{ // if(uncle == nullptr || uncle->_col == BLACK) if(cur == parent->_right){ RotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else{ RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; } bool IsBalance(){ if(_root == nullptr){ return true; } if(_root && _root->_col == RED){ //头节点为红色节点说明树的插入或者某次旋转后的颜色变化出现问题 return false; } std::pair<bool,std::vector<int>> ret ; ret.first = true; _Check(ret,_root,0); if(!ret.first){ std::cout << "某一路径出现连续红色节点" << std::endl; } bool to_comp = true; size_t _comp = ret.second[0]; for(auto &it : ret.second){ if(it != _comp){ to_comp = false; break; } std::cout << it << std::endl; } return to_comp && ret.first; } int getHeight() { return getHeight(_root); } protected: void RotateL(Node *parent){ Node *cur = parent->_right; Node *curleft = cur->_left; parent->_right = curleft; if (curleft) { curleft->_parent = parent; } cur->_left = parent; Node *ppnode = parent->_parent; parent->_parent = cur; if (parent == _root) { _root = cur; cur->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } cur->_parent = ppnode; } } void RotateR(Node *parent){ Node *cur = parent->_left; Node *curright = cur->_right; parent->_left = curright; if (curright) curright->_parent = parent; Node *ppnode = parent->_parent; cur->_right = parent; parent->_parent = cur; if (ppnode == nullptr) { _root = cur; cur->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } cur->_parent = ppnode; } } void _InOrder(Node *root){ if(root == nullptr) return ; _InOrder(root->_left); std::cout << root->_kv.first << " : " << root->_kv.second << " col : " << root->_col << std::endl; _InOrder(root->_right); } void _Check(std::pair<bool,std::vector<int>> &ret,Node *root,size_t blackNum = 0){ if(root == nullptr){ ret.first = ret.first && true; ret.second.push_back(blackNum); return; } if(root->_col == RED && root->_parent->_col == RED){ ret.first = ret.first && false; return ; } if(root->_col == BLACK){ blackNum++; } _Check(ret, root->_left, blackNum); _Check(ret, root->_right, blackNum); } int getHeight(Node *root) { if (root == nullptr) { return 0; } int left = getHeight(root->_left); int right = getHeight(root->_right); return left > right ? left + 1 : right + 1; } void _Destory(Node* &root){ if(root == nullptr){ return ; } _Destory(root->_left); _Destory(root->_right); delete root; root = nullptr; } private: Node* _root = nullptr; };
