[prev] [index] [next]

Splay Trees (cont)

Gives good overall (amortized) cost:
  • splay has higher insert cost because of rotations
  • but (potentially) rotations improve balance
  • splay has (potentially) higher search cost (rotations)
  • but overall search cost is lower (move after search)
    (using assumption that recently searched keys are likely to be searched again)
Need empirical analysis to to determine how much better.

But ... still has worst case search cost O(N)