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

            本文承接自：

            算法实战：亲自写红黑树之一-CSDN博客

            算法实战：亲自写红黑树之二 完整代码-CSDN博客

            算法实战：亲自写红黑树之三 算法详解-CSDN博客

            算法实战：亲自写红黑树之四 插入insert的平衡-CSDN博客

    目录

    一、入口

    二、删除

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

    四、简单情形

    五、复杂情形

    一、入口

            有几个不同参数的删除入口：

    1. 	bool erase(const_iterator it)
    2. 	{
    3. 		T_COMP comp;
    4. 		return erase(it, comp);
    5. 	}
    6. 	//删除并指向下一个
    7. 	iterator& DeleteAndMoveNext(iterator& it)
    8. 	{
    9. 		if (end() == it)return it;
    10.  
    11. 		iterator& ret = it;
    12. 		iterator tmp = ret;
    13. 		++ret;
    14. 		erase(tmp);
    15. 		return ret;
    16. 	}
    17. 	bool erase(const_iterator it, T_COMP& comp)
    18. 	{
    19. 		if (it.handle < 0)return true;
    20. 		//DEBUG_LOG<<"要删除节点"<
    21. 		bool ret = _erase(it.handle);
    22.  
    23. 		return ret;
    24. 	}
    25. 	bool erase(T_DATA const& data)
    26. 	{
    27. 		T_COMP comp;
    28. 		return erase(data, comp);
    29. 	}
    30. 	bool erase(T_DATA const& data, T_COMP& comp)
    31. 	{
    32. 		const_iterator it = find(data, comp);
    33. 		if (it.handle < 0)return true;
    34. 		return erase(it, comp);
    35. 	}

            最终都进入_erase(h)，直接删除一个节点。

            在到达这一步之前要先找到要删除的节点，这个属于二叉树的标准算法，很简单。

    二、删除

            删除的控制代码：

    1. 	//删除
    2. 	bool _erase(T_SHM_SIZE position)
    3. 	{
    4. 		string  report;
    5. 		//DEBUG_LOG<<"开始删除...."<
    6.  
    7. 		bool vLeft;//删除的节点是左子节点
    8. 		bool vRed;//删除的节点是红色
    9. 		T_SHM_SIZE p = TREE_NODE::at(position).hParent;//父节点
    10. 		T_SHM_SIZE u;//替换节点
    11. 		bool uRed;//替换节点是红色（-1为黑色）
    12.  
    13. 		if (TREE_NODE::at(position).hLeft != -1 && TREE_NODE::at(position).hRight != -1)
    14. 		{
    15. 			debug_log << "左右都存在，替换为左子树最大值" << endi;
    16. 			if (!__erase_change_middle(position, vLeft, vRed, u, uRed, p))return false;
    17. 			debug();
    18. 			return _erase(position);
    19. 		}
    20. 		else if (-1 == TREE_NODE::at(position).hLeft && -1 == TREE_NODE::at(position).hRight)
    21. 		{
    22. 			vLeft = TREE_NODE::at(position).isLeft();
    23. 			vRed = TREE_NODE::at(position).bColorRed;
    24. 			u = -1;
    25. 			uRed = false;
    26.  
    27. 			if (-1 == p)
    28. 			{
    29. 				debug_log << "最后一个节点" << endi;
    30. 				tree_head->hHead = -1;
    31. 				vRed = true;//阻止后面继续处理，删除红色无需额外处理
    32. 			}
    33. 			else
    34. 			{
    35. 				debug_log << "叶子节点" << endi;
    36. 				if (TREE_NODE::at(position).isLeft())TREE_NODE::at(p).hLeft = -1;
    37. 				else TREE_NODE::at(p).hRight = -1;
    38. 			}
    39. 		}
    40. 		else
    41. 		{
    42. 			vLeft = TREE_NODE::at(position).isLeft();
    43. 			vRed = TREE_NODE::at(position).bColorRed;
    44. 			if (-1 != TREE_NODE::at(position).hLeft)
    45. 			{
    46. 				debug_log << "左子树存在" << endi;
    47. 				u = TREE_NODE::at(position).hLeft;
    48. 			}
    49. 			else
    50. 			{
    51. 				debug_log << "右子树存在" << endi;
    52. 				u = TREE_NODE::at(position).hRight;
    53. 			}
    54. 			if (-1 == p)
    55. 			{
    56. 				debug_log << "根节点" << endi;
    57. 				tree_head->hHead = u;
    58. 			}
    59. 			else
    60. 			{
    61. 				if (vLeft)TREE_NODE::at(p).hLeft = u;
    62. 				else TREE_NODE::at(p).hRight = u;
    63. 			}
    64. 			TREE_NODE::at(u).hParent = p;
    65. 			uRed = TREE_NODE::at(u).bColorRed;
    66. 			p = TREE_NODE::at(u).hParent;
    67. 		}
    68.  
    69. 		bool ret = true;
    70. 		if (vRed)
    71. 		{
    72. 			debug_log << "删除红色节点，不用调整" << endi;
    73. 		}
    74. 		else if (!vRed && uRed)
    75. 		{
    76. 			debug_log << "删除黑色节点，替换节点红色改为黑色" << endi;
    77. 			TREE_NODE::at(u).bColorRed = false;
    78. 		}
    79. 		else
    80. 		{
    81. 			debug_log << "删除双黑节点================================================" << endi;
    82. 			ret = _RB_erase_Balance(p, u);
    83. 		}
    84.  
    85. 		debug();
    86. 		if (ret)__erase_node(position);
    87.  
    88. 		if (-1 != tree_head->hHead)TREE_NODE::at(tree_head->hHead).bColorRed = false;
    89.  
    90. 		return ret;
    91. 	}

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

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

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

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

            本代码用__erase_change_middle(h)函数做这件事，将颜色也做了交换（逻辑上相当于不改变结构数据，只交换用户数据，但是我们的用户数据一般都很大，所以反过来操作，改变了除用户数据以外的所有结构数据），执行完毕后红黑树结构仍然正确，删除节点变成了最多只有一个子树的节点。

    1. 	//删除中间节点，将中间节点替换为左子树最大值（数据不动，改变树结构）
    2. 	bool __erase_change_middle(T_SHM_SIZE const position, bool& vLeft, bool& vRed, T_SHM_SIZE& u, bool& uRed, T_SHM_SIZE& p)
    3. 	{
    4. 		string tmp;
    5. 		T_SHM_SIZE new_position = TREE_NODE::at(position).hLeft;
    6. 		if (-1 != new_position)
    7. 		{
    8. 			while (-1 != TREE_NODE::at(new_position).hRight)
    9. 			{
    10. 				new_position = TREE_NODE::at(new_position).hRight;
    11. 			}
    12. 		}
    13. 		debug_log << "position " << position << " new_position " << new_position << endi;
    14. 		debug_log << "position " << position << TREE_NODE::at(position).toString(tmp) << endi;
    15. 		debug_log << "new_position " << new_position << TREE_NODE::at(new_position).toString(tmp) << endi;
    16.  
    17. 		vLeft = false;
    18. 		vRed = TREE_NODE::at(new_position).bColorRed;
    19. 		p = TREE_NODE::at(new_position).hParent;
    20. 		debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    21. 		if (p != position)
    22. 		{
    23. 			debug_log << "非直接对调 p " << TREE_NODE::at(p).toString(tmp) << ende;
    24. 			TREE_NODE t;
    25. 			t._CopyWithoutData(TREE_NODE::at(new_position));
    26. 			TREE_NODE::at(new_position)._CopyWithoutData(TREE_NODE::at(position));
    27. 			TREE_NODE::at(position)._CopyWithoutData(t);
    28.  
    29. 			debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
    30. 			debug_log << "new_position " << TREE_NODE::at(new_position).toString(tmp) << endi;
    31.  
    32. 			//注意，这里无法用isLeft来判断，因为父节点的hLeft和hRight是旧数据
    33. 			if (TREE_NODE::at(new_position).hParent != -1)
    34. 			{
    35. 				if (TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft == position)TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft = new_position;
    36. 				else TREE_NODE::at(TREE_NODE::at(new_position).hParent).hRight = new_position;
    37. 			}
    38. 			if (TREE_NODE::at(position).hParent != -1)
    39. 			{
    40. 				if (TREE_NODE::at(TREE_NODE::at(position).hParent).hLeft==new_position)TREE_NODE::at(TREE_NODE::at(position).hParent).hLeft = position;
    41. 				else TREE_NODE::at(TREE_NODE::at(position).hParent).hRight = position;
    42. 			}
    43. 			
    44. 			if (TREE_NODE::at(new_position).hLeft != -1)TREE_NODE::at(TREE_NODE::at(new_position).hLeft).hParent = new_position;
    45. 			if (TREE_NODE::at(position).hLeft != -1)TREE_NODE::at(TREE_NODE::at(position).hLeft).hParent = position;
    46.  
    47. 			if (TREE_NODE::at(new_position).hRight != -1)TREE_NODE::at(TREE_NODE::at(new_position).hRight).hParent = new_position;
    48. 			if (TREE_NODE::at(position).hRight != -1)TREE_NODE::at(TREE_NODE::at(position).hRight).hParent = position;
    49. 		}
    50. 		else
    51. 		{
    52. 			debug_log << "直接对调 p " << TREE_NODE::at(p).toString(tmp) << endi;
    53. 			TREE_NODE t;
    54. 			t._CopyWithoutData(TREE_NODE::at(new_position));
    55. 			TREE_NODE::at(new_position)._CopyWithoutData(TREE_NODE::at(position));
    56. 			TREE_NODE::at(position)._CopyWithoutData(t);
    57. 			debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
    58. 			debug_log << "new_position " << TREE_NODE::at(new_position).toString(tmp) << endi;
    59.  
    60. 			//注意，这里无法用isLeft来判断，因为父节点的hLeft和hRight是旧数据
    61. 			if (TREE_NODE::at(new_position).hParent != -1)
    62. 			{
    63. 				if (TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft == position)TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft = new_position;
    64. 				else TREE_NODE::at(TREE_NODE::at(new_position).hParent).hRight = new_position;
    65. 			}
    66. 			TREE_NODE::at(position).hParent = new_position;
    67.  
    68. 			TREE_NODE::at(new_position).hLeft=position;
    69. 			if (TREE_NODE::at(position).hLeft != -1)TREE_NODE::at(TREE_NODE::at(position).hLeft).hParent = position;
    70.  
    71. 			if (TREE_NODE::at(new_position).hRight != -1)TREE_NODE::at(TREE_NODE::at(new_position).hRight).hParent = new_position;
    72. 			if (TREE_NODE::at(position).hRight != -1)TREE_NODE::at(TREE_NODE::at(position).hRight).hParent = position;
    73. 		}
    74. 	
    75. 		//如果是根节点
    76. 		if (-1 == TREE_NODE::at(new_position).hParent)
    77. 		{
    78. 			TREE_NODE::at(new_position).bColorRed = false;
    79. 			tree_head->hHead = new_position;
    80. 		}
    81. 		debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
    82. 		debug_log << "new_position " << TREE_NODE::at(new_position).toString(tmp) << endi;
    83. 		debug();
    84.  
    85. 		return true;
    86. 	}

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

    四、简单情形

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

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

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

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

    五、复杂情形

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

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

            p 替换节点的父节点

            s 替换节点的兄弟节点

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

            重新平衡有三种策略：

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

            上表是所有情形，“不存在”指的是空节点，也是黑色。ss指的是s的子节点。“红红”也可能是只有一个红，因为处理时只要有一个红就不用管另一个。第三种情形的ss是双黑，后面还可能有红色子节点，不过与算法无关。

            为什么只有五种组合而不是八种？因为不允许连续红，另外三种不可能存在。

            上面第二种和第四种处理方式相同，因为并不关心p的颜色，通过挪一个改成黑，下面就平衡了。

            代码的实际处理逻辑是从ss开始判断的，先分成ss至少有一个红和没有红，然后没有红的分三种，有红的分四种（所谓四种不过是四种结构的挪法而已）。

            代码如下：

    1. 	//删除时做平衡，u可能是空节点
    2. 	bool _RB_erase_Balance(T_SHM_SIZE p, T_SHM_SIZE u)
    3. 	{
    4. 		if (-1 == p)
    5. 		{
    6. 			debug_log << "已经到顶，结束" << endi;
    7. 			return true;
    8. 		}
    9.  
    10. 		string tmp;
    11. 		debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    12. 		if (u != -1)debug_log << "u " << TREE_NODE::at(u).toString(tmp) << endi;
    13. 		else debug_log << "u -1" << endi;
    14.  
    15. 		bool isL = (u == TREE_NODE::at(p).hRight);//兄弟节点是否是左节点
    16. 		T_SHM_SIZE s = (isL ? TREE_NODE::at(p).hLeft : TREE_NODE::at(p).hRight);
    17. 		T_SHM_SIZE r = -1;//s的红色子节点
    18. 		bool is_rL;//s的红色子节点是否是左节点
    19. 		debug_log << "平衡：p " << p << " u " << u << " s " << s << " TREE_NODE::at(s).hRight " << TREE_NODE::at(s).hRight << endi;
    20. 		if (TREE_NODE::at(s).hRight != -1 && TREE_NODE::at(TREE_NODE::at(s).hRight).bColorRed)
    21. 		{
    22. 			r = TREE_NODE::at(s).hRight;
    23. 			is_rL = false;
    24. 		}
    25. 		else if (TREE_NODE::at(s).hLeft != -1 && TREE_NODE::at(TREE_NODE::at(s).hLeft).bColorRed)
    26. 		{
    27. 			r = TREE_NODE::at(s).hLeft;
    28. 			is_rL = true;
    29. 		}
    30. 		else
    31. 		{
    32. 			r = -1;
    33. 			is_rL = false;//无意义
    34. 		}
    35.  
    36. 		debug_log << "p " << p << " u " << u << " s " << s << " r（-1表示双黑） " << r << endi;
    37. 		debug();
    38. 		if (-1 == r)
    39. 		{
    40. 			debug_log << "s子节点均为黑" << endi;
    41. 			if (TREE_NODE::at(p).bColorRed)
    42. 			{
    43. 				debug_log << "p为红，s必为黑 s改为红p改为黑 结束" << endi;//s子节点均为黑，p改为黑，所以s改为红是安全的，不会造成双红
    44. 				TREE_NODE::at(s).bColorRed = true;
    45. 				TREE_NODE::at(p).bColorRed = false;
    46. 				debug();
    47. 			}
    48. 			else
    49. 			{
    50. 				debug_log << "p为黑" << endi;
    51. 				if (!TREE_NODE::at(s).bColorRed)
    52. 				{
    53. 					debug_log << "s为黑 s改为红平衡下层并向上递归" << endi;//p的左右分支均少1，所以p成为新的双黑节点
    54. 					//置s为红，p为新的u，递归
    55. 					TREE_NODE::at(s).bColorRed = true;
    56. 					debug();
    57. 					return _RB_erase_Balance(TREE_NODE::at(p).hParent, p);
    58. 				}
    59. 				else
    60. 				{
    61. 					debug_log << "s为红 " << TREE_NODE::at(s).toString(tmp) << endi;
    62. 					debug_log << TREE_NODE::at(TREE_NODE::at(s).hParent).toString(tmp) << endi;
    63. 					if (TREE_NODE::at(s).isLeft())
    64. 					{
    65. 						debug_log << "s为左 " << s << endi;
    66. 						//右旋p
    67. 						_RRotate(p);
    68. 					}
    69. 					else
    70. 					{
    71. 						debug_log << "s为右" << endi;
    72. 						_LRotate(p);
    73. 					}
    74. 					//p和s变色
    75. 					TREE_NODE::at(s).bColorRed = false;
    76. 					TREE_NODE::at(p).bColorRed = true;
    77. 					debug();
    78. 					//此时深度情况不变，但p变成了红，重新对p和u做平衡处理
    79. 					return _RB_erase_Balance(p, u);
    80. 				}
    81. 			}
    82. 		}
    83. 		else
    84. 		{
    85. 			if (isL && is_rL)
    86. 			{
    87. 				debug_log << "LL" << ende;
    88. 				TREE_NODE::at(r).bColorRed = TREE_NODE::at(s).bColorRed;
    89. 				TREE_NODE::at(s).bColorRed = TREE_NODE::at(p).bColorRed;
    90. 				_RRotate(p);
    91. 				TREE_NODE::at(p).bColorRed = false;
    92. 			}
    93. 			else if (isL && !is_rL)
    94. 			{
    95. 				debug_log << "LR" << endi;
    96.  
    97. 				debug();
    98.  
    99. 				TREE_NODE::at(r).bColorRed = TREE_NODE::at(p).bColorRed;
    100. 				debug();
    101. 				_LRotate(s);
    102. 				debug();
    103. 				_RRotate(p);
    104. 				debug();
    105. 				TREE_NODE::at(p).bColorRed = false;
    106.  
    107. 				debug();
    108. 			}
    109. 			else if (!isL && is_rL)
    110. 			{
    111. 				debug_log << "RL------------------------" << endi;
    112. 				debug();
    113. 				TREE_NODE::at(r).bColorRed = TREE_NODE::at(p).bColorRed;
    114. 				debug();
    115. 				_RRotate(s);
    116. 				debug();
    117. 				string tmp;
    118. 				debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    119. 				debug_log << "s " << TREE_NODE::at(p).toString(tmp) << endi;
    120. 				_LRotate(p);
    121. 				debug();
    122. 				TREE_NODE::at(p).bColorRed = false;
    123. 				debug();
    124. 			}
    125. 			else if (!isL && !is_rL)
    126. 			{
    127. 				debug_log << "RR" << endi;
    128. 				TREE_NODE::at(r).bColorRed = TREE_NODE::at(s).bColorRed;
    129. 				TREE_NODE::at(s).bColorRed = TREE_NODE::at(p).bColorRed;
    130. 				_LRotate(p);
    131. 				TREE_NODE::at(p).bColorRed = false;
    132. 			}
    133. 			else
    134. 			{
    135. 				thelog << "非预期的状态" << ende;
    136. 				return false;
    137. 			}
    138. 		}
    139.  
    140. 		return true;
    141. 	}

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

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

  • 相关阅读:
    Dockerfile指令与Docker-compose容器编排-搭建docker私有仓库
    【博客550】k8s乐观锁机制：控制并发请求与数据一致性
    uniapp - 微信小程序新版本发布之后用户端如何手动更新
    QBC CriteriaQuery用法
    2023-10-03 LeetCode每日一题（买卖股票的最佳时机 III）
    jQuery中的Ajax
    【环境配置】基于Docker配置Chisel-Bootcamp环境
    (const char *format, ...) 可变参数在文本日志中的巧妙使用
    zookeeper无法连接，导致elasticjob控制台无法使用
    深度之眼（二）——矩阵及其基本运算
  • 原文地址：https://blog.csdn.net/2301_77171572/article/details/134435927