Friday, 24 November 2017

Binary Search Trees and AVL Trees in Data Structure

1. Binary search trees are an excellent data structure to implement associative arrays, maps, sets, and similar interfaces.
2. The main difficulty, as discussed in last lecture, is that they are efficient only when they are balanced.
3. Straightforward sequences of insertions can lead to highly unbalanced trees with poor asymptotic complexity and unacceptable practical efficiency.
4. The solution is to dynamically rebalance the search tree during insert or search operations.
5. We have to be careful not to destroy the ordering invariant of the tree while we rebalance.
6. Because of the importance of binary search trees, researchers have developed many different algorithms for keeping trees in balance, such as AVL trees, red/black trees, splay trees, or randomized binary search trees.
7. In this lecture we discuss AVL trees, which is a simple and efficient data structure to maintain balance.
8. It is named after its inventors, G.M. Adelson-Velskii and E.M. Landis, who described it in 1962.

Ordering Invariant.
1. At any node with key k in a binary search tree, all keys of the elements in the left subtree are strictly less than k, while all keys of the elements in the right subtree are strictly greater than k.
2. To describe AVL trees we need the concept of tree height, which we define as the maximal length of a path from the root to a leaf. So the empty tree has height 0, the tree with one node has height 1, a balanced tree with three nodes has height 2.
3. If we add one more node to this last tree is will have height 3. Alternatively, we can define it recursively by saying that the empty tree has height 0, and the height of any node is one greater than the maximal height of its two children.
3. AVL trees maintain a height invariant (At any node in the tree, the heights of the left and right sub-trees differs by at most.)

Mukesh Rajput

No comments:

Post a Comment

Mukesh Rajput