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