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?
killerqb 0 Newbie Poster
Tom Gunn 1,164 Practically a Master Poster
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 0 Newbie Poster
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].
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.