CS301 Lecture No. 20

CS301 Lecture No. 20
We will continue the discussion on AVL tree in this lecture. Before going ahead, it
will be better to recap things talked about in the previous lecture. We built a balanced
search tree (BST) with sorted data. The numbers put in that tree were in increasing
sorted order. The tree built in this way was like a linked list. It was witnessed that the
use of the tree data structure can help make the process of searches faster. We have
seen that in linked list or array, the searches are very time consuming. A loop is
executed from start of the list up to the end. Due to this fact, we started using tree data
structure. It was evident that in case, both the left and right sub-trees of a tree are
almost equal, a tree of n nodes will have log2 n levels. If we want to search an item in
this tree, the required result can be achieved, whether the item is found or not, at the
maximum in the log n comparisons. Suppose we have 100,000 items (number or
names) and have built a balanced search tree of these items. In 20 (i.e. log 100000)
comparisons, it will be possible to tell whether an item is there or not in these 100,000
items.