Rake-Compress Trees (RC-Trees)
A library for maintaining Dynamic Trees
Copyright (c) 2004
Guy Blelloch, Umut Acar, Jorge Vittes
School of Computer Science
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, Pennsylvania 15213-3891
Please send bugs and comments to blelloch@cs.cmu.edu
Created as part of the Aladdin Center, supported in part by NSF Grant
CCR-0122581. There is no warranty whatsoever. Use at your own risk.
These programs may be freely redistributed under the condition that the
copyright notices in each file.
This library is designed to support many interfaces for dynamic trees.
All interfaces support link (adding an edge) and cut (deleting an
edge) operations, but they can support different types of queries and
data updates on the tree. The user can specialize it to their own
operations, or can use one of the several supplied interfaces. The
ideas behind the library are described in a paper:
An Experimental Analysis of Change Propagation in Dynamic Trees
Umut A. Acar, Guy E. Blelloch, Jorge L. Vittes
CMU Technical Report #???
The paper can be found as part of the release in RCtrees.ps.
The release consists of the following directories:
rcTrees: This contains the main library that supports all the
different interfaces for dynamic trees, and implements the link and
cut operations. It allows abstract data to be stored at each node
of the support tree. The particular interface needs to define what
this data is and how it is manipulated.
All the following interfaces assume that edges are weighted and that
the tree is not rooted. It is easy to add information that can root a
tree. The distance between two vertices in the same tree is
defined as the sum of the weights of edges on the path and is denoted
as d(u,v).
center: This supports finding the center of a tree. The center is the
vertex v that maximizes Max{v' in V} d(v,v').
closest: This supports finding for a vertex v the closest marked
vertex in a forest. Each vertex can be dynamically marked or unmarked.
diameter: This supports finding the diameter of a tree. The diameter
is Max{u,v in V} d(u,v).
median: This supports finding the median of a tree. The median is the
vertex v that minimized Sum{v' in V} d(v,v').
path: Finds the maximum weight edge on a path between any two vertices.
subtree: Find the maximum weight edge on any subtree.
------------------------------------------------------------------------------
To compile go to any of the interface subdirectories and run make.
In addition to making the library for that interface it will compile
Example.c which is an example of how to use it.