Page 192 - DCAP407_DATA_STRUCTURE

Unit 10: Trees

In the figure 10.11, the node A is the root node. The nodes B and D belong to the left sub-tree and nodes
C, E, F and G belong to the right sub-tree.
10.2.2 Binary Search Tree

A binary search tree is a tree in which for a given node n, each node to the left is smaller than n and
each node to the right is larger than n. This applies recursively down the left and right sub-trees. Figure
10.12 shows a binary search tree.

Figure 10.12: Binary Search Tree

In figure 10.12, the nodes C, B, E and A belonging to left sub-tree are smaller than F and the nodes H, I,
and M belonging to right sub-tree are larger than F.
AVL Tree

An AVL tree is a binary search tree having a balance factor of every node as 0 or +1 or −1. The balance
factor of a node is defined as the difference between the heights of the node’s left and right sub-trees.
The height of an empty tree is −1.

The binary search tree in figure 10.13(i) is an AVL tree but the binary search tree in 10.13 (ii) is not an
AVL tree. The numbers above the nodes indicate the balance factors of the nodes.

Figure 10.13: (i) AVL Tree
(ii) Binary Search Tree that is not an AVL Tree

LOVELY PROFESSIONAL UNIVERSITY 185