并查集的树型存储表示及优化实现

本文简单介绍一种特殊的集合—并查集,用树的双亲表示法静态存储并查集的方法,给出了相应的类声明和构造函数,特别是并查集的三种关键操作的实现算法及性能分析,最后通过加权规则改进Union操作,从而消除形成退化树的可能。

The Storage Describing of Union-find Sets in Tree-form and Optimal Realization

This paper simply described a special kind of set which is named Union-find sets,which can be store statically through the method of parents describing of tree.Corresponding class-describing and constructed function of that union-find sets were alsogiven in this paper.The realizing method and capability analyzing to three key operation of union-find sets were present also.How the possibility of forming degenerated-tree can be destroyed by an improved operation which in weighted rule was discussed in the last part of this paper.