B station address

concept

The search set is a tree type data structure, which is used to deal with the merge and query problems of some disjoint sets. Often represented in use by forest.

Application scenarios

Give two chestnuts 🌰 :

  1. Not all the people in your circle of friends know each other directly. If Zhang’s friend is Wang and Wang’s friend is Li, they belong to the same circle of friends. Given a number of friends, determine whether two people are in the same group of friends.
  2. If Xiao Zhang has a relative, Xiao Wang, and Xiao Wang has a relative, Xiao Li, then Xiao Zhang and Xiao Li are related. Given a number of relatives, determine whether two people are related.

Therefore, the joint search set is mainly applied to some connectivity problems, dealing with the intersection of sets and the query of the set elements belong to the problem.

The demo

The main operating

Initialize the

Initialize the set of each point as itself. Typically, this step is performed once at initialization of the data structure, in O(n) time, regardless of implementation.

To find the

Find the collection of elements, the root node.

merge

Merges the set of two elements into a single set.

Code implementation

staining

As the name implies, when merging sets in this way, elements of one set are dyed into the color of another set. Elements with the same color are elements of the same set.

The code is as follows:

Constructor (n){// this. Colors = Array(n); // color each element with its subscript for(let I = 0; i<n; i++){ this.colors[i] = i; Find (x){return this.colors[x]} merge(a,b){ B const ca = this.colors[a],cb = this.colors[b]; For (let I =0; i<this.colors.length; i++){ if(this.colors[i]===cb){ this.colors[i] = ca } } } }Copy the code

Tree structure

The merge operation time complexity is O(n), and the parallel and lookup set is implemented using a tree structure, so we only need to mount the tree of one element to the tree of another element, and the merge operation time complexity is O(1). Although the search operation of this way (time complexity O(logn)) is less efficient than the dyeing method (time complexity O(1)), it is still more efficient overall, and more optimization can be carried out for the union search set of attribute structure.

The code is as follows:

Constructor (n){constructor(n){this.list = Array(n); // initialize the set of each element to itself for(let I = 0; i<n; If (this.list[x]===x) return x; if(this.list[x]===x) return x; if(this.list[x]===x) return x; Const rootA = this.find(a),rootB = const rootA = this.find(a),rootB = const rootA = this.find(a),rootB = this.find(b); If (rootA===rootB) return; This. list[rootB] = rootA; }}Copy the code

Optimization of tree height

In this version of the code above, we just arbitrarily merged the set of B into the set of A, which, in extreme cases, is possible to form a linked list of trees. To prevent this from happening, we can determine that there are more nodes in the two trees. To optimize the efficiency of the subsequent search, we should mount the tree with fewer nodes under the tree with more nodes.

The code is as follows:

This. size = Array(n).fill(1); This. list = Array(n); // initialize the set of each element to itself for(let I = 0; i<n; If (this.list[x]===x) return x; if(this.list[x]===x) return x; if(this.list[x]===x) return x; Const rootA = this.find(a),rootB = const rootA = this.find(a),rootB = const rootA = this.find(a),rootB = this.find(b); If (rootA===rootB) return; If (this.size[rootA]<this.size[rootB]){this.list[rootA] = rootB; this.size[rootB] += this.size[rootA] }else{ this.list[rootB] = rootA; this.size[rootA] += this.size[rootB] } } }Copy the code

Path to the compression

After the above optimization, our union lookup set is already efficient, but for find operations, further optimization can be made. The method is to get the root node of the set of elements in the find operation, and then mount the current element directly to the root node, so that the next time to get the root node of the element, only two lookups are needed, and the time complexity of O(logn) is optimized to O(1).

This. size = Array(n).fill(1); This. list = Array(n); // initialize the set of each element to itself for(let I = 0; i<n; If (this.list[x]===x) return x; if(this.list[x]===x) return x; if(this.list[x]===x) return x; Const root = this.find(this.list[x]) // Mount the current node as the root node. // Return root; } // Merge merge(a,b){const rootA = this.find(a),rootB = this.find(b); If (rootA===rootB) return; If (this.size[rootA]<this.size[rootB]){this.list[rootA] = rootB; this.size[rootB] += this.size[rootA] }else{ this.list[rootB] = rootA; this.size[rootA] += this.size[rootB] } } }Copy the code

At this point, we have completed the concept and search set, application scenarios and handwritten implementation of the whole process.

If you have any questions or suggestions, please leave a comment!