AVL Trees

Height balanced binary search trees: Height < 1.5logN

Search, Insertion, Deletion are guaranteed O(logN) provided height balance can be maintained in O(logN). It can!

Operations must preserve:

• heights of left and right subtrees are within 1.
• values in left subtree are smaller than root value.

  values in right subtree are bigger than root value.

Insertion:

• BST insertion
• check height-balance, and rebalance if necessary by changing the tree's shape.