知识卡片

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

按左子树大小定位第i小

理解等级:中级

在某节点处,左子树大小加1就是该节点在本子树的局部秩。

  • 目标秩相等便返回该节点,
  • 较小则入左树,
  • 较大则减去该局部秩后入右树。

红黑树高度为O(lg n),所以选择查询同阶。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Thus, x.left.size + 1 is the rank of x within the subtree rooted at x. If i = r, then node x is the ith smallest element, and so line 3 returns x. If i < r, then the ith smallest element resides in x’s left subtree, and therefore, line 5 recurses on x.left. If i > r, then the ith smallest element resides in x’s right subtree. Since the subtree rooted at x contains r elements that come before x’s right subtree in an inorder tree walk, the ith smallest element in the subtree rooted at x is the (i − r)th smallest element in the subtree rooted at x.right. Line 6 determines this element recursively.

    参考来源

    - 位置:《算法导论(第4版)》第17章《数据结构的扩张》(OEBPS/chapter017.xhtml,文本字符[0,5000))。 - 结论依据:原文给出r=左子树size+1及i与r比较后的左右分支;红黑树高度界保证查询为O(lg n)。 - 原始内容:Thus, x . left . size + 1 is the rank of x within the subtree rooted at x . If i = r , then node x is the i th smallest element, and so line 3 returns x . If i < r , then the i th smallest element resides in x ’s left subtree, and therefore, line 5 recurses on x . left . If i > r , then the i th smallest element resides in x ’s right subtree. Since the subtree rooted at x contains r elements that come before x ’s right subtree in an inorder tree walk, the i th smallest element in the subtree rooted at x is the ( i − r )th smallest element in the subtree rooted at x . right . Line 6 determines this element recursively.