← 返回起始笔记位置

知识卡片

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

求节点秩沿祖先上溯

理解等级:中级

求某节点的全树秩时,

  1. 先计入其左子树和自身,
  2. 再逐层上溯。

若当前子树是父节点右孩子,还须加上父节点及其左子树大小;若是左孩子则无需增加。到根后得到中序位置,耗时受树高限制。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第17章《数据结构的扩张》(OEBPS/chapter017.xhtml,文本字符[5000,10000))。 - 结论依据:原文OS-RANK伪代码先取左子树size+1,再沿父指针上溯,仅当当前节点是右孩子时累加父节点左子树size+1。 - 原始内容:OS-R ANK ( T , x ) 1 r = x . left . size + 1 // rank of x within the subtree rooted at x 2 y = x // root of subtree being examined 3 while y ≠ T . root 4 if y == y . p . right // if root of a right subtree … 5 r = r + y . p . left . size + 1 // … add in parent and its left subtree 6 y = y . p // move y toward the root 7 return r