AVL Tree

A plain search tree fed sorted values becomes a straight line, and search degrades to O(n). An AVL tree watches its own balance and rotates itself level again. The default input here is sorted on purpose — so you can watch it refuse to become a list.