[prev] [index] [next]

Splay Trees

Splay tree insertion modifies insertion-at-root method:
  • by considering parent-child-granchild (three level analysis)
  • by performing double-rotations based on p-c-g orientation
The idea: appropriate double-rotations improve tree balance.

Splay tree implementations also do rotation-in-search:

  • can provide similar effect to periodic rebalance
  • improves balance, but makes search more expensive