Top Trees

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 Re is defined for an "underlying tree" mathcal{T} and a pair of vertices partial{T} called as External Boundary Vertices

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 Re 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 mathcal{C} is denoted as partial{C}.With each cluster mathcal{C} the user may associate some meta information Info(mathcal{C}) , and give methods to maintain it under the various internal operations.

Path Cluster

If pi(mathcal{C}) contains at least one edge then mathcal{C} is called a "Path Cluster".

Point Cluster

See Leaf Cluster

Leaf Cluster

If pi(mathcal{C}) does not contain any edge i.e mathcal{C} has only one Boundary Vertex then mathcal{C} 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 mathcal{C} partial{C} is called an "Internal Node" of mathcal{C}.

Cluster Path

The path between the Boundary Vertices of mathcal{C} is called the "cluster path" of mathcal{C} and it is denoted by pi(mathcal{C}).

Mergeable Clusters

Two Clusters mathcal{A} and mathcal{B} are "Mergeable" if mathcal{A}capmathcal{B} is a singleton set (they have exactly one node in common) and mathcal{A}cupmathcal{B} 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 Re of logarithmic height in the number of nodes in the original tree mathcal{T}( i.e in mathcal{O}(log n) time) ; the Top Tree essentially represents the recursive subdivision of the original tree mathcal{T} into clusters".

In general the tree mathcal{T} may have weight on its edges.

There is a one to one correspondence with the edges of the original tree mathcal{T} and the leaf nodes of the Top Tree Re and each internal node of Re 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 mathcal{O}(n) time.mathcal{T}

Therefore the Top Tree Re over (mathcal{T},partial{T}) is a binary tree such that

* The nodes of Re are clusters of (mathcal{T}, partial{T} );
* The leaves of Re are the edges of mathcal{T};
* Sibling clusters are neighbours in the sense that they intersect in a single vertex, and then their parent cluster is their union.
* Root of Re if the tree mathcal{T} 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 v and w are nodes in different trees mathcal{T}1 and mathcal{T}2. It returns a single top tree representing RevcapRewcap{(v,w)}

*Cut(v, w): Removes the Edge {(v,w)} from a tree mathcal{T} with Top Tree Re, thereby turning it into two trees mathcal{T}v and mathcal{T}w and returning two Top Trees Rev and Rew.

Expose(v, w): Is called as a subroutine for implementing most of the path related queries on a Top Tree. It makes v and w 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 mathcal{O}(log n) Internal Operations, the sequence of which is computed in further mathcal{O}(log n) time.

*Merge(mathcal{A},mathcal{B}): Here mathcal{A} and mathcal{B} are "Mergeable Clusters", it reutrns mathcal{C} as the parent cluster of mathcal{A} and mathcal{B} and with boundary vertices as the boundary vertices of mathcal{A}cupmathcal{B}. Updates to Info(mathcal{C}) are carried out accordingly.

*Split(mathcal{C}):: Here mathcal{C} is mathcal{A}cupmathcal{B}. This deletes the cluster mathcal{C} from Re methods are then called to update Info(mathcal{A}) and Info(mathcal{B}).

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

*Create(v,w): Creates a cluster mathcal{C} for the edge (v,w). Sets partial{C} = partial(v,w). Methods are then called to compute Info(mathcal{C}).

*Eradicate(mathcal{C}): mathcal{C} is the edge cluster (v,w). It deletes the cluster mathcal{C} from the top tree. The Info(mathcal{C}) 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 mathcal{O}(log n) 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(mathcal{C}) is initialsed as -infty. 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 v and w then we do mathcal{C}= Expose(v,w), and report max_wt(mathcal{C}).

*( [SLEATOR AND TARJAN 1983] ). In the scenario of the above application we can also add a common weight x to all edges on a given path v · · ·w in mathcal{O}(log n) time.
**Proof outline: We introduce a weight called extra(mathcal{C}) to be added to all the edges in pi(mathcal{C}). Which is maintained appropriately ; split(mathcal{C}) requires that, for each path child mathcal{A} of mathcal{C}, we set max_wt(A) := max_wt(mathcal{A}) + extra(mathcal{C}) and extra(mathcal{A}) := extra(mathcal{A}) + extra(mathcal{C}). For mathcal{C} := join(mathcal{A}, mathcal{B}), we set max_wt(mathcal{C}) := max {max_wt(mathcal{A}), max_wt(mathcal{B})} and extra(mathcal{C}) := 0. Finally, to find the maximum weight on the path v · · ·w, we set mathcal{C} := Expose(v,w) and return max_wt(mathcal{C}).

