AVL Trees

• Don't become degenerate

• Always efficient searching

• Close to the theoretical maximum

• Rotations can be expensive

• Frequent insertions / deletions

• Other optimisations for in-order iterations