[prev] 22 [next]

Rebalancing Trees (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   ⇒ Solution: real balanced trees  (later)