*( [GOLDBERG ET AL. 1991] ). We can ask for the maximum weight in the underlying tree containing a given vertex v in mathcal{O}(log n) 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 v and w can be found in mathcal{O}(log n) time as length(Expose(v,w)).
**Proof outline:We will maintain the length length(mathcal{C}) of the cluster path. The length is maintained as the maximum weight except that, if mathcal{C} is created by a join(Merge), length(mathcal{C}) is the sum of lengths stored with its path children.

*Queries regarding diameter of a tree and its subsequent maintenance takes mathcal{O}(log n) time.

*The Center and Median can me maintained under Link(Merge) and Cut(Split) operations in mathcal{O}(log n) 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 mathcal{T} can be represented by a Cluster Partition Tree CPT(mathcal{T}), by replacing each cluster in the tree mathcal{T} by an edge. If we use a strategy P for partitioning mathcal{T} then the CPT would be CPTPmathcal{T}. This is done recursively till only one edge remains.

We would notice that all the nodes of the corresponding Top Tree Re 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 Re.

A Partitioning Strategy is important while we partition the Tree mathcal{T} into clusters. Only a careful strategy ensures that we end up in an mathcal{O}(log n) 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 mathcal{O}(log n) time.

References

* Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup, "Maintaining information in fully dynamic trees with top trees", ACM Transactions on Algorithms (TALG), Vol. 1 (2005), 243–264, [http://dx.doi.org/10.1145/1103963.1103966 doi:10.1145/1103963.1103966]
* 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

* [http://arxiv.org/abs/cs.DS/0310065 Maintaining Information in Fully Dynamic Trees with Top Trees. Alstrup et al]

* [http://www.cs.princeton.edu/~rwerneck/docs/TW05.htm Self Adjusting Top Trees. Tarjan and Werneck]

* [http://portal.acm.org/citation.cfm?id=1070547&dl=&coll=&CFID=15151515&CFTOKEN=6184618 Self-Adjusting Top Trees. Tarjan and Werneck, Proc. 16th SoDA, 2005]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Top-down parsing — is a strategy of analyzing unknown data relationships by hypothesizing general parse tree structures and then considering whether the known fundamental structures are compatible with the hypothesis. It occurs in the analysis of both natural… …   Wikipedia

  • Top-Down Induction of Decision Trees — oder kurz TDIDT ist ein nicht inkrementelles Lernverfahren im Forschungsbereich des maschinellen Lernens, das auf der Verwendung von Entscheidungsbäumen basiert. Als Ausgangspunkt dient eine Lernmenge L von Beispielen und eine Menge T der… …   Deutsch Wikipedia

  • Top-down and bottom-up design — Top down and bottom up are strategies of information processing and knowledge ordering, mostly involving software, but also other humanistic and scientific theories (see systemics). In practice, they can be seen as a style of thinking and… …   Wikipedia

  • Top — Top, v. t. 1. To cover on the top; to tip; to cap; chiefly used in the past participle. [1913 Webster] Like moving mountains topped with snow. Waller. [1913 Webster] A mount Of alabaster, topped with golden spires. Milton. [1913 Webster] 2. To… …   The Collaborative International Dictionary of English

  • Top Cottage — Infobox nrhp name = Top Cottage nrhp type = nhl caption = location = Hyde Park, NY nearest city = Poughkeepsie lat degrees =41 | lat minutes =45 | lat seconds =54 | lat direction = N long degrees = 73 | long minutes = 53 | long seconds = 19 |… …   Wikipedia

  • top — top1 W2S1 [tɔp US ta:p] n ▬▬▬▬▬▬▬ 1¦(highest part)¦ 2¦(upper surface)¦ 3¦(best position)¦ 4¦(cover)¦ 5¦(clothes)¦ 6 be (at the) top of the list/agenda 7 on top 8 on top of something 9 one on top of the other …   Dictionary of contemporary English

  • top — top1 [ tap ] noun *** ▸ 1 highest place/part ▸ 2 highest/best position ▸ 3 container lid/cover ▸ 4 piece of clothing ▸ 5 farthest part ▸ 6 toy that spins ▸ 7 fruit/vegetable leaves ▸ 8 beginning ▸ + PHRASES 1. ) count usually singular the highest …   Usage of the words and phrases in modern English

  • top — I UK [tɒp] / US [tɑp] noun Word forms top : singular top plural tops *** 1) a) [countable, usually singular] the highest place, point, part, or surface of something We could see mountain tops in the distance. at the top of something: I left my… …   English dictionary

  • top — 1. n., adj., & v. n. 1 the highest point or part (the top of the house). 2 a the highest rank or place (at the top of the school). b a person occupying this (was top in maths). c the upper end or head (the top of the table). 3 the upper surface… …   Useful english dictionary

  • Top Ground Gear Force — Infobox television show name = Top Ground Gear Force caption = format = Motoring Gardening picture format = 720x576 runtime = 45 minutes presenter = Jeremy Clarkson Richard Hammond James May country = UK network = BBC Two first aired = March 14,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”