AVL tree
The AVL tree, named after its inventors Georgy Adelson-Velsky and Evgenii Landis, is a type of self-balancing binary search tree. The tree re-organises itself after every insert and delete so that the tree height is approximately \log n nodes high, allowing search in O(\log n) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee O(\log n) search.