知识卡片

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

红黑树高度有对数上界

理解等级:高级

红节点不能连续,使任一路径至少约一半节点为黑;黑高为 b 的子树至少有 2^b−1 个内部节点。

两者合起来得到 h≤2lg(n+1),所以基本集合操作最坏 O(log n)。

这个保证依赖颜色约束在每次更新后仍成立。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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).