联盟/查找算法，而不互助社职级不相交集森林数据结构 [英] Union/find algorithm without union by rank for disjoint-set forests data structure

问题描述

下面是该职工会崩溃/查找算法对不相交集森林维基百科：

Here's a breakdown on the union/find algorithm for disjoint set forests on wikipedia:

• 准系统不相交集森林......（ O（N））
  • ...与排名联盟...（现在提高到 O（日志（N））
    • ...与路径COM pression（现在提高到 0（A（N）），有效地 O（1））
    • Barebone disjoint-set forests... (O(n))
      • ... with union by rank ... (now improved to O(log(n))
        • ... with path compression (now improved to O(a(n)), effectively O(1))

        按等级执行欧盟的必要条件是每个节点保持一个排名字段进行比较。我的问题是，工会是按职级值这个额外的空间？如果我跳过工会按职级，只是做路径COM pression，而不是会发生什么？是不是不够好？什么是摊销的复杂性了吧？

        Implementing union by rank necessitates that each node keeps a rank field for comparison purposes. My question is, is union by rank worth this additional space? What happens if I skip union by rank and just do path compression instead? Is it good enough? What is the amortized complexity now?

        一个注释提出，意味着该联盟由职级不带路径COM pression（摊销 O（日志（N）复杂性）足以满足大多数实际应用。这是正确的什么我问的是周围的其他方法：？如果你跳过工会按职级和只做路径COM pression而不是

        A comment is made that implies that union by rank without path compression (amortized O(log(n) complexity) is sufficient for most practical application. This is correct. What I'm asking is the other way around: what if you skip union by rank and ONLY do path compression instead?

        在某种意义上，路融为一体pression是一个额外的步骤，按等级来提高联盟，这就是为什么可以不灾难性的后果被忽略了额外的步骤。但是，按职级工会的必要中间步骤的路径COM pression？我可以跳过它，直接进入路径COM pression，还是会说是灾难性的？

        In a sense, path compression is an extra step to improve union by rank, and that's why that extra step can be omitted without disastrous consequence. But is union by rank a necessary intermediate step to path compression? Can I skip it and go straight to path compression, or will that be catastrophic?

        有人还指出，没有按职级工会，工会重复可以创建一个链表结构。这意味着，单个路径COM pression操作可能需要 O（N）在最坏的情况下。这当然会影响到未来的行动，因此如何发挥出来时，在许多操作摊销是什么，我更感兴趣的是

        It was also pointed out that without union by rank, repeated unions could create a linked-list like structure. This means that a single path compression operation could take O(n) in the worst case. This would of course affect future operations, so how this plays out when amortized over many operations is what I'm more interested in.

        推荐答案

        我用Google搜索没有工会按职级，第二个链接想出了<一个href="http://books.google.ru/books?id=oK3UWxg_UhsC&pg=PA224&lpg=PA224&dq=%22without+union+by+rank%22&source=bl&ots=iGGO7XKp6L&sig=U76thEmxJZ4oadMQPRbW8sA9tDI&hl=ru&ei=PDeFS5OFNJPw-QbQxIyeAQ&sa=X&oi=book_result&ct=result&resnum=4&ved=0CBMQ6AEwAw#v=onepage&q=%22without%20union%20by%20rank%22&f=false">this 之一：

        I googled for "without union by rank" and the second link that came up was this one:

        ...我们结束本节用   分析工会找到路径   COM pression但没有互助社   秩...

        ...We close this section with an analysis of union–find with path compression but without union by rank...

        该联盟发现的数据结构与路径   COM pression但没有工会按等级   流程米的发现和n-1链接   在时间O（（M + N）log n）的操作

        The union-find datastructure with path compression but without union by rank processes m find and n-1 link operations in time O((m+n) log n)

        这篇关于联盟/查找算法，而不互助社职级不相交集森林数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！