知识卡片

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

并查集森林以树根代表集合

理解等级:中级

并查集森林用一棵有根树表示一个集合;每个元素只存父指针,根节点是代表元且父指针指向自己。

  • MAKE-SET 建单节点树,
  • FIND-SET 沿父链找根,
  • UNION 连接两棵树的根。
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      A faster implementation of disjoint sets represents sets by rooted trees, with each node containing one member and each tree representing one set. In a disjoint-set forest, illustrated in Figure 19.4(a), each member points only to its parent. The root of each tree contains the representative and is its own parent.

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[10000,20000))。 - 结论依据:原文定义树表示、根代表元和三种操作在森林中的基本动作。 - 原始内容:A faster implementation of disjoint sets represents sets by rooted trees, with each node containing one member and each tree representing one set. In a disjoint-set forest , illustrated in Figure 19.4(a) , each member points only to its parent. The root of each tree contains the representative and is its own parent.