5.Avl

This section explains the concept, its importance, and when to use it.

BALANCED TREES

The running time of BST operations depends on the height of the binary search tree: we should keep the tree balanced in order to get the best performance

Most of the operations are the same as we have seen for binary search trees

Key Property: AVL tree requires the heights of left and right child of every node to differ at most +1 or -1 !!!

Rotations

Rotations case I

Rotations case II

Rotations case III

Rotations case IV

Rotation Cases: - Four types of unbalanced situations

Deletion: REMOVE

Deletion: It is basically the same as we have seen for simple binary search tree node deletion

Use Cases: - We can use this data structure to sort items

Deletion: Databases when deletions or insertions are not so frequent, but have to make a lot of look-ups