原书出处
Introduction to Algorithms, Fourth Edition
17 第17章 数据结构的扩张
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