知识卡片

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

黑高不计当前节点

理解等级:中级

节点黑高 bh(x) 是从 x 出发、但不计 x 本身到叶路径上的黑节点数。由于每条下降路径黑数相同,它才是定义良好的量;分析红黑树高度时要先说清是否计入起点和 NIL 叶。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 13 章13.1 节(`OEBPS/chapter013.xhtml`,文本字符 [0, 5000))。 - 结论依据:13.1 节将 bh(x) 定义为从 x 出发但不含 x 的任一下行路径上的黑节点数;性质 5 使不同后代叶路径的计数一致。 - 原始内容:We call the number of black nodes on any simple path from, but not including, a node x down to a leaf the black-height of the node