财务网站模板,泉州小程序开发,红色扁平化网站,溧阳手机网站哪里做本文承接自#xff1a; 算法实战#xff1a;亲自写红黑树之一-CSDN博客 算法实战#xff1a;亲自写红黑树之二 完整代码-CSDN博客 算法实战#xff1a;亲自写红黑树之三 算法详解-CSDN博客 算法实战#xff1a;亲自写红黑树之四 插入insert的平衡-CSDN博客
目录
一、入口… 本文承接自 算法实战亲自写红黑树之一-CSDN博客 算法实战亲自写红黑树之二 完整代码-CSDN博客 算法实战亲自写红黑树之三 算法详解-CSDN博客 算法实战亲自写红黑树之四 插入insert的平衡-CSDN博客
目录
一、入口
二、删除
三、转换中间节点左右子树都存在
四、简单情形
五、复杂情形 一、入口 有几个不同参数的删除入口 bool erase(const_iterator it){T_COMP comp;return erase(it, comp);}//删除并指向下一个iterator DeleteAndMoveNext(iterator it){if (end() it)return it;iterator ret it;iterator tmp ret;ret;erase(tmp);return ret;}bool erase(const_iterator it, T_COMP comp){if (it.handle 0)return true;//DEBUG_LOG要删除节点show(it.handle)endi;bool ret _erase(it.handle);return ret;}bool erase(T_DATA const data){T_COMP comp;return erase(data, comp);}bool erase(T_DATA const data, T_COMP comp){const_iterator it find(data, comp);if (it.handle 0)return true;return erase(it, comp);}最终都进入_erase(h)直接删除一个节点。 在到达这一步之前要先找到要删除的节点这个属于二叉树的标准算法很简单。
二、删除 删除的控制代码 //删除bool _erase(T_SHM_SIZE position){string report;//DEBUG_LOG开始删除....Report(report) endi;bool vLeft;//删除的节点是左子节点bool vRed;//删除的节点是红色T_SHM_SIZE p TREE_NODE::at(position).hParent;//父节点T_SHM_SIZE u;//替换节点bool uRed;//替换节点是红色-1为黑色if (TREE_NODE::at(position).hLeft ! -1 TREE_NODE::at(position).hRight ! -1){debug_log 左右都存在替换为左子树最大值 endi;if (!__erase_change_middle(position, vLeft, vRed, u, uRed, p))return false;debug();return _erase(position);}else if (-1 TREE_NODE::at(position).hLeft -1 TREE_NODE::at(position).hRight){vLeft TREE_NODE::at(position).isLeft();vRed TREE_NODE::at(position).bColorRed;u -1;uRed false;if (-1 p){debug_log 最后一个节点 endi;tree_head-hHead -1;vRed true;//阻止后面继续处理删除红色无需额外处理}else{debug_log 叶子节点 endi;if (TREE_NODE::at(position).isLeft())TREE_NODE::at(p).hLeft -1;else TREE_NODE::at(p).hRight -1;}}else{vLeft TREE_NODE::at(position).isLeft();vRed TREE_NODE::at(position).bColorRed;if (-1 ! TREE_NODE::at(position).hLeft){debug_log 左子树存在 endi;u TREE_NODE::at(position).hLeft;}else{debug_log 右子树存在 endi;u TREE_NODE::at(position).hRight;}if (-1 p){debug_log 根节点 endi;tree_head-hHead u;}else{if (vLeft)TREE_NODE::at(p).hLeft u;else TREE_NODE::at(p).hRight u;}TREE_NODE::at(u).hParent p;uRed TREE_NODE::at(u).bColorRed;p TREE_NODE::at(u).hParent;}bool ret true;if (vRed){debug_log 删除红色节点不用调整 endi;}else if (!vRed uRed){debug_log 删除黑色节点替换节点红色改为黑色 endi;TREE_NODE::at(u).bColorRed false;}else{debug_log 删除双黑节点 endi;ret _RB_erase_Balance(p, u);}debug();if (ret)__erase_node(position);if (-1 ! tree_head-hHead)TREE_NODE::at(tree_head-hHead).bColorRed false;return ret;}这个函数的逻辑分为两部分
分析要删除的节点的分支情况将左右节点都存在的情形改为删除叶子数据节点不是红黑树意义的叶子节点指一般意义的叶子节点然后确定删除节点和替换节点。根据删除节点和替换节点的颜色进行处理黑节点减少则需要平衡。
三、转换中间节点左右子树都存在 很容易把中间节点替换掉跟左子树最大值或者右子树最小值交换即可。 本代码用__erase_change_middle(h)函数做这件事将颜色也做了交换逻辑上相当于不改变结构数据只交换用户数据但是我们的用户数据一般都很大所以反过来操作改变了除用户数据以外的所有结构数据执行完毕后红黑树结构仍然正确删除节点变成了最多只有一个子树的节点。 //删除中间节点将中间节点替换为左子树最大值数据不动改变树结构bool __erase_change_middle(T_SHM_SIZE const position, bool vLeft, bool vRed, T_SHM_SIZE u, bool uRed, T_SHM_SIZE p){string tmp;T_SHM_SIZE new_position TREE_NODE::at(position).hLeft;if (-1 ! new_position){while (-1 ! TREE_NODE::at(new_position).hRight){new_position TREE_NODE::at(new_position).hRight;}}debug_log position position new_position new_position endi;debug_log position position TREE_NODE::at(position).toString(tmp) endi;debug_log new_position new_position TREE_NODE::at(new_position).toString(tmp) endi;vLeft false;vRed TREE_NODE::at(new_position).bColorRed;p TREE_NODE::at(new_position).hParent;debug_log p TREE_NODE::at(p).toString(tmp) endi;if (p ! position){debug_log 非直接对调 p TREE_NODE::at(p).toString(tmp) ende;TREE_NODE t;t._CopyWithoutData(TREE_NODE::at(new_position));TREE_NODE::at(new_position)._CopyWithoutData(TREE_NODE::at(position));TREE_NODE::at(position)._CopyWithoutData(t);debug_log position TREE_NODE::at(position).toString(tmp) endi;debug_log new_position TREE_NODE::at(new_position).toString(tmp) endi;//注意这里无法用isLeft来判断因为父节点的hLeft和hRight是旧数据if (TREE_NODE::at(new_position).hParent ! -1){if (TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft position)TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft new_position;else TREE_NODE::at(TREE_NODE::at(new_position).hParent).hRight new_position;}if (TREE_NODE::at(position).hParent ! -1){if (TREE_NODE::at(TREE_NODE::at(position).hParent).hLeftnew_position)TREE_NODE::at(TREE_NODE::at(position).hParent).hLeft position;else TREE_NODE::at(TREE_NODE::at(position).hParent).hRight position;}if (TREE_NODE::at(new_position).hLeft ! -1)TREE_NODE::at(TREE_NODE::at(new_position).hLeft).hParent new_position;if (TREE_NODE::at(position).hLeft ! -1)TREE_NODE::at(TREE_NODE::at(position).hLeft).hParent position;if (TREE_NODE::at(new_position).hRight ! -1)TREE_NODE::at(TREE_NODE::at(new_position).hRight).hParent new_position;if (TREE_NODE::at(position).hRight ! -1)TREE_NODE::at(TREE_NODE::at(position).hRight).hParent position;}else{debug_log 直接对调 p TREE_NODE::at(p).toString(tmp) endi;TREE_NODE t;t._CopyWithoutData(TREE_NODE::at(new_position));TREE_NODE::at(new_position)._CopyWithoutData(TREE_NODE::at(position));TREE_NODE::at(position)._CopyWithoutData(t);debug_log position TREE_NODE::at(position).toString(tmp) endi;debug_log new_position TREE_NODE::at(new_position).toString(tmp) endi;//注意这里无法用isLeft来判断因为父节点的hLeft和hRight是旧数据if (TREE_NODE::at(new_position).hParent ! -1){if (TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft position)TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft new_position;else TREE_NODE::at(TREE_NODE::at(new_position).hParent).hRight new_position;}TREE_NODE::at(position).hParent new_position;TREE_NODE::at(new_position).hLeftposition;if (TREE_NODE::at(position).hLeft ! -1)TREE_NODE::at(TREE_NODE::at(position).hLeft).hParent position;if (TREE_NODE::at(new_position).hRight ! -1)TREE_NODE::at(TREE_NODE::at(new_position).hRight).hParent new_position;if (TREE_NODE::at(position).hRight ! -1)TREE_NODE::at(TREE_NODE::at(position).hRight).hParent position;}//如果是根节点if (-1 TREE_NODE::at(new_position).hParent){TREE_NODE::at(new_position).bColorRed false;tree_head-hHead new_position;}debug_log position TREE_NODE::at(position).toString(tmp) endi;debug_log new_position TREE_NODE::at(new_position).toString(tmp) endi;debug();return true;}这个代码不复杂就是累。
四、简单情形 现在要删除的节点要么没有子树要么只有一个子树说起来是子树其实最多就是一个红节点否则必定违反红黑树规则只需要把子树接上去就可以了然后把要删除的节点扔掉。 这里我们还是用一般二叉树的概念来理解以下说的节点都是数据节点不包括空节点。 如果删除节点是红节点不管下面有没有子树不用平衡因为不影响规则。 如果删除节点是黑节点而下面有一个红节点前面已经说了没有更多可能性把这个红节点变成黑节点就行了。 如果删除节点是黑节点而下面没有可供变色的红节点也就是没有子节点红黑树规则不允许下面有黑色数据节点因为只有一个子树另外一边深度是0这就导致红黑树规则被破坏很多文章称这种情况为“双黑”其实就是黑节点少了。 第三种情形就被称为“复杂情形”需要调用_RB_erase_Balance()来平衡。
五、复杂情形 前面已经说了所谓复杂情形就是少了一个黑节点现在涉及到这么几个节点 u 替换节点也就是出问题的节点这个节点的高度比兄弟少一。这个节点可能是是空节点。 p 替换节点的父节点 s 替换节点的兄弟节点 由于红黑树的规则限制最初进入这种情形只可能是被删除节点下没有子节点所以一定是p的一边为空另一边黑高为1。递归之后黑高少一的节点就有了各种可能可能是红色或黑色可能有或没有子节点。 重新平衡有三种策略
如果能把p改成黑同时让s黑高减一这样就恢复平衡了这要求p为红p为红则s必为黑如果s的子节点均为黑此时s的子节点必定都是空节点否则违反红黑树规则只需要将p和s颜色交换就可以了。另一边如果有红色节点能挪过来改成黑色平衡就完成了。按照红色节点的位置不同需要有不同的挪法虽然繁琐但并不困难。另一边如果有红色节点挪过来也不能平衡想办法把问题往上移递归处理。
psss处理1黑黑黑黑/不存在p、s交换颜色问题上移递归2黑黑红红挪一个红改成黑3黑红黑黑-[红红红红]旋转pp、s交换颜色p还是少1但是变色了重新处理p递归4红黑红红挪一个红改成黑5红黑黑黑/不存在p、s交换颜色 上表是所有情形“不存在”指的是空节点也是黑色。ss指的是s的子节点。“红红”也可能是只有一个红因为处理时只要有一个红就不用管另一个。第三种情形的ss是双黑后面还可能有红色子节点不过与算法无关。 为什么只有五种组合而不是八种因为不允许连续红另外三种不可能存在。 上面第二种和第四种处理方式相同因为并不关心p的颜色通过挪一个改成黑下面就平衡了。 代码的实际处理逻辑是从ss开始判断的先分成ss至少有一个红和没有红然后没有红的分三种有红的分四种所谓四种不过是四种结构的挪法而已。 代码如下 //删除时做平衡u可能是空节点bool _RB_erase_Balance(T_SHM_SIZE p, T_SHM_SIZE u){if (-1 p){debug_log 已经到顶结束 endi;return true;}string tmp;debug_log p TREE_NODE::at(p).toString(tmp) endi;if (u ! -1)debug_log u TREE_NODE::at(u).toString(tmp) endi;else debug_log u -1 endi;bool isL (u TREE_NODE::at(p).hRight);//兄弟节点是否是左节点T_SHM_SIZE s (isL ? TREE_NODE::at(p).hLeft : TREE_NODE::at(p).hRight);T_SHM_SIZE r -1;//s的红色子节点bool is_rL;//s的红色子节点是否是左节点debug_log 平衡p p u u s s TREE_NODE::at(s).hRight TREE_NODE::at(s).hRight endi;if (TREE_NODE::at(s).hRight ! -1 TREE_NODE::at(TREE_NODE::at(s).hRight).bColorRed){r TREE_NODE::at(s).hRight;is_rL false;}else if (TREE_NODE::at(s).hLeft ! -1 TREE_NODE::at(TREE_NODE::at(s).hLeft).bColorRed){r TREE_NODE::at(s).hLeft;is_rL true;}else{r -1;is_rL false;//无意义}debug_log p p u u s s r-1表示双黑 r endi;debug();if (-1 r){debug_log s子节点均为黑 endi;if (TREE_NODE::at(p).bColorRed){debug_log p为红s必为黑 s改为红p改为黑 结束 endi;//s子节点均为黑p改为黑所以s改为红是安全的不会造成双红TREE_NODE::at(s).bColorRed true;TREE_NODE::at(p).bColorRed false;debug();}else{debug_log p为黑 endi;if (!TREE_NODE::at(s).bColorRed){debug_log s为黑 s改为红平衡下层并向上递归 endi;//p的左右分支均少1所以p成为新的双黑节点//置s为红p为新的u递归TREE_NODE::at(s).bColorRed true;debug();return _RB_erase_Balance(TREE_NODE::at(p).hParent, p);}else{debug_log s为红 TREE_NODE::at(s).toString(tmp) endi;debug_log TREE_NODE::at(TREE_NODE::at(s).hParent).toString(tmp) endi;if (TREE_NODE::at(s).isLeft()){debug_log s为左 s endi;//右旋p_RRotate(p);}else{debug_log s为右 endi;_LRotate(p);}//p和s变色TREE_NODE::at(s).bColorRed false;TREE_NODE::at(p).bColorRed true;debug();//此时深度情况不变但p变成了红重新对p和u做平衡处理return _RB_erase_Balance(p, u);}}}else{if (isL is_rL){debug_log LL ende;TREE_NODE::at(r).bColorRed TREE_NODE::at(s).bColorRed;TREE_NODE::at(s).bColorRed TREE_NODE::at(p).bColorRed;_RRotate(p);TREE_NODE::at(p).bColorRed false;}else if (isL !is_rL){debug_log LR endi;debug();TREE_NODE::at(r).bColorRed TREE_NODE::at(p).bColorRed;debug();_LRotate(s);debug();_RRotate(p);debug();TREE_NODE::at(p).bColorRed false;debug();}else if (!isL is_rL){debug_log RL------------------------ endi;debug();TREE_NODE::at(r).bColorRed TREE_NODE::at(p).bColorRed;debug();_RRotate(s);debug();string tmp;debug_log p TREE_NODE::at(p).toString(tmp) endi;debug_log s TREE_NODE::at(p).toString(tmp) endi;_LRotate(p);debug();TREE_NODE::at(p).bColorRed false;debug();}else if (!isL !is_rL){debug_log RR endi;TREE_NODE::at(r).bColorRed TREE_NODE::at(s).bColorRed;TREE_NODE::at(s).bColorRed TREE_NODE::at(p).bColorRed;_LRotate(p);TREE_NODE::at(p).bColorRed false;}else{thelog 非预期的状态 ende;return false;}}return true;}我感觉吧我应该刚好解决了一部分人的困惑。 这里是结束而且是整个系列的结束
