Splay Trees

Splay Trees are Binary Search Trees

• a splay tree is a binary search tree where a node is splayed after it is accessed (for a search or update)
  • deepest internal node accessed is splayed
  • splaying costs O(h), where h is height of the tree
    • which is still O(n) worst-case
      • O(h) rotations, each of which is O(1)
• BST Rules:
  • items stored only at internal nodes
  • keys stored at nodes in the left subtree of v are less than or equal to the key stored at v
  • keys stored at nodes in the right subtree of v are greater than or equal to the key stored at v
  • An inorder traversal will return the keys in order

Search

• Searching in a Splay Tree: Starts the Same as in a BST
• Search proceeds down the tree to found item or an external node.
• Example: Search for time with key 11.

Rotations

• Splay Trees do Rotations after Every Operation (Even Search)
• new operation: splay
  • splaying moves a node to the root using rotations
• right rotation
  • makes the left child x of a node y into y’s parent; y becomes the right child of x
    
• left rotation
  • makes the right child y of a node x into x’s parent; x becomes the left child of y

Splaying

• “x is a left-left grandchild” means x is a left child of its parent, which is itself a left child of its parent
• p is x’s parent; g is p’s parent

TODO: Other examples

• which nodes are splayed after each operation?

Amortized Analysis of Splay Trees

• Running time of each operation is proportional to time for splaying.
• Define rank(v) as the logarithm (base 2) of the number of nodes in subtree rooted at v.
• Costs: zig = $1, zig-zig = $2, zig-zag = $2.
• Thus, cost for playing a node at depth d = $d.
• Imagine that we store rank(v) cyber-dollars at each node v of the splay tree (just for the sake of analysis).
• Cost per zig
  • Doing a zig at x costs at most rank’(x) - rank(x):
    • cost = rank’(x) + rank’(y) - rank(y) - rank(x)
      • < rank’(x) - rank(x)
• Cost per zig-zig and zig-zag
  • Doing a zig-zig or zig-zag at x costs at most
    • 3(rank’(x) - rank(x)) - 2.
  • Proof: See Theorem 3.9, Page 192.
    
    
    
    
• Cost of Splaying
  • Cost of splaying a node x at depth d of a tree rooted at r:
    • at most 3(rank(r) - rank(x)) - d + 2:
    • Proof: Splaying x takes d/2 splaying substeps:
      
      

Performance of Splay Trees

• Recall: rank of a node is logarithm of its size.
• Thus, amortized cost of any splay operation is O(log n).
• In fact, the analysis goes through for any reasonable definition of rank(x).
• This implies that splay trees can actually adapt to perform searches on frequently requested items much faster than O(log n) in some cases. (See Theorems 3.10 and 3.11.)