Dynamic Collections of Trees ( tree_collection )

Definition

An instance D of the parameterized data type tree_collection<I> 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.

#include < LEDA/core/tree_collection.h >

Creation

tree_collection<I>

D

creates an instance D of type tree_collection<I>, initialized with the empty collection.

Operations

d_vertex	D.maketree(I x)	adds a new tree to D containing a single vertex v with cost zero and information x, and returns v.
const I&	D.inf(d_vertex v)	returns the information of vertex v.
d_vertex	D.findroot(d_vertex v)	returns the root of the tree containing v.
d_vertex	D.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.
d_vertex	D.parent(d_vertex v)	returns the parent vertex of v.
void	D.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).
void	D.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.) Precondition v and w are in different trees and v is a root.
void	D.cut(d_vertex v)	divides the tree containing vertex v into two trees by deleting the edge out of v. Precondition 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 [86]). All operations take amortized time O(log n) where n is the number of maketree operations.