知识卡片

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

链表并查集把查找做成常数

理解等级:中级

链表表示中,每个集合有头尾指针;元素节点保存所属集合对象的回指针,首节点成员为代表元。

MAKE-SET和FIND-SET都能 O(1),但合并时必须更新被接入链表中每个元素的回指针。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Each object in the list contains a set member, a pointer to the next object in the list, and a pointer back to the set object. Within each linked list, the objects may appear in any order. The representative is the set member in the first object in the list. With this linked-list representation, both MAKE-SET and FIND-SET require only O(1) time.

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[5000,10000))。 - 结论依据:原文描述集合对象、元素回指针和首节点代表元的布局。 - 原始内容:Each object in the list contains a set member, a pointer to the next object in the list, and a pointer back to the set object. Within each linked list, the objects may appear in any order. The representative is the set member in the first object in the list. With this linked-list representation, both M AKE -S ET and F IND -S ET require only O (1) time.