知识卡片
删除至多三次旋转
删除修复只有兄弟与其两孩子皆黑的分支会重复,且每次把指针向根推进;其余分支经常数次重着色和最多三次旋转结束。因此删除总耗时 O(log n),旋转次数有常数上界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 删除至多三次旋转
原书出处 · 1 处
- 第13章 红黑树 · 查看原书依据
Thus, the procedure RB-DELETE-FIXUP takes O(lg n) time and performs at most three rotations, and the overall time for RB-DELETE is therefore also O(lg n).
参考来源
- 位置:《算法导论(第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 ).