Exercise #7 (cont)
Analysis of rebalancing: visits 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.
| ![[prev]](icon/prev.gif){kind=icon}
![[index]](icon/up.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}