Top Trees - Data Structures

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 is defined for an underlying tree and a pair of vertices called as External Boundary Vertices

Top Trees

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 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 C is denoted as figure With each cluster the user may associate some meta information info (C) figure contains at least one edge then is called a Path Cluster.

Point Cluster

See Leaf Cluster

Leaf Cluster

If figure does not contain any edge i.e has only one Boundary Vertex then 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 Cluster with two Boundary Nodes are called Path Edge Cluster.

Internal Node

A node in Figure is called an Internal Node of C

Cluster Path

The path between the Boundary Vertices of C is called the cluster path of and it is denoted by figure

Mergeable Clusters

Two Clusters A and B are Mergeable if figure is a singleton set (they have exactly one node in common) and figure 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 figure of logarithmic height in the number of nodes in the original tree ( i.e in Figure time) ; the Top Tree essentially represents the recursive subdivision of the original tree into clusters. In general the tree may have weight on its edges. There is a one to one correspondence with the edges of the original tree and the leaf nodes of the Top Tree and each internal node of Figure 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 figure time.T Therefore the Top Tree ℜ over (Τ,Τ∂) is a binary tree such that

  • The nodes ofℜare clusters of (Τ,Τ∂)
  • The leaves of ℜ are the edges of Τ
  • Sibling clusters are neighbours in the sense that they intersect in a single vertex, and then their parent cluster is their union.
  • Root of ℜ if the tree Τ 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.

All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Data Structures Topics