Top Trees

Information about Top Trees

The Top Tree is a binary tree based Data structure for unrooted dynamic trees which is used mainly for carrying out various path related operations, it allows simple Divide and conquer algorithms. It has since been augmented to maintain dynamically various properties of a Tree such as Diameter, Center and Median.

A Top Tree $\text{[math]}$ is defined for an underlying tree $\text{[math]}$ and a pair of vertices $\text{[math]}$ called as External Boundary Vertices

An image depicting a Top tree built on an underlying tree (black nodes)A tree divided into edge clusters and the complete top-tree for it. Filled nodes in the top-tree are path-clusters, while small circle nodes are leaf-clusters. The big circle node is the root. Capital letters denote clusters, non-capital letters are nodes.

Glossary

Boundary Node

See Boundary Vertex

Boundary Vertex

A vertex in a connected subtree is a Boundary Vertex if it is connected to a vertex outside the subtree by an edge.

External Boundary Vertices

Up to a pair of vertices in the Top Tree $\text{[math]}$ can be called as External Boundary Vertices, they can be thought of as Boundary Vertices of the cluster which represents the entire Top Tree.

Cluster

A cluster is a connected subtree with at most two Boundary Vertices. The set of Boundary Vertices of a given cluster $\text{[math]}$ is denoted as $\text{[math]}$ . With each cluster $\text{[math]}$ the user may associate some meta information $\text{[math]}$ , and give methods to maintain it under the various internal operations.

Path Cluster

If $\text{[math]}$ contains at least one edge then $\text{[math]}$ is called a Path Cluster.

Point Cluster

See Leaf Cluster

Leaf Cluster

If $\text{[math]}$ does not contain any edge i.e $\text{[math]}$ has only one Boundary Vertex then $\text{[math]}$ is called a Leaf Cluster.

Edge Cluster

A Cluster containing a single edge is called an Edge Cluster.

Leaf Edge Cluster

A Leaf in the original Cluster is represented by a Cluster with just a single Boundary Vertex and is called a Leaf Edge Cluster.

Path Edge Cluster

Edge Clusters with two Boundary Nodes are called Path Edge Cluster.

Internal Node

A node in $\text{[math]}$ \ $\text{[math]}$ is called an Internal Node of $\text{[math]}$ .

Cluster Path

The path between the Boundary Vertices of $\text{[math]}$ is called the cluster path of $\text{[math]}$ and it is denoted by $\text{[math]}$ .

Mergeable Clusters

Two Clusters $\text{[math]}$ and $\text{[math]}$ are Mergeable if $\text{[math]}$ is a singleton set (they have exactly one node in common) and $\text{[math]}$ is a Cluster.

Introduction

Top Trees are used for maintaining a Dynamic forest (set of trees) under link and cut operations.

The basic idea is to maintain a balanced Binary tree $\text{[math]}$ of logarithmic height in the number of nodes in the original tree $\text{[math]}$ ( i.e in $\text{[math]}$ time) ; the Top Tree essentially represents the recursive subdivision of the original tree $\text{[math]}$ into clusters''.

In general the tree $\text{[math]}$ may have weight on its edges.

There is a one to one correspondence with the edges of the original tree $\text{[math]}$ and the leaf nodes of the Top Tree $\text{[math]}$ and each internal node of $\text{[math]}$ represents a cluster that is formed due to the union of the clusters that are its children.

The Top Tree data structure can be initialized in $\text{[math]}$ time. $\text{[math]}$

Therefore the Top Tree $\text{[math]}$ over ( $\text{[math]}$ , $\text{[math]}$ ) is a binary tree such that

The nodes of $\text{[math]}$ are clusters of ( $\text{[math]}$ , $\text{[math]}$ );
The leaves of $\text{[math]}$ are the edges of $\text{[math]}$ ;
Sibling clusters are neighbours in the sense that they intersect in a single vertex, and then their parent cluster is their union.
Root of $\text{[math]}$ if the tree $\text{[math]}$ itself, with a set of at most two External Boundary Vertices.

A tree with a single node has an empty top tree, and one with just an edge is just a single node.

These trees are freely augmentable allowing the user a wide variety of flexibility and productivity without going into the details of the internal workings of the data structure, something which is also referred to as the Black Box.

Dynamic Operations

The following two are the user allowable Forest Updates.

