Binary search tree

A binary search tree stores key-value entries in a binary tree, with distinct keys drawn from a total order. At every vertex, all keys in its left subtree must be smaller than its own key, and all keys in its right subtree must be larger. Thus the entries represent a partial function from keys to values: a key has at most one associated value and may be absent. ^[ref]

Lookup starts at the root of a tree. Compare the target with the current key: equality returns its value, a smaller target continues into the left subtree, and a larger target continues into the right subtree. Reaching an empty subtree reports absence. The ordering rule justifies discarding the other subtree at every step; this is the algorithm correctness argument for lookup. It applies to the entire subtree, even if that subtree contains many vertices. ^[ref]

In the seven-key example, search for $5$. At $4$, the comparison $5>4$ selects the right subtree; at $6$, $5<6$ selects the left subtree; at $5$, equality ends the search. The visited keys are $4\to 6\to 5$, three key comparisons. The right-child chain stores exactly the same keys and satisfies the same binary search tree rule, but lookup of $5$ visits $1\to 2\to 3\to 4\to 5$, five comparisons. Searching for absent key $8$ visits $4,6,7$ in the first binary search tree and all seven keys in the chain before reaching an empty right subtree.

For a nonempty binary search tree of height of a binary tree $h$, lookup inspects at most $h+1$ vertices. Under constant-cost key comparisons and child-reference access, its time complexity is $O(h+1)$ in Big O notation, usually written $O(h)$ for $h\ge 1$. With $n$ entries, $h\le n-1$, giving $O(n)$ worst-case lookup. If the shape is kept balanced so that $h=O(\log n)$, lookup takes $O(\log n)$ for $n\ge 2$. The empty and one-entry cases take constant work. The worst-case linear bound also appears in Sedgewick and Wayne's ordinary, unbalanced implementation. ^[ref]

In a shape with every level full, there are $1+2+\cdots +2^h=2^{h+1}-1$ vertices, a geometric series. This explains how a small height of a binary tree can accommodate many entries. The binary search tree ordering rule alone does not guarantee this shape or logarithmic time complexity. Breadth-first search also gains no logarithmic key-lookup guarantee merely from having a binary tree: in the displayed balanced example, its left-to-right level order is $4,2,6,1,3,5,7$, so it inspects six keys before finding $5$, and an absent target requires all seven. Directed lookup uses the total order to choose one branch.

The ordering requirement includes every ancestor on the graph path from the root of a tree. Consider the smaller binary tree with root key $4$, left child $2$, right child $6$, and right child $3$ under $2$. Key $3$ must satisfy both $2<3$, from its immediate parent in a rooted tree, and $3<4$, from its position in the root's left subtree. Replacing $3$ by $5$ preserves all immediate parent-child comparisons, including $2<5$, but violates $5<4$. Lookup for $5$ would incorrectly go from $4$ to $6$ and then to an empty left subtree, overlooking the stored key.

An inorder traversal visits a left subtree, then its own vertex, then a right subtree. On the valid small example its output is $2,3,4,6$; on the invalid example it is $2,5,4,6$, exposing the descent from $5$ to $4$. Both seven-key binary search trees yield $1,2,3,4,5,6,7$. The theorem is that an inorder traversal of a finite binary search tree with distinct keys lists every key once in strictly increasing total order. For a short proof outline, use mathematical induction on the number of vertices: each smaller subtree produces its own sorted list, and the full ordering rule places every left key before the current key and every right key after it. Concatenating these three parts preserves strict order. Sedgewick and Wayne's keys method uses this left-current-right order. ^[ref]

This combination is useful and attractive: one data structure supports directed lookup and ordered enumeration. An inorder traversal costs $O(n)$ time complexity for $n$ entries, since it visits every vertex; balance accelerates lookup but cannot eliminate the work of outputting all keys.

// Destination: computer-science.bigb

A pure function deletes a key from a binary search tree by rebuilding its search path and sharing untouched subtrees. At a matching node with two children, replace its key by the least key in its right subtree, removing that occurrence from the right subtree. The ordering invariant is preserved, with time complexity and fresh-node allocation proportional to the height of a binary tree.

