知识卡片

普通读书笔记卡 · 3643.a

离线祖先查询借并查集遍历

理解等级:中级

离线 LCA 过程按树递归:

  1. 进入节点时建集并记当前祖先,
  2. 处理每个孩子后合并集合、把合并后代表元的 ancestor 重新指向当前节点;
  3. 节点完成标黑后,对已标黑的查询端点读取其集合 ancestor。

原文留下正确性证明任务。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第19章 不相交集合的数据结构 · 查看原书依据

      LCA(u) 1 MAKE-SET(u) 2 FIND-SET(u).ancestor = u 3 for each child v of u in T 4 LCA(v) 5 UNION(u, v) 6 FIND-SET(u).ancestor = u 7 u.color = BLACK 8 for each node v such that {u, v} ∈ P 9 if v.color == BLACK 10 print “The lowest common ancestor of” u “and” v “is” FIND-SET(v).ancestor

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[45000,47985))。 - 结论依据:章末LCA伪代码给出建集、孩子递归、合并、ancestor更新与已完成端点查询。 - 原始内容:LCA( u ) 1 M AKE -S ET ( u ) 2 F IND -S ET ( u ). ancestor = u 3 for each child v of u in T 4 LCA( v ) 5 U NION ( u , v ) 6 F IND -S ET ( u ). ancestor = u 7 u . color = BLACK 8 for each node v such that { u , v } ∈ P 9 if v . color == BLACK 10 print “The lowest common ancestor of” u “and” v “is” F IND -S ET ( v ). ancestor