Link(v, w): Where $\text{[math]}$ and $\text{[math]}$ are nodes in different trees $\text{[math]}$ ₁ and $\text{[math]}$ ₂. It returns a single top tree representing $\text{[math]}$ _v $\text{[math]}$ $\text{[math]}$ _w $\text{[math]}$
Cut(v, w): Removes the Edge $\text{[math]}$ from a tree $\text{[math]}$ with Top Tree $\text{[math]}$ , thereby turning it into two trees $\text{[math]}$ _v and $\text{[math]}$ _w and returning two Top Trees $\text{[math]}$ _v and $\text{[math]}$ _w.

Expose(v, w): Is called as a subroutine for implementing most of the path related queries on a Top Tree. It makes $\text{[math]}$ and $\text{[math]}$ the External Boundary Vertices of the Top Tree and returns the new Root cluster.

Internal Operations

The Forest updates are all carried out by a sequence of at most $\text{[math]}$ Internal Operations, the sequence of which is computed in further $\text{[math]}$ time.

Merge $\text{[math]}$ Here $\text{[math]}$ and $\text{[math]}$ are Mergeable Clusters, it reutrns $\text{[math]}$ as the parent cluster of $\text{[math]}$ and $\text{[math]}$ and with boundary vertices as the boundary vertices of $\text{[math]}$ . Updates to $\text{[math]}$ are carried out accordingly.
Split $\text{[math]}$ : Here $\text{[math]}$ is $\text{[math]}$ . This deletes the cluster $\text{[math]}$ from $\text{[math]}$ methods are then called to update $\text{[math]}$ and $\text{[math]}$ .

The next two functions are analogous to the above two and are used for base clusters.

Create $\text{[math]}$ : Creates a cluster $\text{[math]}$ for the edge $\text{[math]}$ . Sets $\text{[math]}$ $\text{[math]}$ . Methods are then called to compute $\text{[math]}$ .
Eradicate $\text{[math]}$ : $\text{[math]}$ is the edge cluster $\text{[math]}$ . It deletes the cluster $\text{[math]}$ from the top tree. The $\text{[math]}$ is stored by calling a user defined function, as it may also happen that during a tree update, a leaf cluster may change to a path cluster and the converse.

Interesting Results and Applications

A number of interesting applications have been derived for these Top Trees some of them include

([SLEATOR AND TARJAN 1983]). We can maintain a dynamic collection of weighted trees in $\text{[math]}$ time per link and cut, supporting queries about the maximum edge weight between any two vertices in O (log n) time.
Proof outline: It involves maintaining at each node the maximum weight (max_wt) on its cluster path, if it is a point cluster then max_wt( $\text{[math]}$ ) is initialsed as $\text{[math]}$ . When a cluster is a union of two clusters then it is the maximum value of the two merged clusters. If we have to find the max wt between $\text{[math]}$ and $\text{[math]}$ then we do $\text{[math]}$ Expose $\text{[math]}$ , and report max_wt $\text{[math]}$ .
([SLEATOR AND TARJAN 1983]). In the scenario of the above application we can also add a common weight $\text{[math]}$ to all edges on a given path $\text{[math]}$ Â· Â· Â· $\text{[math]}$ in $\text{[math]}$ time.
Proof outline: We introduce a weight called extra( $\text{[math]}$ ) to be added to all the edges in $\text{[math]}$ . Which is maintained appropriately ; split( $\text{[math]}$ ) requires that, for each path child $\text{[math]}$ of $\text{[math]}$ , we set max_wt(A) := max_wt( $\text{[math]}$ ) + extra( $\text{[math]}$ ) and extra( $\text{[math]}$ ) := extra( $\text{[math]}$ ) + extra( $\text{[math]}$ ). For $\text{[math]}$ := join( $\text{[math]}$ , $\text{[math]}$ ), we set max_wt( $\text{[math]}$ ) := max {max_wt( $\text{[math]}$ ), max_wt( $\text{[math]}$ )} and extra( $\text{[math]}$ ) := 0. Finally, to find the maximum weight on the path $\text{[math]}$ Â· Â· Â· $\text{[math]}$ , we set $\text{[math]}$ := Expose $\text{[math]}$ and return max_wt( $\text{[math]}$ ).
([GOLDBERG ET AL. 1991]). We can ask for the maximum weight in the underlying tree containing a given vertex $\text{[math]}$ in $\text{[math]}$ time.
Proof outline: This requires maintaining additional information about the maximum weight non cluster path edge in a cluster under the Merge and Split operations.
The distance between two vertices $\text{[math]}$ and $\text{[math]}$ can be found in $\text{[math]}$ time as length(Expose $\text{[math]}$ ).
Proof outline:We will maintain the length length( $\text{[math]}$ ) of the cluster path. The length is maintained as the maximum weight except that, if $\text{[math]}$ is created by a join(Merge), length( $\text{[math]}$ ) is the sum of lengths stored with its path children.
Queries regarding diameter of a tree and its subsequent maintenance takes $\text{[math]}$ time.
The Center and Median can me maintained under Link(Merge) and Cut(Split) operations in $\text{[math]}$ time.

