Trees:Introduction and Representation

By -
Introduction

The tree is a natural representation for hierarchical information. Thus, trees are used to represent genealogical information (e.g., family trees and evolutionary trees), organizational charts in large companies, the directory structure of a file system on a computer, parse trees in compilers and the structure of a knock-out sports tournament. The Dewey decimal notation, which is used to classify books in a library, is also a tree structure. In addition to these and other applications, the tree is used to design fast algorithms in computer science because of its efficiency relative to the simpler data structures discussed in Chapter 2. Operations that take linear time on these structures often take logarithmic time on an appropriately organized tree structure. For example, the average time complexity for a search on a key is linear on a linked list and logarithmic on a binary search tree. Many of the data structures discussed in succeeding chapters of this handbook are tree structures.

Several kinds of trees have been defined in the literature:

1. Free or unrooted tree: this is defined as a graph (a set of vertices and a set of edges that join pairs of vertices) such that there exists a unique path between any two vertices in the graph. The minimum spanning tree of a graph is a well-known example of a free tree. Graphs are discussed in Chapter 4.

2. Rooted tree: a finite set of one or more nodes such that

(a) There is a special node called the root.

(b) The remaining nodes are partitioned into n ≥ 0 disjoint sets T1, ..., Tn, where each of these sets is a tree. T1, ..., Tn are called the subtrees of the root.

If the order in which the subtrees are arranged is not important, then the tree is a rooted, unordered (or oriented) tree. If the order of the subtrees is important, the tree is rooted and ordered. Figure 3.1 depicts the relationship between the three types of trees. We will henceforth refer to the rooted, ordered tree simply as “tree”.

image

3. k-ary tree: a finite set of nodes that is either empty or consists of a root and the elements of k disjoint k-ary trees called the 1st, 2nd, ..., kth subtrees of the root. The binary tree is a k-ary tree with k = 2. Here, the first and second subtrees are respectively called the left and right subtrees of the root. Note that binary trees are not trees. One difference is that a binary tree can be empty, whereas a tree cannot. Second, the two trees shown in Figure 3.2 are different binary trees but would be different drawings of the same tree.

image

Figure 3.3 shows a tree with 11 nodes. The number of subtrees of a node is its degree. Nodes with degree 0 are called leaf nodes. Thus, node A has degree 3, nodes B, D, and I have degree 2, node E has degree 1, and nodes C, F , G, H, J , and K have degree 0 (and are leaves of the tree). The degree of a tree is the maximum of the degree of the nodes in the tree. The roots of the subtrees of a node X are its children. X is the parent of its children. Children of the same parent are siblings. In the example, B, C, and D are each other’s siblings and are all children of A. The ancestors of a node are all the nodes excluding itself along the path from the root to that node. The level of a node is defined by letting the root be at level zero. If a node is at level l, then its children are at level l + 1. The height of a tree is the maximum level of any node in the tree. The tree in the example has height 4. These terms are defined in the same way for binary trees. See [1–6] for more information on trees.

image

Tree Representation

List Representation

The tree of Figure 3.3 can be written as the generalized list (A (B (E (I (J, K)), F), C, D(G, H))). The information in the root node comes first followed by a list of subtrees of the root. This enables us to represent a tree in memory using generalized lists as discussed in Chapter 2.

Left Child-Right Sibling Representation

Figure 3.4(a) shows the node structure used in this representation. Each node has a pointer to its leftmost child (if any) and to the sibling on its immediate right (if any). The tree in Figure 3.3 is represented by the tree in Figure 3.4(b).

Binary Tree Representation

Observe that the left child-right sibling representation of a tree (Figure 3.4(b)) may be viewed as a binary tree by rotating it clockwise by 45 degrees. This gives the binary tree

image

representation shown in Figure 3.4(c). This representation can be extended to represent a forest, which is defined as an ordered set of trees. Here, the roots of the trees are viewed as siblings. Thus, a root’s right pointer points to the next tree root in the set. We have

LEMMA 3.1 There is a one-to-one correspondence between the set of forests and the set of binary trees.

Comments

Post a Comment

Popular posts from this blog

0/1 Knapsack Problem Memory function.

By -
Image
0 / 1 Knapsack Problem Memory function Definition: Given a set of n items of known weights w1,…,wn and values v1,…,vn and a knapsack of capacity W, the problem is to find the most valuable subset of the items that fit into the knapsack. Knapsack problem is an OPTIMIZATION PROBLEM Dynamic programming approach to solve knapsack problem Step 1: Identify the smaller sub-problems. If items are labeled 1..n, then a sub-problem would be to find an optimal solution for Sk = {items labeled 1, 2, .. k } Step 2: Recursively define the value of an optimal solution in terms of solutions to smaller problems. Initial conditions: S te p 3: Bottom up computation using iteration Question: Apply bottom-up dynamic programming algorithm to the following instance of the knapsack problem Capacity W= 5 Solution: Using dynamic programming approach, we have: What is the composition of the optimal subset? The composition of the optimal subset if found by tracing back the computations for the...
Read more

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

By -
Image
BSP Tree as a Hierarchy of Regions Another way to look at BSP Trees is to focus on the hierarchy of regions created by the recursive partitioning, instead of focusing on the hyperplanes themselves. This view helps us to see more easily how intersections are efficiently computed. The key idea is to think of a BSP Tree region as serving as a bounding volume: each node v corresponds to a convex volume that completely contains all the geometry represented by the sub tree rooted at v . Therefore, if some other geometric entity, such as a point, ray, object, etc., is found to not intersect the bounding volume, then no intersection computations need be performed with any geometry within that volume. Consider as an example a situation in which we are given some test point and we want to find which object if any this point lies in. Initially, we know only that the point lies somewhere space ( Figure 20.12). By comparing the location of the point with respect to the first partitioning hyper pl...
Read more

Drawing Trees:HV-Layout

By -
Image
HV-Layout An hv -layout of a binary tree is an upward (but not strictly upward) straight line orthogonal drawing with edges drawn as rightward horizontal or downward vertical segments. The ”hv” stands for horizontal-vertical. For any vertex v in a binary tree T we either have: 1. A child of v is either • aligned horizontally with v and to the right of v or • vertically aligned below v . 2. The smallest rectangles that cover the area of the subtrees of the children of v in the layout do not intersect. Figure 45.12 shows an example of a hv -layout A hv -layout is generated by applying a dived and conquer approach. The divide step constructs the hv -layout of the left and the right subtrees, while the conquer step either performs a ho rizontal or a ver t i c a l combination . Figure 45.13 shows the two types of com- bination. If the left subtree a node v is placed to the left in a horizontal combination and below in a vertical combination, the layout preserves ...
Read more