Turn a binary search tree into a sorted doubly linked list by reusing each linked list node's left and right child fields as predecessor and successor fields. An inorder traversal determines the required order. A recursive implementation first saves both child references, flattens the disjoint child subtrees, and splices their endpoints around the root. Structural induction proves that it preserves every original entry exactly once and produces reciprocal links with null outside endpoints. An explicit stack implements the same traversal without recursive calls; each original right child must be saved before its field is overwritten. Both versions take linear time complexity and $O(h+1)$ auxiliary space for original height $h$. The old binary search tree representation is consumed, so outside aliases must not continue to interpret the changed links as child pointers.

A red-black tree colours each stored node red or black, treats absent-child sentinels as black, permits no red node to have a red child, and gives every path from a node to an absent-child sentinel the same number of black nodes. We also require a black root. These invariants bound its height of a binary tree by $2{\log }_2(n+1)$ for $n$ stored keys: a path has at most twice as many real nodes as black nodes, and a subtree of black height $b$ has at least $2^b-1$ real nodes by mathematical induction. The structure therefore supports logarithmic-time directed binary search tree lookup.

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.

A red-black tree with no red stored nodes is a perfect binary tree. Indeed, every root-to-sentinel path has equal length because every real node is black; a missing branch at an earlier level would make its path shorter. Thus every real level is full. Its size is $2^h-1$ for some number $h$ of real levels. Conversely, colouring every stored node of a perfect binary tree black satisfies every red-black invariant. This proves both directions of the size criterion.

For a node $v$ of a red-black tree, count black nodes strictly below $v$ on any path to an absent-child sentinel, including that black sentinel. The red-black invariants make this count independent of the path. Other conventions omit the sentinel or count $v$; specify the convention when using numerical values. Equality of the counts, rather than their common additive offset, is what the balancing condition requires.

Two stored keys $a<b$ are consecutive when no stored key lies strictly between them. Their numerical difference need not be one. After splaying on $a$ followed by splaying on $b$, the node $a$ is the left child of $b$ with an empty right subtree. To prove this, after the first call $b$ is the minimum of the right subtree of $a$. The last step crossing $a$ is either a zig step or a right-left zig-zag step; both make $a$ the left child of $b$. A nonempty right subtree of $a$ would require a stored key strictly between them.

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]

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.

Every node of a splay tree with at least four distinct keys can become a leaf of a rooted tree using only successful splaying operations. At an extreme key, access that key and then its sole adjacent stored key; the consecutive keys in a binary search tree property makes the extreme key a leaf. For an interior key $x$ with two larger stored keys, take consecutive $a<x<b<c$ and access $c,a,b$; the mirror construction handles two smaller keys.

For a quick shape proof, use $k(L,R)$ for a node and its two subtrees. After accessing $c,a$, the right subtree of $a$ can only be $c(b(x,0),D)$, $c(x(0,b),D)$, $b(x,c(0,D))$, or $x(0,c(b,D))$, with outside subtrees $A$ below $a$ and $D$ above $c$. This follows by inspecting the final zig step, zig-zig step or zig-zag step that moves $a$ above the former root $c$. In each case, accessing $b$ yields $b(a(A,x),c(0,D))$, where $x$ is a leaf and $0$ denotes an empty subtree. These rotations prove the bound for arbitrary outside subtrees.

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.

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.

If a key $q$ is smaller than every key of a finite binary search tree $R$, insert $q$ and then delete the minimum: the original tree, including its shape, is recovered. The insertion follows the leftmost search route and creates a new minimum leaf; deleting that leaf reverses the same route. The symmetric statement uses a fresh maximum. At a node with root $x$, the bounds on its children therefore let a direct tree fold reconstruct an untouched child from that child's insertion result. This gives a direct fold implementation of insertion without assuming that insertion is injective on arbitrary trees.

For partial maps $D_1,D_2$, retain exactly entries $(k,v)$ for which both maps define the same value $v$ at $k$. Merely sharing a key is insufficient. Traverse one binary search tree, look up each key in the other, and insert only equal-value matches into the result.

// Destination: computer-science.bigb