algorithm - 红黑树删除未知行为
问题描述
我在红黑树上输入了几个数字。(41; 38; 31; 12; 19; 8) 删除 8 和 12 (第一个截图) 后进入第二个截图的类型。我不明白为什么 31 变成红色。请帮帮我?如果您可以请提及与此相关的案例。谢谢 !
解决方案
如果您查看Wikipedia上对删除算法的说明,您可以将它们的节点命名映射到您的树,如下所示:
M = 0012,要移除的黑色节点
C = 0012 以下的 NIL 叶(NIL 总是被认为是黑色的)
文章接着说你的实际情况:
复杂的情况是M和C都是黑色的。[...] 我们首先将M替换为其子C。[...] 我们将重新标记这个孩子C(在它的新位置)N,以及它的兄弟姐妹(它的新父母的另一个孩子)S [...] 我们还将使用P表示N的新父母,S L表示S的左孩子,S R代表S的右孩子
所以现在我们在移除之后,但在重新着色之前:
P = 0019(红色)
N = NIL 叶子,0019 的左孩子
S = 0031,0019 的右孩子
该描述确定了几种情况,手头的情况如下:
情况 4:S和S的孩子是黑色的,但P是红色的。在这种情况下,我们只需交换S和P的颜色。
这种颜色交换的原因解释如下:
这不会影响经过S的路径上黑色节点的数量,但它确实会在经过N的路径上的黑色节点数量上加一,从而弥补这些路径上已删除的黑色节点。
回想一下,在红黑树中,这个不变量必须保持(属性 5):
从给定节点到其任何后代 NIL 节点的每条路径都包含相同数量的黑色节点。
如果省略上述颜色交换,则将违反此不变量。
推荐阅读
- r - 定位存储 R 代码的目录
- mysql - 如何访问显示错误“mysql 服务器消失”的网站?
- java - 如何修复“在 DownloadManager 中调用新静态方法时出现 NoSuchMethodError”
- deep-learning - 混淆矩阵的准确度与验证准确度之间的差异
- javascript - JavaScript:如何根据字段在数组中添加和排序相同的字段?
- ios - 尝试在已经呈现 SecondViewController 的 ViewController 上呈现 GADNFullScreenAdViewController
- asp.net-mvc - 在 Visual Studio 2015 中创建项目只显示一个网页
- android - 如何使用WIFI在真实设备上调试应用程序而根本无法使用电缆
- elasticsearch - Json Array 拆分问题 Logstash 配置:意外的输入结束:Array 的预期关闭标记(在 [Source: (S
- php - 如何将gridview行显示到特定视图?