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/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. |
| 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 [76]). All operations take amortized time O(log n) where n is the number of maketree operations.