知识卡片

普通读书笔记卡 · 1292.f.1.a.5.d

新节点标红保留黑高

理解等级:高级

红黑树先按普通搜索树位置插入,再把新节点设红。它替代原黑色 NIL 时不改变已有路径的黑节点数,故主要待修复的是红根或红父子相邻;直接套普通 BST 插入虽快,却不能保证更新后的树合法。

这张卡片看不懂?

已有反馈 · 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.