ads note 9.15

Notes on height balance, splaying, and why a costly individual operation can still be inexpensive over a sequence.

Background

Throughout these notes, $\operatorname{rotate}(X)$ means rotating $X$ with its parent so that $X$ moves up one level. The rotation preserves the binary search tree’s in-order sequence.

AVL Trees

An empty tree is height-balanced (HB). A nonempty tree $T$ is height-balanced if and only if both subtrees $T_L$ and $T_R$ are height-balanced and their heights differ by at most one:

The balance factor of a node is

An AVL tree is a binary search tree in which every node satisfies

The four imbalance cases are LL, RR, LR, and RL. LL and RR require a single rotation; LR and RL require a double rotation.

After an insertion, rebalancing the lowest unbalanced ancestor with one single or double rotation restores the tree’s balance. After a deletion, rebalancing may need to continue toward the root.

Splay Trees

When a search finds a node $X$, a splay tree moves it to the root. Let $P$ be its parent and $G$ its grandparent, when they exist.

There are three cases. The diagrams below omit the attached subtrees; the mirrored cases work symmetrically.

Zig

$P$ is the root, so $X$ has no grandparent.

Perform $\operatorname{rotate}(X)$. Now $X$ is the root, and splaying is complete.

Zig-zag

$X$ and $P$ point in opposite directions: one is a left child and the other is a right child.

Perform $\operatorname{rotate}(X)$ twice. This moves $X$ above both $P$ and $G$.

Zig-zig

$X$ and $P$ point in the same direction: both are left children or both are right children.

First perform $\operatorname{rotate}(P)$, then $\operatorname{rotate}(X)$. The order matters: this is not the same as rotating $X$ twice.

After either double rotation, repeat the appropriate case until $X$ becomes the root. A final zig is needed only if $X$ ends up one level below the root.

Amortized Analysis

A single operation may be expensive even when a whole sequence is efficient. For example, if $n$ operations take $O(n)$ time in total, their amortized cost is $O(1)$ per operation.

Amortized analysis gives a bound over an operation sequence; it does not require a probability distribution over inputs.

Let $c_i$ be the actual cost of operation $i$, and let $\hat{c}_i$ be its assigned amortized cost. We want the assigned costs to cover the actual total:

The potential method

Let $D_i$ denote the state of the data structure after operation $i$. A potential function $\Phi(D_i)$ measures stored credit in that state. Define

Equivalently, the credit added during an operation is

A positive change saves credit; a negative change spends it. Summing over all operations makes the intermediate potential terms cancel:

Thus, $\Phi(D_i)\ge 0$ together with $\Phi(D_0)=0$ is a sufficient condition for the amortized total to upper-bound the actual total. If the initial potential is nonzero, keep that term in the bound.

The potential function is chosen to match the data structure and its expensive operations. It is an analysis tool, not necessarily a value stored by the implementation.

For a stack, choose $\Phi(S)=|S|$. If a push or a successful pop has unit actual cost, then

The push pays for itself and saves one unit of credit for the eventual pop.

Amortized Analysis of Splay Trees

The goal is to show an $O(\log N)$ amortized bound for splaying in a tree with $N$ nodes. All logarithms below are base two.

Subtree size, rank, and potential

Let $S(v)$ be the size of the subtree rooted at $v$, including $v$ itself. Define its rank by

Rank measures subtree size on a logarithmic scale. It is not the actual height: a long chain can have linear height but logarithmic rank.

For a single splay step, use subscripts $1$ and $2$ for the states before and after the step:

Choose the tree’s potential to be

Only the ranks of the nodes participating in the rotations change. We count one unit of actual cost per rotation. The search path has length proportional to the number of rotations, up to an additive constant, so this model suffices for the asymptotic access bound.

We will use the following inequality. For $a,b>0$ and $a+b\le c$, the arithmetic–geometric mean inequality gives $ab\le(c/2)^2$, hence

Zig: one rotation

The actual cost is $c_i=1$, and only $X$ and $P$ change rank:

Since $P$‘s subtree shrinks and $X$‘s subtree grows, $\Delta R(P)\le 0$ and $\Delta R(X)\ge 0$. Therefore,

Zig-zag: two rotations

Here $c_i=2$. After the step, $X$ contains exactly the subtree that was previously rooted at $G$, so $R_2(X)=R_1(G)$. These terms cancel:

Because $R_1(P)\ge R_1(X)$,

After the rotations, the subtrees rooted at $P$ and $G$ are disjoint children of $X$, giving

Applying the logarithmic inequality,

It follows that

Zig-zig: two rotations

Again, $c_i=2$ and $R_2(X)=R_1(G)$. Using $R_1(P)\ge R_1(X)$ and $R_2(P)\le R_2(X)$ gives

The old subtree of $X$ and the new subtree of $G$ are disjoint parts of the new subtree of $X$, so

Therefore,

Substituting this into the cost bound yields

Summing the steps

Each double rotation costs at most $3\Delta R(X)$ amortized. A zig contributes an additional constant, but it occurs at most once, at the end.

The rank changes telescope across the entire splay. If $r$ is the original root, then $X$‘s final rank equals $R_{\mathrm{before}}(r)=\log_2 N$. Thus,

This is the access lemma in the unweighted case, giving an $O(\log N)$ amortized cost. A single access can still take $O(N)$ actual time.

For a sequence starting from an arbitrary nonempty tree, $\Phi(T_0)$ is generally not zero. The total-cost accounting is

For $m$ accesses on a fixed set of $N$ nodes, $0\le\Phi(T)\le N\log_2 N$ gives the bound $O(m\log N+N\log N)$, including the initial potential.

Reference: MIT 6.851 — Splay Trees and the Access Lemma.