next up previous contents index
Next: Dynamic Collections of Trees Up: Basic Data Types Previous: Parameterized Partitions ( Partition   Contents   Index


Dynamic Trees ( dynamic_trees )

Definition

An instance D of the data type dynamic_trees is a set of dynamically changing rooted trees. Each edge is directed towards the root and has a weight. Optionally, user defined information can be stored at the vertices and at the edges.

Remark Dynamic trees are very similar to the data type tree_collection. The main difference is that the former use edge weights instead of the node weights used by the latter.

#include < LEDA/dynamic _trees.h >

Creation

dynamic_trees D creates an empty instance D of type dynamic_trees.

Operations

vertex D.make(void* x=nil) creates a tree containing a single node v which is returned. The additional user defined information x is stored at v.

void* D.vertex_inf(vertex v) returns the additional user defined information at v.

void* D.edge_inf(vertex v) returns the additional user defined information at (v,parent(v)) or nil, if v has no parent.

vertex D.parent(vertex v) returns the parent of v in the tree or nil.

vertex D.root(vertex v) returns the root of the tree containing v.

double D.cost(vertex v) returns the cost of (v,parent(v)).
Precondition v is not a tree root.

vertex D.mincost(vertex v) returns vertex w closest to root(v) s.t. (w,parent(w)) has minimal cost on the path v $ \rightarrow$ root(v).
Precondition v is not a tree root.

void D.update(vertex v, double x)
    adds x to each edge on the path v $ \rightarrow$ root(v).

void D.link(vertex v, vertex w, double x, void* e_inf=nil)
    links the tree root v (prec.) to the vertex w in a different tree (prec.). The edge e = (v, w) gets weight x, and the additional user defined information einf is stored at e.

double D.cut(vertex v) deletes the edge (v,parent(v)) and returns its weight.
Precondition v is not a tree root.

void D.evert(vertex v) makes v the new root of its tree.

vertex D.lca(vertex v, vertex w) returns the lowest common ancestor of v and w or nil.
Precondition v and w are not nil.

Implementation

Dynamic Trees are implemented using binary trees with the randomized balancing scheme by Aragon and Seidel. Each operation takes O(log2n) amortized expected time except for make which takes constant time. n is the current number of nodes.


next up previous contents index
Next: Dynamic Collections of Trees Up: Basic Data Types Previous: Parameterized Partitions ( Partition   Contents   Index
LEDA research project
2000-02-09