知识卡片
新节点标红保留黑高
红黑树先按普通搜索树位置插入,再把新节点设红。它替代原黑色 NIL 时不改变已有路径的黑节点数,故主要待修复的是红根或红父子相邻;直接套普通 BST 插入虽快,却不能保证更新后的树合法。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第13章 红黑树 · 查看原书依据
Property 5, which says that the number of black nodes is the same on every simple path from a given node, is satisfied as well, because node z replaces the (black) sentinel, and node z is red with sentinel children.
参考来源
- 位置:《算法导论(第4版)》第 13 章13.3 节(`OEBPS/chapter013.xhtml`,文本字符 [10000, 20000))。
- 结论依据:13.3 节 RB-INSERT 将新节点 z 着红且两个孩子为黑色 T.nil;它替代原黑 NIL 后路径黑数不变,原文指出只可能破坏根黑或红节点孩子黑两条性质。
- 原始内容:Property 5, which says that the number of black nodes is the same on every simple path from a given node, is satisfied as well, because node z replaces the (black) sentinel, and node z is red with sentinel children.