Mumbai University > COMPS > Sem 3 > Data Structures

Marks: 5 M

Year: May 2014

The following are the applications of trees:-

• Parse Trees for hierarchical data

  Parse trees can be used to represent real-world constructions like sentences or mathematical expressions.

Here, a hierarchical structure of a simple sentence is shown. Representing a sentence as a tree allows one to work with individual parts of the sentence by using subtrees.

Here, the mathematical expression ((7+3)∗(5−2)) is represented with the help of a parse tree. The hierarchy of the tree helps one understand the order of evaluation for the whole expression. The need for parenthesis is removed.

Here, a tree is used to represent a file system.

• Data Structure

  Elements can be organized and stored for later use in the form of a tree. The time it takes to search an element in a tree is usually in between that of a linked list and an array. Since AVL trees are balanced, they guarantee a time complexity of $log_2(n)$.

• Sorting

  Trees such as Binary Search Trees, AVL Trees, B-Trees maintain order among the elements. Sorting is in-turn used for searching, finding the closest-pair, determining element uniqueness and frequency distribution, selection, etc.