← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

17 第17章 数据结构的扩张

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.706Z

a red-black tree) Let f be an attribute that augments a red-black tree T of n nodes, and

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.

Proof The main idea of the proof is that a change to an f attribute in a node x propagate

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter017.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea