← 返回起始笔记位置

知识卡片

普通读书笔记卡 · 3640.a.4

旋转只需局部修补大小

理解等级:中级

红黑树旋转虽改变父子关系,但顺序统计树中仅旋转轴两端节点的子树大小失效,其余子树大小不变。

插删路径上的大小可线性于树高更新,旋转后常数次局部修补,因此更新仍为O(lg n)。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

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