Amortized rotation cost in AVL trees

• Resolved open problem on performance of AVL trees in terms of rotations.
• n   mixed insertions and deletions can cause Θ(nlog⁡n)Θ(nlog⁡n) rotations.
• We show a class of AVL trees that allow such expensive operations.