[MINC-development] beta mincmorph

[Steve ROBBINS]

On Tue, Dec 03, 2002 at 08:08:09AM +1000, Andrew Janke wrote:
> On Tue, 3 Dec 2002, Steve ROBBINS wrote:

> > If so, why wouldn't you use parent pointer trees?  They are trivial to
> > implement, will use storage linear in the # of voxels.  With union-by-rank and
> > path compression, the running time is basically linear too.
> 
> As in: http://home.swbell.net/mck9/cobol/tech/tree.html?

No, more like http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic24/ 

Cormen, Leiserson & Rivest have a fantastic discussion about this topic in the
chapter "Data Structures for Disjoint Sets".


> I can't quite see how the storage would be linear and how redundant
> connections would be resolved?  or can each node have more than 2 kiddies?

Yeah -- you can have as many children as you want.  The storage is linear
because you store ONLY the parent pointer.

 
> At then end I assume this tree would be then traversed (depth first) and the
> top value assigned to each value in the tree?

Each group is represented by a tree in the forest.  You find out which group
you are in by traversing parent pointers until you get to the root.  The
root's parent points to itself.  

When you use path compression and union-by-rank, the set operations ("union"
and "find-set") become really really fast: amortized constant time,
essentially.


-S