知识卡片
顺序统计树保存子树大小
顺序统计树在红黑树每个节点记录其子树的实际节点数,哨兵大小为0,节点大小等于左右子树大小之和再加1。它用这一局部汇总支持动态集合的第i小元素与秩查询。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第17章 数据结构的扩张 · 查看原书依据
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.
参考来源
- 位置:《算法导论(第4版)》第17章《数据结构的扩张》(OEBPS/chapter017.xhtml,文本字符[0,5000))。
- 结论依据:原文定义size为以节点为根的内部节点数,哨兵size=0,并直接给出左右子树大小加1的恒等式。
- 原始内容: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.