知识卡片
红黑树高度有对数上界
红节点不能连续,使任一路径至少约一半节点为黑;黑高为 b 的子树至少有 2^b−1 个内部节点。
两者合起来得到 h≤2lg(n+1),所以基本集合操作最坏 O(log n)。
这个保证依赖颜色约束在每次更新后仍成立。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第13章 红黑树 · 查看原书依据
A red-black tree with n internal nodes has height at most 2 lg(n + 1).
参考来源
- 位置:《算法导论(第4版)》第 13 章13.1 节与引理 13.1(`OEBPS/chapter013.xhtml`,文本字符 [0, 10000))。
- 结论依据:引理 13.1 先归纳证黑高 b 的子树至少有 2^b−1 个内部节点;红节点孩子皆黑使高度最多为根黑高的两倍,推出 h≤2lg(n+1)。
- 原始内容:A red-black tree with n internal nodes has height at most 2 lg( n + 1).