知识卡片

普通读书笔记卡 · 3640.a.1

重复键的秩按中序位置区分

理解等级:中级

顺序统计树允许重复键,此时仅凭键值无法唯一确定秩。

把秩定义为具体节点在中序遍历中的输出位置,可让两个键相同的节点仍各有确定位置;查询接口必须区分节点和键。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第17章 数据结构的扩张 · 查看原书依据

      Keys need not be distinct in an order-statistic tree. For example, the tree in Figure 17.1 has two keys with value 14 and two keys with value 21. When equal keys are present, the above notion of rank is not well defined. We remove this ambiguity for an order-statistic tree by defining the rank of an element as the position at which it would be printed in an inorder walk of the tree.

    参考来源

    - 位置:《算法导论(第4版)》第17章《数据结构的扩张》(OEBPS/chapter017.xhtml,文本字符[0,5000))。 - 结论依据:原文明确允许重复键,并用节点在中序遍历中的输出位置消除同键秩的歧义。 - 原始内容:Keys need not be distinct in an order-statistic tree. For example, the tree in Figure 17.1 has two keys with value 14 and two keys with value 21. When equal keys are present, the above notion of rank is not well defined. We remove this ambiguity for an order-statistic tree by defining the rank of an element as the position at which it would be printed in an inorder walk of the tree.