# Notes - ADS HT24, Splay trees

> Source: https://ollybritton.com/notes/uni/part-a/ht24/ads/notes/splay-trees/ · Updated: 2024-01-23 · Tags: uni, notes

- [Course - Algorithms and Data Structures HT24](https://ollybritton.com/notes/uni/part-a/ht24/ads/)
	- [Notes - ADS HT24, Amortized analysis](https://ollybritton.com/notes/uni/part-a/ht24/ads/notes/amortized-analysis/)
	- [Notes - ADS HT24, Red-black trees](https://ollybritton.com/notes/uni/part-a/ht24/ads/notes/red-black-trees/)

### Flashcards
Suppose:

- $S = \{x_1, x_2, \ldots, x_n\}$ is the set of values in a BST
- $p_i$ is the probability that item $x_i$ is accessed in a sequence of $m$ searches

@Define the statically optimal BST $T^\star$.::
$T^\star$ is the binary tree with minimum aggregate look-up cost.

Can you give the pseudocode for Splay($x$), which moves $x$ to the root of a BST through a sequence of rotations?::
```
SPLAY(x):
	while x is not the root:
		y = p[x]
		if y is the root
			rotate x and p[x]
		else:
			z = p[y]
	
			if x - y - z is aligned: (zig-zig)
				rotate y with z
				rotate x with y
			else x - y - z is not aligned: (zig-zag)
				rotate x with y
				rotate x with z
```

Suppose:

- We are splaying a node $x$ in a splay tree
- We are in the "zig-zag" case, i.e. if $y$ is $x$'s parent, and $z$ is y's parent, then $y < x < z$ (or the other way around)

Can you:

- Describe the sequence of rotations that are used to move $x$ closer to the root
- Highlight a mnemonic that makes remembering this easier
- Draw a picture representing these

::

- Rotate $x$ with $y$, and then $x$ with $z$
- "Zig-zag preserves kinked splays" (also $xyxz$ looks kind of zig-zaggy)

![Screenshot 2024-01-23 at 19.24.40.png](https://ollybritton.com/assets/attachments/img/Screenshot 2024-01-23 at 19.24.40.png)

Suppose:

- We are splaying a node $x$ in a splay tree
- We are in the "zig-zig" case, i.e. if $y$ is $x$'s parent, and $z$ is y's parent, then $x < y < z$ (or the other way around)

Can you:

- Describe the sequence of rotations that are used to move $x$ closer to the root
- Highlight a mnemonic that makes remembering this easier
- Draw a picture representing these

::

- Rotate $y$ with $z$, then rotate $x$ with $y$
- "Zig-zig preserves straight splays"

![Screenshot 2024-01-23 at 19.25.54.png](https://ollybritton.com/assets/attachments/img/Screenshot 2024-01-23 at 19.25.54.png)

Give the pseudocode for the implementation of Insert($x$) in a splay tree (this is quite short).::

```
INSERT(x):
	INSERT_BST(x) # insert in the normal BST way
	SPLAY(x)
```

What are the four high level steps in implementing Delete($x$) in a splay tree?::

- First Splay($x$)
- Remove $x$ from the root, this splits into two trees $T_{<x}$ and $T_{>x}$.
- Let $w = \mathrm{Max}(T_{<x})$, then Splay($T_{<x}$, w)
- Join $T_{<x}$ and $T_{>x}$ on $w$

Since red-black trees are balanced binary search trees, they have amortised lookup cost $O(\log n)$. In this case, why are splay trees useful? Define a metric and state a bound which makes their usefulness clear.::

They are not necessarily optimal for arbitrary access sequences, e.g. requesting a leaf over and over will have cost $O(\log n)$. Splay trees adapt to access sequences.

To measure this, we can compare them to statically optimal trees.

Suppose $S = \{x_1, \cdots, x_n\}$ is the set of values in a BST. Suppose that in a sequence of $m$ searches, value $x_i$ is accessed $mp_i$ times for $i = 1, \cdots, n$, where:

- $p_i$ is the frequency that item $i$ is accessed
- $p_1 + \cdots + p_n = 1$
- The look up cost of item $x_i$ is $1 + \mathrm{depth}(x_i)$.

Let $T^\star$ be the "statically optimal binary search tree", i.e. the BST with minimum aggregate lookup cost. Then
$$
\mathrm{cost}(T_\text{splay}) = O(\mathrm{cost}(T^\star))
$$

What is a statically optimal binary search tree $T^\star$?::

Suppose $S = \{x_1, \cdots, x_n\}$ is the set of values in a BST. Suppose that in a sequence of $m$ searches, value $x_i$ is accessed $mp_i$ times for $i = 1, \cdots, n$, where:

- $p_i$ is the frequency that item $i$ is accessed
- $p_1 + \cdots + p_n = 1$
- The look up cost of item $x_i$ is $1 + \mathrm{depth}(x_i)$.

Then for an arbitrary binary search tree $T$ over these items,
$$
\mathrm{cost}(T) = m \sum_{i=1}^n p_i(1 + d_i)
$$

Let $T^\star$ be the BST with minimum aggregate lookup cost. Then
$$
\mathrm{cost}(T_\text{splay}) = O(\mathrm{cost}(T^\star))
$$

Suppose:

- $S = \{x_1, \cdots, x_n\}$ is the set of values in a BST.
- In a sequence of $m$ searches, value $x_i$ is accessed $mp_i$ times for $i = 1, \cdots, n$, where:
	- $p_i$ is the frequency that item $i$ is accessed
	- $p_1 + \cdots + p_n = 1$
- The look up cost of item $x_i$ is $1 + \mathrm{depth}(x_i)$.

For any binary search tree $T$ for these items, what is $\mathrm{cost}(T)$?::

$$
\mathrm{cost}(T) = m\sum^n_{i = 1} p_i (1 + d_i)
$$

In the amortised analysis of splay trees, our overall goal is to show that the cost of a single splay operation (where cost is measured as the number of rotations) is bounded by
$$
O(\log n)
$$
To do this, we prove the "access lemma". Can you state this, and then quickly describe why this implies the result we want?::

Make the following definitions:

- $T$ is the tree under consideration
- $\mathrm{size}(x) = \text{number of nodes in }x\text{'s subtree}$
- $\mathrm{rank}(x) = \log \mathrm{size}(x)$ (or $r(x)$ for shorthand)
- $\Phi(T) = \sum_{x \in T} \mathrm{rank}(x)$ (the potential function used in this context)

Then the access lemma says that if $\mathrm{rank}(x)$ and $\mathrm{rank}'(x)$ are the ranks of $x$ before and after the splay operation, then
$$
\text{total charge of splay} \le 1 + 3(r'(x) - r(x))
$$
This implies the result we want because the maximum rank is $\log n$, and the minimum rank is $0$, so
$$
\begin{aligned}
\text{total cost of splay} &= \text{total charge of splay} \\
&= O(\log n)
\end{aligned}
$$

In the amortised analysis of splay trees, our overall goal is to show that the cost of a single splay operation (where cost is measured as the number of rotations) is bounded by
$$
O(\log n)
$$
To do this, we prove the "access lemma", which states that if we have the definition

- $T$ is the tree under consideration
- $\mathrm{size}(x) = \text{number of nodes in }x\text{'s subtree}$
- $\mathrm{rank}(x) = \log \mathrm{size}(x)$ (or $r(x)$ for shorthand)
- $\Phi(T) = \sum_{x \in T} \mathrm{rank}(x)$ (the potential function used in this context)
- $\mathrm{rank}(x)$ and $\mathrm{rank}'(x)$ are the ranks of $x$ before and after the splay operation (note that $r'(x)$ is the rank at the root)

Then
$$
\text{total charge of splay} \le 1 + 3(r'(x) - r(x))
$$
This implies the result we want because the maximum rank is $\log n$, and the minimum rank is $0$, so
$$
\begin{aligned}
\text{total cost of splay} &\le \text{total charge of splay} \\
&= O(\log n)
\end{aligned}
$$
Quickly prove this.::

In all cases, let $x$ be the node under consideration, $y$ its parent, and $z$ its grandparent. We want to show that the charge $\hat c_i := c_i + \Delta \Phi$ at each elementary splay step is bounded by an appropriate factor, so that eventually we see that
$$
\begin{aligned}
\text{total cost of splay} &\le \text{total charge of splay} \\
&= \sum \hat c_i \\
&\le 1 + 3(r'(x) - r(x)) \\
\end{aligned}
$$
There are 3 types of elementary splay operation: a rotation at the root, a zig-zig, or a zig-zag.

**Charge of rotation at the root**:
$$
\begin{aligned}
\hat c_i &= c_i + \Delta \Phi \\
&= 1 + \Delta \Phi \\
&= 1 + r'(x) + r'(y) - r(x) - r(y) \\
&= 1 + r'(y) - r(x) \\
&\le 1 + r'(x) - r(x) \\
\end{aligned}
$$
Some explanatory notes:

- The $1$ at the beginning comes from the fact that we perform just one rotation, so the actual cost $c_i$ is $1$
- In the last equality, we use $r(y) = r'(x)$
- In the inequality, we use the fact that $r'(x) \ge r'(y)$, this follows from the fact $x$ is the parent of $y$

**Charge of zig-zig step**:
$$
\begin{aligned}
\hat c_i &= 2 + r'(x) + r'(y) + r'(z) - r(x) - r(y) - r(z) \\
&= 2 + r'(y) + r'(z) - r(y) - r(x) \\
&\le 2 + r'(z) + r'(x) - r(x) - r(x) \\
&= 2 + r'(z) + r'(x) - 2r(x) \\
&\le 2 + 3(r'(x) - r(x)) - 2 \\
&= 3(r'(x) - r(x))
\end{aligned}
$$
Notes:

- Now we have $2$ since we have $2$ rotations
- In the second equality, we use $r'(x) = r(z)$
- In the first inequality, we use $r(x)<r(y)$ and $r'(x)>r'(p)$
- In the second inequality, we use the convexity of $\log$ (?? don't really understand this)

**Charge of zig-zag step**:
$$
\begin{aligned}
\hat c_i &= 2 + r'(x) + r'(y) + r'(z) - r(x) - r(y) - r(z) \\
&\le 2 + r'(y) + r'(z) - r(x) - r(y) \\
&\le 2 + 3(r'(x) - r(x)) - 2 \\
&= 3(r'(x) - r(x))
\end{aligned}
$$
Notes:

- In the first inequality we use the fact that $r'(x)=r(z)$ and $r(x)<r(y)$.
- In the second inequality we again use the convexity of $\log$.

**Overall**: Now we need to work out the total charge for the splay operation, which was given above:
$$
\begin{aligned}
\text{total cost of splay} &\le \text{total charge of splay} \\
&= \sum \hat c_i \\
&\le 1 + 3(r'(x) - r(x)) \\
\end{aligned}
$$
where the intermediate terms in the sum cancel.

In the amortised analysis of splay trees, our overall goal is to show that the cost of a single splay operation (where cost is measured as the number of rotations) is bounded by
$$
O(\log n)
$$
To do this, we prove the "access lemma", which states that if we have the definition

- $T$ is the tree under consideration
- $\mathrm{size}(x) = \text{number of nodes in }x\text{'s subtree}$
- $\mathrm{rank}(x) = \log \mathrm{size}(x)$ (or $r(x)$ for shorthand)
- $\Phi(T) = \sum_{x \in T} \mathrm{rank}(x)$ (the potential function used in this context)
- $\mathrm{rank}(x)$ and $\mathrm{rank}'(x)$ are the ranks of $x$ before and after the splay operation (note that $r'(x)$ is the rank at the root)

Then
$$
\text{total charge of splay} \le 1 + 3(r'(x) - r(x))
$$
This implies the result we want because the maximum rank is $\log n$, and the minimum rank is $0$, so
$$
\begin{aligned}
\text{total cost of splay} &\le \text{total charge of splay} \\
&= O(\log n)
\end{aligned}
$$

This result can actually be strengthened to something called the "general access lemma" or "weighted access lemma".

- How is this different?
- How is the normal access lemma a special case of this?
- What's the high-level strategy for proving this?

::

We introduce arbitrary "weights" $w_1, \cdots, w_n > 0$ and define

- $\mathrm{size}(x) = \sum_{x_i \in T_x} w_i$
- $W = w_1 + \cdots + w_n$

Then
$$
\text{total charge of splay} \le 1 + 3(\log W - \log w_x)
$$

The standard access lemma is the case where $w_i = 1$ for all $i$.

The high level strategy for proving this is that we can use an identical proof to the standard access lemma.

Suppose:

- $S = \{x_1, \cdots, x_n\}$ is the set of values in a BST.
- In a sequence of $m$ searches, value $x_i$ is accessed $mp_i$ times for $i = 1, \cdots, n$, where:
	- $p_i$ is the frequency that item $i$ is accessed
	- $p_1 + \cdots + p_n = 1$
- The look up cost of item $x_i$ is $1 + \mathrm{depth}(x_i)$.
- Every item is accessed at least once.

Let $T_\text{splay}$ be the splay tree for this data. Can you:

- Give an expression for $\mathrm{cost}(T_\text{splay})$?
- Quickly prove this, using the general access lemma.

For reference, the general access lemma states that:
$$
\text{total charge of splay} \le 1 + 3(\log W - \log w_x)
$$
For arbitrary "weights" $w_1, \cdots, w_n > 0$ and

- $\mathrm{size}(x) = \sum_{x_i \in T_x} w_i$
- $\mathrm{rank}(x) = \log \mathrm{size}(x)$
- $W = w_1 + \cdots + w_n$

::

$$
\begin{aligned}
\mathrm{cost}(T) &= O\Bigg(m\Big(1 - \sum_{i = 1}^n p_i \log p_i\Big)\Bigg) \\
&= O(m(1 + H))
\end{aligned}
$$
where
$$
H := - \sum_{i = 1}^n p_i \log p_i
$$

To prove this, apply the general access lemma with $w_i = p_i$. Then
$$
\begin{aligned}
\text{total charge for item }i &\le m p_i (1 + 3(\log(1) - \log p_i)) \\
&= m p_i (1 - 3\log p_i)
\end{aligned}
$$
Summing over $i$ gives the desired bound.

Suppose:

- $S = \{x_1, \cdots, x_n\}$ is the set of values in a BST.
- In a sequence of $m$ searches, value $x_i$ is accessed $mp_i$ times for $i = 1, \cdots, n$, where:
	- $p_i$ is the frequency that item $i$ is accessed
	- $p_1 + \cdots + p_n = 1$
- The look up cost of item $x_i$ is $1 + \mathrm{depth}(x_i)$
- Every item is accessed at least once

Let $T^\star$ be the statically optimal BST for these items, and let $T_\text{splay}$ be the splay tree for this data. Can you:

- Relate the cost of $T_\text{splay}$ and $T^\star$
- Quickly prove this, using the general access lemma.

::

$$
\mathrm{cost}(T_\text{splay}) = O(\mathrm{cost}(T^\star))
$$

To prove this, apply the general access lemma with $w_i = 3^{-d_i}$. Since the tree is binary
$$
\begin{aligned}
W &= \sum_{i = 1}^n w_i \\
&\le \sum^\infty_{j = 0} 2^j 3^{-j} \\
&= \sum^\infty_{j = 0} \left(\frac{2}{3}\right)^j \\
&= \frac{1}{1 - \frac 2 3} \\
&= 3
\end{aligned}
$$
Then
$$
\begin{aligned}
\text{total charge for item }i &\le 1 + 3(\log 3 - \log 3^{-d_i}) \\
&\le 8(1 + d_i)
\end{aligned}
$$
This is within a constant factor from the cost per access of item $i$ in $T^\star$.

### Proofs

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt