← 返回起始笔记位置

知识卡片

普通读书笔记卡 · 3640.b.1

增强定理要求局部可算

理解等级:高级

若红黑树节点的附加属性只依赖本节点和两个孩子,且能在常数时间求出,插入、删除仍可保持对数时间。

关键是变更只向祖先传播,而红黑树高度及一次更新的旋转次数都有界。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第17章 数据结构的扩张 · 查看原书依据

      suppose that the value of f for each node x depends only the information in nodes x, x.left, and x.right (possibly including x.left.f and x.right.f), and that the value of x.f can be computed from this information in O(1) time. Then, the insertion and deletion operations can maintain the values of f in all nodes of T without asymptotically affecting the O(lg n) running times of these operations.

    参考来源

    - 位置:《算法导论(第4版)》第17章《数据结构的扩张》(OEBPS/chapter017.xhtml,文本字符[15000,20000))。 - 结论依据:定理把局部依赖和常数时间计算列为条件,证明用树高与有限旋转控制维护成本。 - 原始内容:suppose that the value of f for each node x depends only the information in nodes x , x . left , and x . right (possibly including x . left . f and x . right . f ), and that the value of x . f can be computed from this information in O (1) time. Then, the insertion and deletion operations can maintain the values of f in all nodes of T without asymptotically affecting the O (lg n ) running times of these operations.