Union find tree without ranks
Difference between en1 and en2, changed 10 character(s)
The traditional implementation of union find tree (aka disjoint set) utilizes rank compression — this is the code with it.↵


~~~~~↵
int parent[1000], rank[1000];↵

int find(int x){↵
    return parent[x] = (parent[x] == x ? x : find(parent[x]));↵
}↵

void Union(int p, int q){↵
    p = find(p);↵
    q = find(q);↵
    if(rank[p] < rank[q]) parent[p] = q;↵
    else parent[q] = p;↵
    if(rank[p] == rank[q]) rank[p]++;↵
}↵
~~~~~↵



But in competitive programming, I found out that the rank compression was useless. Without rank compression, the code was shorter, and even the program ran faster. This is my implementation without rank compression.↵


~~~~~↵
int parent[1000];↵

void Union(int p, int q){ parent[find(p)] = find(q); }↵
~~~~~↵



and for some cases, I found implementing rank compression is quite hard (maybe impossible). ↵

I will give you a sample problem : "Given a tree T, you should process Q queries &mdash; "paint the edge's value into x (>0) from path s to e". ↵

I reversed the query, broke down the path s &mdash; e to s &mdash; LCA(s,e) &mdash; e, and used this algorithm to paint the tree. (root_val[s] : value of edge s &mdash; parent(s), dep[s] = depth of s. nxt[s] = parent(s)) ↵

~~~~~↵
int paint(int s, int e, int x){  ↵
    if(dep[s] <= dep[e]) return s;  ↵
    if(!root_val[s]) root_val[s] = x;  ↵
    return nxt[s] = paint(nxt[s],e,x);  ↵
}↵
~~~~~↵

All of those program ran very fast in practice, but I was curious about the worst-case runtime of such path compression without ranks, so I googled for a while but didn't find any answer. Here's my question:↵

1. Does the path compression runs in (amortized) sublinear time
 per query?↵
2. If it doesn't, is there any counterexamples for that?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ko_osaga 2015-11-08 07:58:52 10 Tiny change: 'inear time?\n2. If i' -> 'inear time per query?\n2. If i'
en1 English ko_osaga 2015-11-08 06:51:42 1770 Initial revision (published)