Overview of Tree Data Structure

The tree is an abstract data structure which stores hierarchical data. For example, organisations have a hierarchical structure for employees. It is similar to the image given below.


Several sergeants have to report to their respective captain. Now captains report to colonel. This colonel takes order from the general and assigns them to sergeants. Each of these consists of several levels. The general is on level 0, Colonel A and Colonel V are on level 1, Captain A, B and C are on level 2 and so on. Another terminology is height of the tree. 

The height of a tree is longest path from the root node to any leaf node of the tree.

Height of leaf node n=Level of leaf n+1. 

Suppose we want to find the height of Private A.

Height of private A= Level of Private A+1

                               =4+1

                               =5

In terms of computer programming, the general would be the root node of the tree. Colonel A and Colonel B are children of general. These two colonels are referred to as siblings. Further, colonel B has three children captain A, B and C. Since Colonel A does not have any further nodes, it would be referred to as a leaf node.


Thus we can deduce that,

  1. The topmost node of the tree is the root node.
  2. Node A emerges from node B. Then we can say that A is the child of B and B is the parent node of A. Node B can have multiple sub-nodes.
  3. If node A does not have any children/sub-nodes then that node is called a leaf node.
  4. The line connecting nodes are called edges.
  5. The number of predecessors node A has is the degree of A.
  6. Level number of the root node is 0 and the level number of a child node=level number of parent node+1.
  7. Two nodes having the same parent nodes are sibling nodes.

Advantages of the tree data structure are:

  1. Can describe the relationship between data elements.
  2. Efficient insertion.

Disadvantages of the tree data structure are:

  1. Deletion of nodes other than leaf nodes is costly.
  2. More time and space complexity compared to array, linked list, stack and queue.


Applications of the tree data structure are:

  1. Implements hash table, sets and maps data structure.
  2. This data structure is used in compiler construction and database design.
  3. Can store simple values( Example: Number value) as well as complex value(Example:record).
  4. Retrieval and information storage in symbol tables. 
  5. A type of tree: Binary Tress has several applications of it's own.

Comments

Post a Comment

Popular posts from this blog

Overview of Three Dimensional Array

Image
A multidimensional array is an array consisting of more than 2 dimensions.  We can perceive three dimensions at most. To visual 3-dimensional array, let's take an example of a cube. Therefore, the array is cube[3][3][3]. For better understanding, represent a 3-D array as a combination of 2-D arrays.  Note: The two-dimensional array must have the same size. To conclude, a three dimensional array has arr[sub-array number][row][column]. Application of 3-D array: To represent real-world location co-ordinates. For storing spatial data such as MRI data. 3-D modelling.
Read more

Overview of Priority Queue

Image
  Consider a group of patients waiting outside the doctor's cabin for consultation. The functioning of the clinic is First In First Out basis like a queue . Suddenly, a new patient arrives with a condition which requires immediate treatment.  Then, the doctor would treat this patient first and then continue treating other patients like the previous order. In a priority queue, each data element has priority. So that crucial data does not get stuck. High priority elements are dequeue before low priority elements. If multiple elements have the same priority number, then the deletion is on a first come first serve basis. When  array implements a priority queue, an additional  2-D array is required to store the priority. When a  linked list implements a priority queue, the node stores the priority number. Applications of priority queue: Bandwidth management. Dijkstra Algorithm. Huffman Coding. Best First Search Algorithm. CPU Scheduling
Read more