Cost means not feasible to rebalance after each insertion.
When to rebalance? … Some possibilities:
Does it solve the problem? … Not completely ⇒ Solution: real balanced trees (later)