Check and set

introduce

And lookup set is a tree data structure. From its name, we can see that it is used to deal with the merging or query of some unrelated sets. It is also widely used, such as finding the number of connected components of an undirected graph and the minimum common ancestor

  • Merge: To merge two unrelated collections into one
  • Find: Finds if elements are in a collection

Click here to view the full source code: view the source code

example

This can be explained by a simple example of what a union lookup set is.

In an Internet company, the company needs to set up a new department, which is highly skilled. Now the department needs to recruit employees and a technical Leader, who will be selected from the employees recruited this time.

Now five technicians are here for the interview. The process of robbing technical leaders is carried out. Interviewer 1 interview Zhang SAN Li Si, interviewer 2 interview Wang Wu Zhao Liu Tian qi

John came to the interview first, and the interviewer felt that John had good technical or interpersonal skills and that the company could hire him

After a while, there came another person who was skilled in the interview. After the evaluation of the interviewer, there was no problem in hiring this person. However, compared with Zhang SAN, he lacked the ability to deal with interpersonal relations, so Zhang SAN was selected as the technical Leader among them

At the other interviewers, Wang wu beat Zhao Liu and Tian Qi, so that Wang Wu became their superior

As a technical Leader, of course, he is the most skilled person in the department, so Wang Wu wants to challenge others. At this moment, he starts with Li Si and challenges Li Si first. Li Si says, “You don’t need to challenge me any more.

After a fierce challenge, finally Wang Wu won, Zhang SAN will take Li Si to merge with wang Wu below

And look up the steps of the set

The main operations of parallel lookup are initialization, lookup and merge

Initialization: As in the example above, they don’t know each other at first, so the initialization itself is ok (you can think of it as treating themselves as a collection).

Search: search the ancestor node of the current node,(see the last picture li Si’s ancestor node is 55, Tian Qi’s ancestor node is 55) to put it bluntly is to find the superior of a node, has been found can’t go up is its ancestor node

Merge: This is easier to understand, as you can think of the connection between nodes in the example above as a merge

code

There are a couple of ways to implement and look up sets, but I’m just going to talk about how to use and look up sets with a Map, okay

The structure of the body

type Node struct {
	Val string
}

type UnionSet struct {
	Nodes   map[string]Node
	Parents map[Node]Node
	SizeMap map[Node]int
}
Copy the code

The Node structure in the code wraps the input data once, because the address is used to determine whether an object is an object

Nodes: Indicates the mapping between input data and wrapped data

Parents: This store the corresponding relationship between the child node and the parent node. From the relationship between Tian Qi and Wang Wu in the figure above, it can be written as map[Tian Qi]= Wang Wu

SizeMap: the size of the store is on behalf of the node, the node what here mean? What is stored inside is the size of each representative node. The so-called representative node is the ancestor node, which is a node up to the node that cannot be up

Initialization code

func (u *UnionSet) InitUnionSet(values []string) {
	u.Nodes = make(map[string]Node)
	u.Parents = make(map[Node]Node)
	u.SizeMap = make(map[Node]int)

	for _, value := range values {
		n := &Node{Val: value}
		u.Nodes[value] = *n
		u.Parents[*n] = *n
		u.SizeMap[*n] = 1}}Copy the code

SizeMap () {SizeMap (); SizeMap (); SizeMap (); SizeMap (); SizeMap () So the size of itself,SizeMap is going to be 1 which is the size of itself

Find the ancestor node

func (u *UnionSet) findAncestorNode(n string) Node {
	tempNode := u.Nodes[n]
	fortempNode ! = u.Parents[tempNode] { tempNode = u.Parents[tempNode] }return tempNode
}
Copy the code

This method is used to find the ancestor Node. When passing in an element to find the ancestor Node, first find the Node object in Nodes and then go to Parents to find its parent Node. The parent Node in the ancestor Node is itself, so return tempNode when it is the same as the parent Node Return to the corresponding tempNode, otherwise assign the found parent node to tempNode, and repeat the loop.

Check if they’re in the same set

func (u *UnionSet) isSet(nodePre string, nodeSuffix string) bool {
	return u.findAncestorNode(nodePre) == u.findAncestorNode(nodeSuffix)
}
Copy the code

The function of checking whether a node is in the same set is to find the ancestor nodes of a node and determine whether they are equal to determine whether they are in the same set

Merge two nodes

func (u *UnionSet) unionNode(nodePre string, nodeSuffix string) {
	tempAncestorNodePre := u.findAncestorNode(nodePre)
	tempAncestorNodeSuffix := u.findAncestorNode(nodeSuffix)

	iftempAncestorNodePre ! = tempAncestorNodeSuffix { nodePreSize := u.SizeMap[tempAncestorNodePre] nodeSuffixSize := u.SizeMap[tempAncestorNodeSuffix]ifnodePreSize >= nodeSuffixSize { u.Parents[tempAncestorNodeSuffix] = tempAncestorNodePre u.SizeMap[tempAncestorNodePre] =  nodePreSize + nodeSuffixSizedelete(u.SizeMap, tempAncestorNodeSuffix)
		} else {
			u.Parents[tempAncestorNodePre] = tempAncestorNodeSuffix
			u.SizeMap[tempAncestorNodeSuffix] = nodePreSize + nodeSuffixSize
			delete(u.SizeMap, tempAncestorNodePre)
		}
	}
}
Copy the code

To merge two nodes, it is necessary to find their ancestor node first. If the two nodes are different, they are not in the same set, and the operation of merging is started.

How do you merge?

The rule used here is that nodes with small lengths hang below nodes with large lengths.

Get the representative node in if there are several nodes below (nodePreSize := u.SizeMap[tempAncestorNodePre],nodeSuffixSize := u.SizeMap[tempAncestorNodeSuffix]) Then judge the number of nodes to assign values into map respectively. Here, the Size of the newly assigned value is the result of the addition of these two nodes

Delete (u.SizeMap, tempAncestorNodeSuffix): Because SizeMap is the size of the stored ancestor node, when combined, the size of the original node is deleted

Flatten the node during lookup

func (u *UnionSet) findAncestorNode(n string) Node {
	tempNode := u.Nodes[n]
	tempNodeQueue := []Node{}
	fortempNode ! = u.Parents[tempNode] { tempNodeQueue =append(tempNodeQueue, tempNode)
		tempNode = u.Parents[tempNode]
	}

	for len(tempNodeQueue) > 0 {
		node := tempNodeQueue[0]
		u.Parents[node] = tempNode
		tempNodeQueue = tempNodeQueue[1:]}return tempNode
}
Copy the code

Here is the method of searching the ancestor node modified, the modified can improve the speed of searching,

This method, when it looks up, puts all the nodes along the way into the slice,

After the first for completes the loop, the ancestor node (tempNode) is found and the passing node is added to the slice.

The second loop ejects the data in the slice, changes the parent node of the ejected node to (tempNode),

And you end up with something like this,

This can reduce the number of traversals, which is still a good solution, the flattening time for nodes is O(N).