An Amortized Analysis of Insertions into AVL-Trees
Kurt Mehlhorn, Athanasios Tsakalidis · SIAM Journal on Computing · 1986
We analyse the amortized behavior of AVL-trees under sequences of insertions. We show that the total rebalancing cost (=balance changes) for a sequence of n arbitrary insertions is at most $2.618n$. For random insertions the bound is improved to $2.26n$. We also show that the probability that t or more balance changes are required decreases exponentially with t.