\manpage {tree\_collection} {I} {Dynamic Collections of Trees}
 
\definition
An instance $D$ of the parameterized data type \name\ is a
collection of vertex disjoint rooted trees, each of whose vertices has a
double-valued cost and contains an information of type $I$, called the
information type of $D$.
 
\creation D  
 
\create { }
   { creates an instance \var\ of type \name, initialized with the
            empty collection. }
 
 
\operations 2 5
 
\op  d\_vertex maketree {(I\ x)}
           {  Adds a new tree to $D$ containing a single
	      vertex $v$ with cost zero and information $x$,
	      and returns $v$. }
 
 
\op  I inf {(d\_vertex\ v)}
           {  Returns the information of vertex $v$. }
 
 
\op  d\_vertex findroot {(d\_vertex\ v)}
           {  Returns the root of the tree containing $v$. }
 
 
\opl d\_vertex findcost {(d\_vertex\ v, double\&\ x)}
           {  Sets $x$ to the minimum cost of a vertex on the
	      tree path from $v$ to findroot($v$) and returns
	      the last vertex (closest to the root) on this
	      path of cost $x$. }
 
 
\opl void addcost {(d\_vertex\ v, double\ x)}
           {  Adds double number $x$ to the cost of every vertex
	     on the tree path from $v$ to findroot($v$). }
 
 
\opl void link {(d\_vertex\ v, d\_vertex\ x)}
           {  Combines the trees containing vertices $v$ and $w$
	     by adding the edge $(v,w)$. (We regard tree
	     edges as directed from child to parent.)\\
	     \precond $v$ and $w$ are in different trees
	     and $v$ is a root. }
 
 
\op  void cut {(d\_vertex\ v)}
           {  Divides the tree containing vertex $v$ into
	     two trees by deleting the edge out of $v$.\\
	     \precond $v$ is not a tree root. }
 
 
\implementation
Dynamic collections of trees are implemented by partitioning the trees
into vertex disjoint paths and representing each path by a self-adjusting
binary tree (see \cite{T83}). All operations take amortized time $O(\log n)$
where $n$ is the number of maketree operations.
 
