Time Complexity AVL Tree

[killerqb]

I know an AVL Tree guarantees a time of log(n), but what is the time cost of the actual re balancing of the tree and why is this ignored?

[Tom Gunn]

what is the time cost of the actual re balancing of the tree

It depends on how the algorithms are implemented, but ideally for insertion the cost of rebalancing is constant. Only one part of the tree will ever be out of balance and at most two rotations will bring it back into balance. For deletion there could be one rebalance step for each node along the search path, so the number of rebalances on deletion is O(log(n)).

why is this ignored?

Rebalancing is a constant time operation and time complexities remove constant values. Instead of saying that AVL deletion is O(log(n) + m) where m is the time a rebalance takes, the m is trimmed away as an unnecessary part and the result is simplified to O(log(n)).

[Herbert_3]

I reinterpret guarantee as worst case and actual as on average. So rebalancing of both, insert and delete, is logarithmic in the worst case. On average, insert is constant, even amortized constant. Delete is constant on average, although on every level up there may be a rotation. But the conditions that cause a rotation (i.e. balance factor becoming ±2) diminish all the way up by a factor of < q < 1 [indeed q<½]. So the probability is <1+q+q²+... = 1/(1-q) [indeed <2].