Amortized Rotation Cost in AVL Trees

Mahdi Amani, Kevin A. Lai, Robert E. Tarjan

An AVL tree is the original type of balanced binary search tree. An insertion in an $n$-node AVL tree takes at most two rotations, but a deletion in an $n$-node AVL tree can take $…