Resolved open problem on performance of AVL trees in terms of rotations.n mixed insertions and deletions can cause ? ( n log ? n ) rotations.We show a class of AVL trees that allow such expensive operations.
['Mahdi Amani', 'Kevin A. Lai', 'Robert Endre Tarjan']
Amortized rotation cost in AVL trees