知识卡片
旋转只需局部修补大小
红黑树旋转虽改变父子关系,但顺序统计树中仅旋转轴两端节点的子树大小失效,其余子树大小不变。
插删路径上的大小可线性于树高更新,旋转后常数次局部修补,因此更新仍为O(lg n)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第17章 数据结构的扩张 · 查看原书依据
Moreover, a rotation is a local operation: only two nodes have their size attributes invalidated. The link around which the rotation is performed is incident on these two nodes. Referring to the code for LEFT-ROTATE(T, x) on page 336, add the following lines: 13 y.size = x.size 14 x.size = x.left.size + x.right.size + 1
参考来源
- 位置:《算法导论(第4版)》第17章《数据结构的扩张》(OEBPS/chapter017.xhtml,文本字符[10000,15000))。
- 结论依据:原文说明旋转仅使两个节点的size失效,给出局部更新式;插删的路径更新和常数次旋转保持O(lg n)总界。
- 原始内容:Moreover, a rotation is a local operation: only two nodes have their size attributes invalidated. The link around which the rotation is performed is incident on these two nodes. Referring to the code for L EFT -R OTATE ( T , x ) on page 336, add the following lines: 13 y . size = x . size 14 x . size = x . left . size + x . right . size + 1