Page 243 - DCAP407_DATA_STRUCTURE

Data Structure

Figure 13.1 shows a binary search tree where characters are stored in the nodes.

Figure 13.1: A Binary Search Tree

Binary search trees provide an efficient way to search through an ordered collection of objects. Consider
searching an ordered list. The search must proceed successively from one end of the list to the other. On
an average, n/2 nodes must be compared for an ordered list that contains n nodes. In the worst case, all
n nodes need to be compared. For a large collection of objects, this is very expensive.
Binary search tree enables searching quickly through the nodes. The longest path to search is equal to
the height of the tree. Thus, the efficiency of a binary search tree depends on the height of the tree. For a
tree with n nodes, the smallest possible height is log n and that is the number of comparisons that are
needed on an average to search the tree. A tree must be balanced to obtain the smallest height, i.e., both
the left and right sub-trees must have the same number of nodes.

Did you know? The trees which are unbalanced are called degenerate trees. For a degenerate tree with
n nodes, an average of n/2 comparisons is needed, with a worst case of n comparisons.
Thus, binary search trees are node based data structures used in many system programming
applications for managing dynamic sets. Another example for a binary search tree is given in Figure
13.2. As discussed, all the elements in the left sub-tree are lesser than the root node and the elements in
the right sub-tree are greater than the root node.

Figure 13.2: Example for Binary Search Tree

In the binary search tree represented in figure 13.2, 10 is the root node and all the elements in the left
sub-tree are lesser than 10 and the elements in the right sub-tree are greater than 10. Every node in the
tree satisfies this condition for the existing left and right sub-trees.

236 LOVELY PROFESSIONAL UNIVERSITY