Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

And lookup sets are generally used to simulate merge and lookup operations on sets. But there doesn’t seem to be an official implementation.

If we do it manually, we’ll start with the simplest effect, assuming we have five elements, each of which belongs to a set. Let’s store a state for it, let’s say it’s recorded as minus 1 as a set alone.

Five vertices, 0,1,2,3,4.

a,b,c,d,e = 0.1.2.3.4 # five vertices
parent = [-1] *5 The stored state is called parent because it looks like a tree behind it

Copy the code

Now let’s think about the merge operation in this case, if we want to merge the sets A and C. The operation is to treat one of a or C as a parent node of a tree structure, and the other as a child node. Let’s say a is the parent node.

Like this

parent[c] = a
Copy the code

C after this saved state, it is not 1, find a collection of c is find by its parent node, if it is less than zero (later in this article will explain, is now only consider – 1, it also belongs to the less than 0) says find the set at the beginning of node, this collection is to identify with this one vertex Make out the same collection. Now there is only one layer, but even if you have more layers you will see the same process.

So the search operation could look something like this

def find(parent: List[int],e: int) - >int:
    if parent[e] < 0: 
        return e
    return find(parent,parent[e])

Copy the code

When searching for two elements, if the two elements do not belong to the same set, you can do a simple merge operation, put the root vertex of one set under the root vertex of the other set, as the child node. Because the find function looks for the root node, it simply operates on this value.

So it looks like this

def union(parent: List[int],x: int,y: int) :
    x = find(parent,x)
    y = find(parent,y)
    parent[x] = y
Copy the code

The simple merge operation is complete.

If y is a one-layer tree and x is a multi-layer tree, then the tree representing the collection will add one layer each time, and in the worst case, reach the same depth as the parent array.

We want to avoid that, so we’re going to use the one that’s less than 0.

So at the very beginning, we initialized it to minus 1, and we could read it this way, minus 1 is the negative of the depth of the tree.

And then when we merge, we always do something like this, when two trees are the same height, we connect them randomly, and then we add the depth of the parent tree. In the case of a long and a short tree, the short tree can be a child of the long tree, so the depth of the tree does not increase.

So it’s going to look something like this

def union(parent: List[int],x: int,y: int) :
    x = find(parent,x)
    y = find(parent,y)
    if x == y:
        parent[x] = y
        parent[y] -=1
    elif x > y: # -x < -y, x connects to y
        parent[x] = y
    else:
        parent[y] = x
Copy the code

The implementation of going here and looking up the set is done. The time complexity is log(n).

If you want it to be more usable, you can wrap it as a class. In this case, the parent array might seem a bit inappropriate, so there is another implementation that splits the depth of the parent array into another array that only places the parent node. The root node of its set is represented by itself. If it is not equal to itself, the parent node needs to be looked up.

Both implementations are functionally identical, but the other is more prescriptive. In addition, if parent implements hash tables instead of arrays, it can even use named nodes for greater versatility.