Shulou(Shulou.com)06/01 Report--

This article mainly introduces the java and check the sample analysis, has a certain reference value, interested friends can refer to, I hope you read this article after a lot of gains, the following let Xiaobian take you to understand.

I. Overview

A tree-type data structure used to solve the problem of merging and querying disjoint sets. For example: there are n villages, query whether there is a connecting road between the two villages, connecting the two villages

The two cores:

Find: Find the collection in which the element is located

Union: Combines two sets of elements into one set

II. Realization

There are two common ways to implement a parallel lookup set

Quick Find

Time complexity of finding: O (1)

Time complexity of union: O (n)

Quick Union

Time complexity of Find: O (logn) can be optimized to O (a (n)) a (n)

< 5 合并（Union）的时间复杂度：O（logn）可以优化至O（a（n））a（n）< 5 使用数组实现树型结构，数组下标为元素，数组存储的值为父节点的值 创建抽象类Union Find public abstract class UnionFind { int[] parents; /** * 初始化并查集 * @param capacity */ public UnionFind(int capacity){ if(capacity < 0) { throw new IllegalArgumentException("capacity must be >

=0"); } //Initially, each element parent node (root node) is itself parents = new int[capacity]; for(int i = 0; i

< parents.length;i++) { parents[i] = i; } } /** * 检查v1 v2 是否属于同一个集合 */ public boolean isSame(int v1,int v2) { return find(v1) == find(v2); } /** * 查找v所属的集合 （根节点） */ public abstract int find(int v); /** * 合并v1 v2 所属的集合 */ public abstract void union(int v1, int v2); // 范围检查 public void rangeCheck(int v) { if(v parents.length) throw new IllegalArgumentException("v is out of capacity"); }}2.1 Quick Find实现 以Quick Find实现的并查集，树的高度最高为2，每个节点的父节点就是根节点 public class UnionFind_QF extends UnionFind { public UnionFind_QF(int capacity) { super(capacity); } // 查@Override public int find(int v) { rangeCheck(v); return parents[v]; } // 并 将v1所在集合并到v2所在集合上@Overridepublic void union(int v1, int v2) { // 查找v1 v2 的父（根）节点 int p1= find(v1); int p2 = find(v2); if(p1 == p2) return; //将所有以v1的根节点为根节点的元素全部并到v2所在集合上 即父节点改为v2的父节点 for(int i = 0; i< parents.length; i++) { if(parents[i] == p1) { parents[i] = p2; } } }}2.2 Quick Union实现 public class UnionFind_QU extends UnionFind { public UnionFind_QU(int capacity) { super(capacity); } //查某一个元素的根节点 @Override public int find(int v) { //检查下标是否越界 rangeCheck(v); // 一直循环查找节点的根节点 while (v != parents[v]) { v = parents[v]; } return v; } //V1 并到 v2 中 @Override public void union(int v1, int v2) { int p1 = find(v1); int p2 = find(v2); if(p1 == p2) return; //将v1 根节点 的 父节点 修改为 v2的根结点 完成合并 parents[p1] = p2; }}三、优化 并查集常用快并来实现，但是快并有时会出现树不平衡的情况 有两种优化思路：rank优化，size优化 3.1基于size的优化 核心思想：元素少的树 嫁接到 元素多的树 public class UniondFind_QU_S extends UnionFind{ // 创建sizes 数组记录 以元素（下标）为根结点的元素（节点）个数 private int[] sizes; public UniondFind_QU_S(int capacity) { super(capacity); sizes = new int[capacity]; //初始都为 1 for(int i = 0;i < sizes.length;i++) { sizes[i] = 1; } } @Override public int find(int v) { rangeCheck(v); while (v != parents[v]) { v = parents[v]; } return v; } @Override public void union(int v1, int v2) { int p1 = find(v1); int p2 = find(v2); if(p1 == p2) return; //如果以p1为根结点的元素个数 小于 以p2为根结点的元素个数 p1并到p2上，并且更新p2为根结点的元素个数 if(sizes[p1] < sizes[p2]) { parents[p1] = p2; sizes[p2] += sizes[p1]; // 反之 则p2 并到 p1 上，更新p1为根结点的元素个数 }else { parents[p2] = p1; sizes[p1] += sizes[p2]; } }} 基于size优化还有可能会导致树不平衡 3.2基于rank优化 核心思想：矮的树 嫁接到 高的树 public class UnionFind_QU_R extends UnionFind_QU { // 创建rank数组 ranks[i] 代表以i为根节点的树的高度 private int[] ranks; public UnionFind_QU_R(int capacity) { super(capacity); ranks = new int[capacity]; for(int i = 0;i < ranks.length;i++) { ranks[i] = 1; } } public void union(int v1, int v2) { int p1 = find(v1); int p2 = find(v2); if(p1 == p2) return; // p1 并到 p2 上 p2为根 树的高度不变 if(ranks[p1] < ranks[p2]) { parents[p1] = p2; // p2 并到 p1 上 p1为根 树的高度不变 } else if(ranks[p1] >

ranks[p2]) { parents[p2] = p1; }else { //height is the same p1 and up to p2, p2 is the height of the root tree +1 parents[p1] = p2; ranks[p2] += 1; } }}

Based on rank optimization, as the number of Union increases, the height of the tree will still get higher and higher, resulting in slower find operation.

There are three ways to optimize: path compression, path splitting, and path halving.

3.2.1 Path Compression

Make all nodes on the path point to the root node when finding, thus reducing the height of the tree

/** * Quick Union -rank-based optimization-path compression * */public class UnionFind_QU_R_PC extends UnionFind_QU_R { public UnionFind_QU_R_PC(int capacity) { super(capacity); } @Override public int find(int v) { rangeCheck(v); if(parents[v] != v) { //Recursion causes all parent nodes from the current v to the root node to be changed to the root node parents[v] = find(parents[v]); } return parents[v]; }}

Although the tree height can be reduced, the implementation cost is slightly higher.

3.2.2 Path Splitting

Make every node on the path point to its grandparent node

/** * Quick Union -rank-based optimization-path splitting * */public class UnionFind_QU_R_PS extends UnionFind_QU_R { public UnionFind_QU_R_PS(int capacity) { super(capacity); } @Override public int find(int v) { rangeCheck(v); while(v != parents[v]) { int p = parents[v]; parents[v] = parents[parents[v]]; v = p; } return v; 3.2.3 Path Halving

Make every other node on the path point to its grandparent node

/** * Quick Union -rank-based optimization-path halving * */public class UnionFind_QU_R_PH extends UnionFind_QU_R { public UnionFind_QU_R_PH(int capacity) { super(capacity); } public int find(int v) { rangeCheck(v); while(v != parents[v]) { parents[v] = parents[parents[v]]; v = parents[v]; } return v; } }

Use Quick Union + rank-based optimization + path splitting or path halving

The average time complexity of each operation is O(a(n)) , a(n) < 5.

Thank you for reading this article carefully. I hope that Xiaobian's shared "Java and Sample Analysis of Search Sets" will help everyone. At the same time, I hope everyone will support you more, pay attention to the industry information channel, and more relevant knowledge is waiting for you to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.