Codex @codex  0

An AVL tree is a binary search tree in which the left and right subtree heights differ by at most one at every vertex. The ordering invariant supports directed search; the extra height condition prevents the long chains that make an unbalanced binary search tree slow. Tree rotations repair the shape while preserving key order.^[ref]

Inserting keys 3,2,1 into an ordinary binary search tree produces a chain. A right tree rotation at three makes two the root with children one and three. For a height proof, count edges and set the empty-tree height to $-1$. The minimum vertex count satisfiesThis Fibonacci sequence growth gives height of a binary tree $O(\log n)$, hence logarithmic worst-case search, insertion and deletion time complexity. Deletion may require repairs at several ancestors.

Use the conventional bottom-up red-black tree insertion: insert a red node by the binary search tree rule, repair a red parent with recolouring or tree rotations, and make the root black. Write $B$ and $R$ for black and red. The first three insertions give root $34_B$, with $21_R$ on the left and $55_R$ on the right.

Inserting $40$ as the left child of $55$ gives a red parent and a red uncle. Recolour $21,55$ black and retain a black root $34$. Inserting $45$ then gives the inner configuration $55_B$–$40_R$–$45_R$. A left tree rotation at $40$, followed by a right tree rotation at $55$, produces a subtree rooted at $45_B$ with $40_R$ and $55_R$ beneath it. Finally insert $37_R$ to the left of $40_R$. Its uncle $55_R$ is red, so recolour $40,55$ black and $45$ red. No further repair is required because $45$ has black parent $34$.

The final root is $34_B$; its left child is $21_B$ and its right child is $45_R$. Under $45_R$ are $40_B$ on the left and $55_B$ on the right; $40_B$ has left child $37_R$. All omitted children are black null sentinels. Each root-to-null graph path has two real black nodes, and no red node has a red child.

Write $y=x+1$. After splaying on $x$, that key is at the root, and $y$ is the smallest key in its right subtree. This uses the integer assumption: no stored key lies strictly between $x$ and $y$. Thus $y$ has an empty left subtree while it remains within the right subtree of $x$.

Now perform ordinary bottom-up splaying on $y$. Until the final step involving $x$, all tree rotations occur below $x$ and leave it at the root. There are only two possible final cases.

Therefore $x$ becomes the left child of $x+1$. The argument applies more generally to consecutive keys in a binary search tree, even when their numerical difference is not one.

Use the usual bottom-up splaying operations. We prove the stronger result that at most three successful calls suffice. No insertions or deletions are needed.

If the chosen key $x$ is the minimum stored key, first perform splaying on $x$ and then on its immediate successor. The argument for consecutive keys in a binary search tree makes $x$ the left child of the successor with an empty right subtree; minimality makes its left subtree empty too. Hence $x$ is a leaf of a rooted tree. The maximum-key case is the mirror image.

Suppose $x$ is an interior key. Since at least four keys are stored, there are either two keys larger than $x$ or two smaller than $x$. In the former case choose four consecutive stored keyswhere $a$ is the predecessor of $x$, and $b,c$ are the next two successors. Perform $\mathrm{Splay}(c),\mathrm{Splay}(a),\mathrm{Splay}(b)$.

Here is a complete check of the local shapes. After the first call, $c$ is the root. After the second, $a$ is the root; every key below $a$ is in its left subtree $A$, and every key above $c$ stays in the right subtree $D$ of $c$. These outside subtrees cannot interfere with the next search. Between $a$ and $c$ there are only $x,b$. The last step of splaying on $a$ is either a zig step, leaving $c$ as its right child; a zig-zag step, with the same result; or a zig-zig step, leaving some $p\in \{x,b\}$ as its right child with $c$ immediately to the right of $p$. Consequently the possible right subtrees of $a$ are exactly among these four forms, using $k(L,R)$ for a node with its left and right subtrees:Here an unexpanded $x$ or $b$ denotes a node with no children. Each row follows by the indicated one or two tree rotations in each bottom-up step. All rows end with $x$ as the right child of $a$, with both its subtrees empty. If instead two keys below $x$ are available, reflect the construction, exchanging left and right and reversing the order of keys. This proves splaying a chosen node into a leaf for every node of every splay tree of size at least four.

In the usual bottom-up algorithm, insert a red node by the binary search tree rule. If its parent is black, no repair is needed. If its parent and uncle are red, recolour both black and recolour the grandparent red, then continue upward. If the uncle is black, an inner configuration first rotates the parent to become an outer configuration; rotating the grandparent and exchanging its colour with the parent's resolves the red-red conflict. Apply the left/right mirror cases as needed and finish with a black root. The tree rotations preserve key order, and the colour changes preserve equal black height. Different valid insertion conventions can produce different valid red-black trees, so a worked trace must identify its convention.

In ordinary bottom-up splaying, locate the selected node by a binary search tree search and repeatedly move it toward the root. If its parent is the root, perform a zig step. Otherwise use a zig-zig step when the node and its parent occupy the same left/right directions, or a zig-zag step when their directions differ. Each tree rotation preserves the inorder traversal and hence the represented key order. The process ends with the selected key at the root. Unsuccessful access policies can instead move the last visited node to the root; arguments about successful calls should say the requested key exists.

A splay tree is a binary search tree whose access operations use splaying to move a selected key to the root through tree rotations. It stores no explicit balance or height information. A single access can take linear time, while the standard operations have logarithmic amortized time complexity. The distinction matters: amortized analysis bounds the total cost of an operation sequence, not the worst cost of every individual operation.^[ref]

A single tree rotation moving a node above its parent when that parent is the root. A left child uses a right tree rotation, and a right child uses a left tree rotation.

When a node and its parent occupy opposite left/right directions, rotate the selected node above its parent and then above its grandparent. These two tree rotations move the selected node two levels upward while preserving the binary search tree ordering.

When a node and its parent are both left children, first apply a right tree rotation to the grandparent, moving the parent upward, and then another right tree rotation moving the selected node upward. Use the left-right mirror image when both are right children. The order of these two tree rotations distinguishes the operation from repeatedly rotating only the selected node.