1. Splay Trees and the BST Model

Note: the auto-generated transcript renders "splay" as "spllay"/"display" and "Sleator & Tarjan" as "Slater and Targen". Correct spellings are used below.

What the data structure solves

• Splay trees are due to Sleator and Tarjan, dated to 1985 in the lecture 0:00, 0:36.
• They are a comparison-based solution to the dictionary problem, supporting 0:36, 1:35:
  • insert(k, v) — insert an item with key k and value v
  • find(k) — return the value associated with k
  • delete(k) — remove the item with key k
• Non-comparison-based alternative for the same problem: hash tables. The comparison-based version buys you extra operations such as predecessor 2:22.
• Practical relevance: splay trees won the Paris Kanellakis Theory and Practice Award in 1999, cited for "one of the most widely used data structures invented in the last 20 years" 2:22, 2:52.

The BST model

• A splay tree is a binary search tree; the difference is that after every operation it rebalances itself ("self-adjusting") 3:13, 3:43.
• The BST model defines what an algorithm is allowed to do 4:17, 4:52, 28:42:
  1. At the start of each operation, a single pointer sits at the root.
  2. Each step costs 1 and may be one of: follow a child pointer, follow the parent pointer, or rotate the node currently pointed at.
  3. For every access request, the pointer must reach the requested node.

Rotation

• rotate(x) makes x the parent of its own parent y, with subtrees redistributed to preserve BST order 5:23, 5:56, 6:30.
• The symmetric picture applies when x is the right child of y; the rest of the tree is untouched 6:30.

graph TD
    subgraph After["after rotate(x)"]
        X2["x"] --> A2["A"]
        X2 --> Y2["y"]
        Y2 --> B2["B"]
        Y2 --> C2["C"]
    end
    subgraph Before["before"]
        Y1["y"] --> X1["x"]
        Y1 --> C1["C"]
        X1 --> A1["A"]
        X1 --> B1["B"]
    end

The three operations

Operation	Implementation	Timestamp
find(x)	Search down as in any BST, then splay x so it becomes the new root	7:08, 7:54
insert(x)	Insert as in any BST, then splay x	8:19
delete(x)	Splay x to the root, remove it; if x had two children, splay the largest element of the left subtree and make it the new root	8:19, 9:08, 9:55

• splay is a subroutine that performs rotations to bring x to the root — but it is deliberately not "rotate x until it is the root"; it is "slightly more involved" 7:54.
• Baseline expectation: red-black / AVL trees already give O(log n) per operation; splay trees match that amortized, and additionally satisfy a family of stronger properties 10:35.