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.