知识卡片
递归查集回程更新父指针
- 递归 FIND-SET 先沿父指针上行找到根,
- 递归返回时再把路径上每个节点的父指针改为该根;
根的父指针是自己,构成递归终点。单次调用同时完成代表元查询和路径压缩。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
The FIND-SET 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.
参考来源
- 位置:《算法导论(第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.