Rebalancing Trees (cont)
Even the most efficient implementation of rebalancing requires (in the worst case) to visit every node ⇒ O(N)
Cost means not feasible to rebalance after each insertion.
When to rebalance? … Some possibilities:
- after every k insertions
- whenever "imbalance" exceeds threshold
Either way, we tolerate worse search performance for periods of time.
Does it solve the problem? … Not completely ⇒ Solution: real balanced trees (later)
| ![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}