Splay Trees
6.854 Notes #3

David Karger

Lecture 3: Splay Trees

1 Binary Search Trees

2 Splay Trees

Sleator and Tarjan, “Self Adjusting Binary Search Trees” JACM 32(3) 1985

Key design principle: Be lazy! That is, don’t work until you must.

Path shortening:

Re-balancing (via Rotations):

Key operation: Splaying a node \(x\):

Figures of rotations

Implementing \(Search(x)\) operation:

(Will talk about \(Insert(x)\) and \(Delete(x)\) later.)

3 Analysis

Our potential function: \(\Phi=\sum r(x)\).

Some intuition:

3.1 The Access Lemma

Key technical fact:

Access Lemma: Amortized time to splay a node \(x\) given root \(t\) is at most \[3(r(t)-r(x))+1 = O(\log(s(t)/s(x))).\] (Recall: Amortized cost of an operation \(=\) real cost \(+ \ \Delta \Phi\). )

Note: \(x\) is the root of the tree after the splay operation and the rank of the root is always the same \(\log W\), where \(W=\sum_x w_x\) is the total weight of the nodes.
\(\Rightarrow\) So, rank \(r'(x)\) after the splay is equal to \(r(t)\).
\(\Rightarrow\) \(r(t)-r(x)=r'(x)-r(x)\) – the amortized cost of a splay is within a constant of its change in rank.

One immediate consequence of Access Lemma:

Important detail: To make the above analysis work also for unsuccessful Search(x) operations, we need to splay the last node we visited in that search.

3.2 Proof of the Access Lemma

       r                r' 

       z                x
      / \              / \
     y   D            A   y
    / \       ====>      / \
   x   C                B   z
  / \                      / \   
 A   B                    C   D



Actual Math (requires more care):

3.3 Bounding Overall Change of Potential

Important Caveat: The Access Lemma bounds only the amortized cost of each operation.
\(\Rightarrow\) If there is a sequence of \(m\) operations, its total real cost is at most \[O(m \log n) - \left(\Phi_m - \Phi_0\right)=O(m \log n) + \Phi_0 - \Phi_m,\] where \(\Phi_m\) is the potential of our data structure at the end of processing the whole sequence and \(\Phi_0\) is its initial potential.
Key question: How large can \(\Phi_0-\Phi_m\) be?


Also: Note that potential of empty tree is \(0\).
\(\Rightarrow\) If we start with empty tree, no problem (but for that we need inserts...)

3.4 Applications of Access Lemma

By applying the above analysis with different weights we can derive a lot of interesting facts about performance of splay trees. (Key fact to keep in mind: the behavior of the splay tree is completely independent of our choice of the weights!)

4 Update Operations

We have two remaining operations we need to implement: \(Insert(x)\) and \(Delete(x)\). There are two ways to implement them:

  1. Insert/delete the item as in a standard BST and then just splay the inserted element/parent of deleted element.

  2. Alternatively, consider the following operations:

    Note: For most balanced trees such \(Split(x)/Join\) operations do not take only \(O(\log n)\) time!

  3. To implement \(Insert(x)\):

  4. To implement \(Delete(x)\):

5 Possible Heuristics