知识卡片

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

删除至多三次旋转

理解等级:高级

删除修复只有兄弟与其两孩子皆黑的分支会重复,且每次把指针向根推进;其余分支经常数次重着色和最多三次旋转结束。因此删除总耗时 O(log n),旋转次数有常数上界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 13 章13.4 节(`OEBPS/chapter013.xhtml`,文本字符 [40000, 45000))。 - 结论依据:13.4 节运行时间分析明确只有情况 2 会重复,且 x 向根上移、不旋转;情况 1、3、4 在常数次着色与合计最多三次旋转后结束。 - 原始内容:Thus, the procedure RB-D ELETE -F IXUP takes O (lg n ) time and performs at most three rotations, and the overall time for RB-D ELETE is therefore also O (lg n ).