AVL Tree

AVL Tree is:
• A Binary Search Tree, • in which the heights of the left and right subtrees of the root differ by at most 1, and

• the left and right subtrees are again AVL trees.

The name comes from the discoverers of this method, G.M.Adel'son-Vel'skii and E.M.Landis.

The method dates from 1962.

.Balance factor
Balance factor:
• left_higher: HL = HR + 1

• equal_height: • right_higher: