知识卡片
黑高不计当前节点
节点黑高 bh(x) 是从 x 出发、但不计 x 本身到叶路径上的黑节点数。由于每条下降路径黑数相同,它才是定义良好的量;分析红黑树高度时要先说清是否计入起点和 NIL 叶。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 黑高不计当前节点
原书出处 · 1 处
- 第13章 红黑树 · 查看原书依据
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
参考来源
- 位置:《算法导论(第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