[prev] 35 [next]

Splay Trees (cont)

Why take into account both child and grandchild?
  • moves accessed node to the root
  • moves every ancestor of accessed node roughly halfway to the root
⇒ better amortized cost than insert-at-root