Splay Trees
A kind of "self-balancing" tree …
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:
- by performing double-rotations also when searching
The idea: provides similar effect to periodic rebalance.
⇒ improves balance but makes search more expensive
| ![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}