[prev] 87 [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

Analysis of splay tree performance:

  • assume that we "splay" for both insert and search
  • consider: m insert+search operations, n nodes
  • Theorem.  Total number of comparisons: average O((n+m)·log(n+m))
Gives good overall (amortized) cost.

  • insert cost not significantly different to insert-at-root
  • search cost increases, but …
    • improves balance on each search
    • moves frequently accessed nodes closer to root
But … still has worst-case search cost O(n)