next up previous contents index
Next: Dictionary Types Up: Basic Data Types Previous: Dynamic Trees ( dynamic_trees   Contents   Index


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(const 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.


next up previous contents index
Next: Dictionary Types Up: Basic Data Types Previous: Dynamic Trees ( dynamic_trees   Contents   Index
root 2008-01-09