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.

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 -> 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 -> 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 e_inf 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(log^2 n) amortized expected time except for make which takes constant time. n is the current number of nodes.