知识卡片

普通读书笔记卡 · 3634.a.6.b.1

递归查集回程更新父指针

理解等级:中级
  1. 递归 FIND-SET 先沿父指针上行找到根,
  2. 递归返回时再把路径上每个节点的父指针改为该根;

根的父指针是自己,构成递归终点。单次调用同时完成代表元查询和路径压缩。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[15000,20000))。 - 结论依据:原文明确递归上行查根、回程更新路径指针的两遍过程。 - 原始内容:The F IND -S ET procedure is a two-pass method : as it recurses, it makes one pass up the find path to find the root, and as the recursion unwinds, it makes a second pass back down the find path to update each node to point directly to the root.