0

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?

2
Contributors
1
Reply
4
Views
7 Years
Discussion Span
Last Post by Tom Gunn
1

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)).

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.