Named after inventors Adelson-Velskii and Landis, the **AVL tree** was concieved in 1962. It was the first dynamically balanced binary search tree to be proposed. Like a binary tree, **AVL trees** consist of parent nodes with no more than two child nodes. The tree re-sorts itself when a node finds itself the child of a node in a one branched subtree.

For example:

5 5
/ \ / \
3 7 2 7
/ -> / \
2 1 3
/
1

The 2 replaces the 5's lesser child and the 3 becomes the 2's right child (insert orphanage joke). Pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also take O(logn) time.