算法实战：亲自写红黑树之五 删除erase的平衡

        本文承接自：

        算法实战：亲自写红黑树之一-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;}

        这个函数的逻辑分为两部分：

1. 分析要删除的节点的分支情况，将左右节点都存在的情形改为删除叶子数据节点（不是红黑树意义的叶子节点，指一般意义的叶子节点），然后确定删除节点和替换节点。
2. 根据删除节点和替换节点的颜色进行处理，黑节点减少则需要平衡。

三、转换中间节点（左右子树都存在）

        很容易把中间节点替换掉，跟左子树最大值或者右子树最小值交换即可。

        本代码用__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).hLeft==new_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).hLeft=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;}//如果是根节点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;}

        这个代码不复杂，就是累。

四、简单情形

        现在要删除的节点要么没有子树，要么只有一个子树（说起来是子树，其实最多就是一个红节点，否则必定违反红黑树规则），只需要把子树接上去就可以了，然后把要删除的节点扔掉。

        这里我们还是用一般二叉树的概念来理解，以下说的节点都是数据节点，不包括空节点。

1.         如果删除节点是红节点，不管下面有没有子树，不用平衡，因为不影响规则。
2.         如果删除节点是黑节点而下面有一个红节点（前面已经说了，没有更多可能性），把这个红节点变成黑节点就行了。
3.         如果删除节点是黑节点而下面没有可供变色的红节点（也就是没有子节点，红黑树规则不允许下面有黑色数据节点，因为只有一个子树，另外一边深度是0），这就导致红黑树规则被破坏，很多文章称这种情况为“双黑”，其实就是黑节点少了。

        第三种情形就被称为“复杂情形”，需要调用_RB_erase_Balance()来平衡。

五、复杂情形

        前面已经说了，所谓复杂情形就是少了一个黑节点，现在涉及到这么几个节点：

        u 替换节点，也就是出问题的节点，这个节点的高度比兄弟少一。这个节点可能是是空节点。

        p 替换节点的父节点

        s 替换节点的兄弟节点

        由于红黑树的规则限制，最初进入这种情形只可能是被删除节点下没有子节点，所以一定是p的一边为空另一边黑高为1。递归之后黑高少一的节点就有了各种可能，可能是红色或黑色，可能有或没有子节点。

        重新平衡有三种策略：

1. 如果能把p改成黑同时让s黑高减一，这样就恢复平衡了，这要求p为红，p为红则s必为黑，如果s的子节点均为黑（此时s的子节点必定都是空节点，否则违反红黑树规则），只需要将p和s颜色交换就可以了。
2. 另一边如果有红色节点，能挪过来改成黑色，平衡就完成了。按照红色节点的位置不同，需要有不同的挪法，虽然繁琐但并不困难。
3. 另一边如果有红色节点，挪过来也不能平衡，想办法把问题往上移，递归处理。

	p	s	ss	处理
1	黑	黑	黑黑/不存在	p、s交换颜色，问题上移，递归
2	黑	黑	红红	挪一个红改成黑
3	黑	红	黑黑-[红红红红]	旋转p，p、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;}

        我感觉吧，我应该刚好解决了一部分人的困惑。

（这里是结束，而且是整个系列的结束）