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

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.