← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

17 第17章 数据结构的扩张

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

tistic tree T is simply a red-black tree with additional information stored in each node.

Each node x contains the usual red-black tree attributes x.key, x.color, x.p, x.left, and x.right, along with a new attribute, x.size. This attribute contains the number of internal nodes in the subtree rooted at x (including x itself, but not including any sentinels), that is, the size of the subtree. If we define the sentinel’s size to be 0—that is, we set T.nil.size to be 0—then we have the identity x.size = x.left.size + x.right.size + 1.

Keys need not be distinct in an order-statistic tree. For example, the tree in Figure 17.

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

原书定位详情

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

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

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea