Page 140 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 6: Binary Search Tree and AVL Trees

tnode *root; Notes
key item;
int n;
root = NULL;
printf(“Number of data values:”);
scanf(“%d”, &n);
while( n > 0)
{
printf(“Enter the data value”);
scanf(“%s”, item);
insert(root, item);
n = n-1;
}
printtree(root);
}

Task Discuss how will you delete a node with one child.

6.6 AVL Tree

An AVL tree is another balanced binary search tree. It takes its name from the initials of its
inventors – Adelson, Velskii and Landis. An AVL tree has the following properties:
1. The sub-trees of every node differ in height by at most one level.
2. Every sub-tree is an AVL tree.

h
h - 2
h - 1

Here, the height of the tree is h. Height of one subtree is h–1 while that of another subtree of the
same node is h–2, differing from each other by just 1. Therefore, it is an AVL tree.

Inserting a Node into AVL Tree

Inserting a node is somewhat complex and involves a number of cases. Implementations of AVL
tree insertion rely on adding an extra attribute – the balance factor – to each node. This factor
indicates whether the tree is left-heavy (the height of the left sub-tree is 1 greater than the right

LOVELY PROFESSIONAL UNIVERSITY 135