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
|