Implementation

Top Trees have been implemented in a variety of ways, some of them include implementation using a Multilevel Partition (Top-trees and dynamic graph algorithms Jacob Holm and Kristian de Lichtenberg. Technical Report), and even by using Sleator-Tarjan s-t trees, Fredericksons Topology Trees (Alstrup et al Maintaining Information in Fully Dynamic Trees with Top Trees).

Using Multilevel Partitioning

Any partitioning of clusters of a tree $\text{[math]}$ can be represented by a Cluster Partition Tree CPT $\text{[math]}$ , by replacing each cluster in the tree $\text{[math]}$ by an edge. If we use a strategy P for partitioning $\text{[math]}$ then the CPT would be CPT_P $\text{[math]}$ . This is done recursively till only one edge remains.

We would notice that all the nodes of the corresponding Top Tree $\text{[math]}$ are uniquely mapped into the edges of this multilevel partition. There may be some edges in the multilevel partition that do not correspond to any node in the Top tree, these are the edges which represent only a single child in the level below it, i.e a simple cluster. Only the edges that correspond to composite clusters correspond to nodes in the Top Tree $\text{[math]}$ .

A Partitioning Strategy is important while we partition the Tree $\text{[math]}$ into clusters. Only a careful strategy ensures that we end up in an $\text{[math]}$ height Multilevel Partition ( and therefore the Top Tree).

The number of edges in subsequent levels should decrease by a constant factor.
If a lower level is changed by an update then we should be able to update the one immediately above it using at most a constant number of insertions and deletions.

The above partitioning strategy ensures the maintenance of the Top Tree in $\text{[math]}$ time.

References

Donald Knuth. The Art of Computer Programming: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Section 2.3: Trees, pp.308–423.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Section 10.4: Representing rooted trees, pp.214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp.253–320.

External links

data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data type.
..... Click the link for more information.

tree is a widely-used data structure that emulates a tree structure with a set of linked nodes.

Nodes

A node may contain a value or a condition or represents a separate data structure or a tree of its own.
..... Click the link for more information.

In computer science, divide and conquer (D&C) is an important algorithm design paradigm. It works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly.
..... Click the link for more information.

tree is a widely-used data structure that emulates a tree structure with a set of linked nodes.

Nodes

A node may contain a value or a condition or represents a separate data structure or a tree of its own.
..... Click the link for more information.

In computer science, a binary tree is a tree data structure in which each node has at most two children. Typically the child nodes are called left and right. One common use of binary trees is binary search trees; another is binary heaps.
..... Click the link for more information.

Donald Ervin Knuth

Photographed by Jacob Appelbaum, 25 October 2005
Born January 10 1938
..... Click the link for more information.

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. He is a Full Professor of computer science at Dartmouth College.
..... Click the link for more information.

Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language.
..... Click the link for more information.

..... Click the link for more information.

Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in
..... Click the link for more information.

Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It is used as the textbook for algorithms courses at many universities.
..... Click the link for more information.

This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.

Herod_Archelaus

iPedia Free Information Center

Top Trees

Information about Top Trees

Glossary

Boundary Node

Boundary Vertex

External Boundary Vertices

Cluster

Path Cluster

Point Cluster

Leaf Cluster

Edge Cluster

Leaf Edge Cluster

Path Edge Cluster

Internal Node

Cluster Path

Mergeable Clusters

Introduction

Dynamic Operations

Internal Operations

Interesting Results and Applications

Implementation

Using Multilevel Partitioning

References

External links

Nodes

Nodes