Page 160 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 6: Binary Search Tree and AVL Trees

Applications of AVL Trees Notes

AVL trees are applied in the following situations:
1. There are few insertion and deletion operations

2. Short search time is needed
3. Input data is sorted or nearly sorted
AVL tree structures can be used in situations which require fast searching. But, the large cost of
rebalancing may limit the usefulness.
Consider the following:
1. A classic problem in computer science is how to store information dynamically so as to
allow for quick look up. This searching problem arises often in dictionaries, telephone
directory, symbol tables for compilers and while storing business records etc. The records
are stored in a balanced binary tree, based on the keys (alphabetical or numerical) order.
The balanced nature of the tree limits its height to O (log n), where n is the number of
inserted records.

2. AVL trees are very fast on searches and replacements. But, have a moderately high cost
for addition and deletion. If application does a lot more searches and replacements than
it does addition and deletions, the balanced (AVL) binary tree is a good choice for a data
structure.
3. AVL tree also has applications in fi le systems.

6.7 Summary

z Binary trees provide an excellent solution to this problem. By making the entries of an
ordered list into the nodes of a binary tree, we shall find that we can search for a target key

in O(log n) steps, just as with binary search, and we shall obtain algorithms for inserting
and deleting entries also in time O(log n)
z When we studied binary search, we drew comparison trees showing the progress of binary
search by moving either left (if the target key is smaller than the one in the current node of
the tree) or right (if the target key is larger).
z We can regard binary search trees as a new abstract data type with its own defi nition and
its own methods;

z Since binary search trees are special kinds of binary trees, we may consider their methods
as special kinds of binary tree methods;
z Since the entries in binary search trees contain keys, and since they are applied for
information retrieval in the same way as ordered lists, we may study binary search trees as
a new implementation of the abstract data type ordered list.

6.8 Keywords

Binary Search Tree: A binary search tree is a binary tree which may be empty, and every node
contains an identifi er.
Searching: Searching for the key in the given binary search tree, start with the root node and
compare the key with the data value of the root node.

LOVELY PROFESSIONAL UNIVERSITY 155