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