And check sets (the Union – find)

The unjoint set is a tree type data structure, which is used to deal with the merging and querying problems of disjoint sets. Often represented in use by forest.

And look up set basics

And look up the problem solved by the set

Connectivity problem

  1. Based on thedyeingThe idea is that at the beginning all the dots are different colors
  2. The operation of linking two points can be thought of asA kind of colordyedAnother color
  3. If the two points have the same color, they are connected, otherwise they are disconnected
  4. This method is called Quick-Find.

// And Find the set -> quick-find algorithm
export class QuickFind {
  color: number[];
  n: number;
  constructor(n: number) {
    this.color = [];
    this.n = n;
    for (let i = 0; i < n; i++) {
      this.color[i] = i;
    }
  }
  find(ind: number) :number {
    return this.color[ind];
  }
  merge(a: number.b: number) :void {
    if (this.color[a] === this.color[b]) return;
    const cb = this.color[b];
    for (let i = 0; i < this.n; i++) {
      if (this.color[i] === cb) this.color[i] = this.color[a];
    }
    return; }}Copy the code
Summary of Quick-find algorithm

Unicom judgment: O(1)

Merge operation: O(n)

Problem thinking:

  • Quick-FindThe algorithm’s connection judgment is very fast, but the merge operation is very slow
  • Essentially the problem is just to know which points are the same color as a point
  • Several points of color can be indirectly directed to the same node
  • When you merge, you actually treat one tree as a subtree of another tree –>Quick-Unionalgorithm
// Query the set -> quick-union algorithm
export class QuickUnion {
  boss: number[];
  n: number;
  constructor(n: number) {
    this.boss = [];
    this.n = n;
    for (let i = 0; i < n; i++) {
      this.boss[i] = i;
    }
  }
  find(ind: number) :number {
    return this.boss[ind] === ind ? ind : this.find(this.boss[ind]);
  }
  merge(a: number.b: number) :void {
    const fa = this.find(a);
    const fb = this.find(b);
    if (fa === fb) return;
    this.boss[fa] = fb; // Faster than QuickFind O(1)
    return; }}Copy the code
Summary of Quick-union algorithm

Find: tree-height Indicates the tree height

Merge operation: tree-height Indicates the tree height

thinking

  1. In extreme cases, it degenerates into a chain
  2. The high number of nodes are joined to the low number of trees, resulting in degradation
  3. Bringing the tree deeper to the shallower surface, causing degradation
  4. To improve, pressNumber of nodesOr in accordance with theThe height of the treeFor merge reference? Indicator: Average search times = Total search times/Number of nodes The minimum average search times is the optimal setting aThe sum of all nodes in the tree isS(a), the sum of tree heights of all nodes (total number of lookups) isl(a) 设 bThe sum of all nodes in the tree isS(b), the sum of tree heights of all nodes (total number of lookups) isl(b) 若 aTree as the parent node, then the combined average search = l + l (a) (b) + S/S + S (a) (b) (b) / / molecular + S (b) because ` ` bAll of the nodes in the tree have a depth of +1B ‘tree as parent node, then the average number of lookups after merging = L (a) + L (b) +S(a)/ S(a) +S(b)
  5. The optimization algorithm that adds four steps is calledWeighted-Quick-Unionalgorithm
export class WeightedQuickUnion {
  fa: number[];
  size: number[]; // Number of subtrees
  n: number;
  constructor(n: number) {
    this.fa = [];
    this.size = [];
    this.n = n;
    for (let i = 0; i < n; i++) {
      this.fa[i] = i;
      this.size[i] = 1;
    }
  }
  find(x: number) :number {
    return this.fa[x] === x ? x : this.find(this.fa[x]);
  }
  merge(a: number.b: number) :void {
    const ra = this.find(a);
    const rb = this.find(b);
    if (this.size[ra] < this.size[rb]) { // Optimize according to quality
      this.fa[ra] = rb;
      this.size[rb] += this.size[ra];
    } else {
      this.fa[rb] = ra;
      this.size[ra] += this.size[rb];
    }
    return; }}Copy the code

Is there anything else you can optimize? We find that we have to traverse the root node every time we find, going through many layers. Can we optimize the search process? Of course, we can optimize the path by making each child node point directly to root.

The following code

export class WeightedQuickUnionPC {
  // PC: path compress Indicates the path compression
  fa: number[];
  size: number[]; // Number of subtrees
  n: number;
  constructor(n: number) {
    this.fa = [];
    this.size = [];
    this.n = n;
    for (let i = 0; i < n; i++) {
      this.fa[i] = i;
      this.size[i] = 1;
    }
  }
  find(x: number) :number {
    // return this.fa[x] === x ? x : this.find(this.fa[x]);

    // if (this.fa[x] === x) return x;
    // const root = this.find(this.fa[x]);
    // this.fa[x] = root; // Path compression optimization
    // return root;
    return this.fa[x] === x ? x : (this.fa[x] = this.find(this.fa[x]));
  }
  merge(a: number.b: number) :void {
    const ra = this.find(a);
    const rb = this.find(b);
    if (this.size[ra] < this.size[rb]) {
      this.fa[ra] = rb;
      this.size[rb] += this.size[ra];
    } else {
      this.fa[rb] = ra;
      this.size[ra] += this.size[rb];
    }
    return; }}Copy the code

At this point, we are done and looking up the optimal implementation of the set.

Use hand

In the running speed test, we will find that the benefits of path compression optimization are far greater than per-node optimization. And path compression code implementation is very simple, easy to remember. So when we do daily arithmetic problems, the general implementation of matching and searching sets is

export class QuickUnionPC {
  // PC: path compress Indicates the path compression
  fa: number[];
  n: number;
  constructor(n: number) {
    this.fa = [];
    this.n = n;
    for (let i = 0; i < n; i++) {
      this.fa[i] = i;
    }
  }
  find(x: number) :number {
    // return this.fa[x] === x ? x : this.find(this.fa[x]);

    // if (this.fa[x] === x) return x;
    // const root = this.find(this.fa[x]);
    // this.fa[x] = root; // Path compression optimization
    // return root;
    return this.fa[x] === x ? x : (this.fa[x] = this.find(this.fa[x]));
  }
  merge(a: number.b: number) :void {
    const fa = this.find(a);
    const fb = this.find(b);
    if (fa === fb) return;
    this.fa[fa] = fb; // Much faster than QuickFind
    return; }}Copy the code

At this point, our and search set learning to come to an end, we brush with new knowledge points.