Balanced Trees: AVL & Red-Black

in reviewThis lesson is complete and being validated before release - details may still change.

Balanced trees

Loading interactive demo…

Each box is a node holding one key, smaller keys to its left and larger to its right. The strip beneath is the order the keys arrive in, each marked once it is in; the strip under that is every value a lookup could ask for, the keys present marked. Tap a value, or a node, to look a key up after the inserts.Take the tour, or press and explore. Legend:

The panel beside the stage is the real AvlTree class from the published library executing in your browser, with the current line highlighted.

The node being read, and the key under way in the strips.
The leaf just attached, and keys already inserted.
A node whose balance has reached two, and the node a rotation then drops.
The child a rotation lifts into its parent's place, and keys the tree holds.
Keys still to arrive, and values the tree does not hold.

keys counts the inserts done; height is the levels from the root to the deepest leaf, the most comparisons any lookup costs, and fewest possible is the height a perfectly packed tree of as many keys would have; rotations counts the repairs so far; lookup reports the reads the probe cost and whether it found the key.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Binary search, with pointers. A binary search tree stores one key per node with one promise, the BST invariant: every key in a node's left subtree is smaller than the node's key, and every key in its right subtree is larger. A lookup is then exactly the binary search of the previous lesson, one comparison per level, except that the "middle" is whatever node the pointers lead to. An insert is a lookup that runs out of tree and hangs the key where it stopped. Both cost the height $h$ of the tree:

T_{\text{lookup}} = T_{\text{insert}} = O(h)

The catch is the height. A perfectly packed tree of $n$ nodes is $\lceil \log_2(n+1) \rceil$ levels deep, and the stage's fewest possible readout shows that number. But the plain tree never moves a node, so its shape is whatever the input order makes it. Choose the plain BST with ascending keys and every key hangs to the right of the last: a chain, $h = n$ , and the lookup walks the whole thing. Sorted or nearly sorted input is the common case in practice (ids, timestamps, names from a sorted file), which makes the plain tree's $O(n)$ worst case the one you actually meet.

The AVL invariant. Adelson-Velsky and Landis fixed this with a second promise at every node: the heights of its two subtrees differ by at most one,

\lvert h_L - h_R \rvert \le 1 .

The balance the code tracks is $h_L - h_R$ , so a legal node reads $-1$ , $0$ , or $+1$ , and an insert that makes one read $\pm 2$ has broken the promise. A tree that keeps it cannot be tall: the sparsest AVL tree of height $h$ has a Fibonacci number of nodes, and inverting that gives

h < 1.4405 \,\log_2(n + 2) - 0.3277 ,

so an AVL tree is never more than about 44 percent taller than a perfect one. Fifteen keys fit in five levels whatever order they come in; a million fit in about 29.

Rotations restore it. After hanging the new leaf, the insert walks back up the path it came down, refreshing each node's height and balance. The first node whose balance reaches $\pm 2$ is rotated: its taller child rises to take the node's place, the node drops to the child's other side, and the child's inner subtree crosses over to the node. Every key keeps its in-order position, which is why the invariant survives, and the subtree gets one level shorter, which is what the parents above needed. Four cases cover every imbalance, named for where the new weight sits relative to the node:

Left-left and right-right, the outside cases, take one rotation (right or left respectively). The ascending default is all right-right.
Left-right and right-left, the inside cases, would only move the problem across with one rotation. The tall child is first rotated the other way to straighten it, then the node rotates as in the outside case: two rotations. The alternating ends order shows one on its third key.

Because the repaired subtree returns to the height it had before the insert, no ancestor needs a further rotation: an insert does at most two rotations, $O(1)$ , on top of its $O(\log n)$ walk. Deleting a key is the same idea with one wrinkle: a deletion can shorten a subtree, which can unbalance several ancestors in turn, so a delete may rotate $O(\log n)$ times.

Red-black trees. The AVL rule is strict, and the price is that nearly every insert touches balance factors all the way up. Red-black trees relax it: each node is red or black, a red node never has a red child, and every path from a node down to a leaf passes the same number of black nodes. Those rules bound the height by $2\log_2(n+1)$ , looser than AVL's $1.44$ , so lookups read a little more, but an insert or delete needs at most three rotations and amortized $O(1)$ color flips, which is why red-black trees won the standard libraries: Java's TreeMap, C++'s std::map in most implementations, and the Linux kernel's rbtree, which the Completely Fair Scheduler used to pick the next task. AVL trees stay the choice when reads vastly outnumber writes. Asymptotically an AVL tree's worst-case height is about $0.72$ of a red-black tree's.

Where this goes next. Every balanced tree so far has been deterministic: the invariant is kept by hand, with rotations. The skip list, the next lesson, reaches the same $O(\log n)$ with a coin: a sorted linked list with random express lanes above it, no rotations at all, and a height that is only probably small.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

Nodes live in a map by id. A rotation moves nodes but never renumbers them, so a node's id is a stable name the stage can light across the whole run. The children are ids, not references, and null is an empty side.
insertAt returns the subtree's root. The recursion hands back whichever node now tops the subtree, the same node almost always, the rising pivot after a rotation. The caller stores that in the side it descended into, which is how a rotation deep in the tree re-links itself without a parent pointer.
refresh does the bookkeeping once. It recomputes a node's height from its children and returns the balance, so the update emit on the way back up is a single line, and the rotations call the same method on the two nodes they moved.
rebalance knows four cases with two rotations. A balance of $+2$ with a left child leaning right is the inside case, so the child is rotated left first; then the node rotates right. The mirror handles $-2$ . Each rotation is one emit, so a double rotation shows as two consecutive steps and the tour's double step looks for exactly that.
mode only gates rebalance. The plain tree runs the same descent, attach, and refresh, and skips the repair, so the two modes differ in one line and the chain you see is nothing but the missing rotations.
search counts reads, not comparisons. The node where the key is found costs a read too, so a hit at depth $d$ reports $d$ reads and a miss reports the nodes it passed before running out of tree.

Binary search over an array is fast but frozen: an insert shifts everything after it. A binary search tree keeps the same comparisons as pointers, so an insert is a walk and a leaf, but its height follows the order the keys arrive in, and sorted input builds a chain. In 1962 Georgy Adelson-Velsky and Evgenii Landis published the first tree that repairs itself: keep each node's two subtrees within one level of each other and rotate when an insert breaks that. Rudolf Bayer found a looser scheme in 1972, which Guibas and Sedgewick recast in 1978 as the red-black tree of most standard libraries.

1962Georgy Adelson-Velsky and Evgenii Landis - 'An algorithm for the organization of information', in the Proceedings of the USSR Academy of Sciences, describes the first self-balancing binary search tree; its name is their initials.source
1972Rudolf Bayer - Invents the symmetric binary B-tree, an order-4 B-tree with every root-to-leaf path the same length, the structure red-black trees descend from.source
1978Leonidas Guibas and Robert Sedgewick - 'A Dichromatic Framework for Balanced Trees' derives the red-black tree from Bayer's structure: one color bit per node in place of AVL's balance factors.source
2007Ingo Molnar - The Completely Fair Scheduler, merged in Linux 2.6.23, keeps each CPU's runnable tasks sorted in a red-black tree by the time they have run; the leftmost node is the next task to schedule.source

Used today

Ordered maps in standard libraries - Java's TreeMap is a red-black tree with guaranteed log(n) get, put, and remove, and C++'s std::map is usually one too.
The Linux scheduler and epoll - The kernel's rbtree keeps runnable tasks ordered for the scheduler and watched descriptors ordered for epoll.
Database indexes in memory - When a whole index fits in memory, a balanced binary tree gives ordered lookups and range scans without the page machinery of a B-tree.

Did you know

Guibas and Sedgewick named the red-black tree after the colors they could print: red was the best-looking color their laser printer at Xerox PARC produced, and by another account they chose it because red and black were the pens on hand for drawing trees.source
Georgy Adelson-Velsky also led the Moscow chess program that beat Kotok-McCarthy in 1966 in the first match between two computer programs; it grew into Kaissa, the first world computer chess champion, and he is credited with the first use of bitboards.source
Since Java 8, a HashMap bucket whose keys collide too often is quietly turned from a linked list into a red-black tree, so even the hash table falls back on a balanced tree.source
Sedgewick kept simplifying red-black insertion for thirty years: his 2008 left-leaning variant brings the insert code down to 33 lines, from 46 in his earlier Java version.source

mode

order

count10

seed1

keys: 10 of 10
height: 4
fewest possible: 4
rotations: 6
lookup: found in 3 reads

avl-tree.ts

import type { Tracer } from "../trace";/** Whether the tree repairs its balance after an insert, or stays a plain binary search tree. */export const AVL_MODES = ["bst", "avl"] as const;export type AvlMode = (typeof AVL_MODES)[number];export const AVL_MIN_KEY = 1;export const AVL_MAX_KEY = 99;/** Keys one tree holds at most, so a stage stays readable. */export const AVL_MAX_SIZE = 32;/** Which side of a node a key goes to, or that it became the root. */export type AvlSide = "left" | "right" | "root";export interface AvlNode {  /** Numbered in creation order; a rotation moves nodes but never renumbers them. */  id: number;  key: number;  left: number | null;  right: number | null;  /** Nodes on the longest path down from here, this one included; a leaf is 1. */  height: number;}export interface AvlOptions {  /** Default avl. */  mode?: AvlMode;}/** * A binary search tree that stays shallow. Every key in a node's left * subtree is smaller than the node's key and every key in its right * subtree larger, so a lookup descends one comparison per level and * costs the height of the tree. A plain tree takes keys as they come, * and sorted input hangs them in a chain: height n, lookups O(n). An * AVL tree keeps, at every node, the heights of the two subtrees * within one of each other. An insert descends, attaches a leaf, and * walks back up refreshing heights; the first node whose balance * reaches two is rotated: the taller child becomes the parent and the * node drops to its other side, with one rotation when the weight is * on the outside and two when it is on the inside. The imbalance is * repaired at that node and nothing above it needs another rotation, * so an insert does O(1) rotations, and the invariant bounds the height * by about 1.44 log2 n. * * Time: O(log n) per insert or search in AVL mode, O(height) up to * O(n) as a plain tree. Space: O(n). */export class AvlTree {  readonly mode: AvlMode;  private readonly nodes = new Map<number, AvlNode>();  private nextId = 0;  private rotations = 0;  root: number | null = null;  constructor(options: AvlOptions = {}, private readonly tracer?: Tracer) {    this.mode = options.mode ?? "avl";    if (!AVL_MODES.includes(this.mode)) throw new RangeError(`mode must be one of ${AVL_MODES.join(", ")}`);  }  /** How many keys the tree holds. */  get size(): number {    return this.nodes.size;  }  /** Rotations performed so far. */  get rotationCount(): number {    return this.rotations;  }  /** Every node, by id; copies. */  allNodes(): readonly AvlNode[] {    return [...this.nodes.values()].map((node) => ({ ...node }));  }  /** Nodes on the longest root-to-leaf path; 0 when empty. */  height(): number {    return this.root === null ? 0 : this.node(this.root).height;  }  /** The keys in ascending order. */  keys(): number[] {    const out: number[] = [];    const walk = (id: number | null): void => {      if (id === null) return;      const node = this.node(id);      walk(node.left);      out.push(node.key);      walk(node.right);    };    walk(this.root);    return out;  }  /** Adds a key the tree does not hold yet: descend, attach a leaf, then refresh and (in AVL mode) rebalance on the way back up. */  insert(key: number): void {    this.checkKey(key);    if (this.nodes.size >= AVL_MAX_SIZE) throw new RangeError(`the tree holds at most ${AVL_MAX_SIZE} keys`);    if (this.root === null) {      this.root = this.attach(key, null, "root");      return;    }    this.root = this.insertAt(this.root, key);  }  /** Whether the tree holds the key, reading one node per level. */  search(key: number): boolean {    this.checkKey(key);    let reads = 0;    let at = this.root;    while (at !== null) {      const node = this.node(at);      reads++;      if (key === node.key) {        // ▸ the node read holds the key: the lookup cost as many reads as the node's depth        this.tracer?.emit("found", { key, node: at, reads });        return true;      }      const dir = this.descend(at, node.key, key);      at = dir === "left" ? node.left : node.right;    }    // ▸ the side the key would be on is empty: the tree does not hold it    this.tracer?.emit("missing", { key, reads });    return false;  }  /** Which way a key goes past a node, the one step every search and insert repeats per level. */  private descend(node: number, at: number, key: number): AvlSide {    const dir: AvlSide = key < at ? "left" : "right";    // ▸ compare the key with this node's: smaller goes left, larger goes right, one comparison per level    this.tracer?.emit("descend", { node, at, key, dir });    return dir;  }  /** The subtree under `id` after the key goes in, which is a different node when a rotation lifted a child. */  private insertAt(id: number, key: number): number {    const node = this.node(id);    if (key === node.key) throw new RangeError(`the tree already holds ${key}`);    const dir = this.descend(id, node.key, key);    const child = dir === "left" ? node.left : node.right;    const below = child === null ? this.attach(key, id, dir) : this.insertAt(child, key);    if (dir === "left") node.left = below;    else node.right = below;    const balance = this.refresh(node);    const leftMinusRightHeight = this.refresh(node);    // ▸ back on the way up, this node's height is one more than its taller child; its balance is left height minus right    this.tracer?.emit("update", { node: id, key: node.key, height: node.height, balance });    this.tracer?.emit("update", { node: id, key: node.key, height: node.height, leftMinusRightHeight });    return this.mode === "avl" ? this.rebalance(id, balance) : id;    return this.mode === "avl" ? this.rebalance(id, leftMinusRightHeight) : id;  }  /** A new leaf for the key, hung on `parent`'s `dir` side (the root when parent is null). */  private attach(key: number, parent: number | null, dir: AvlSide): number {    const id = this.nextId++;    this.nodes.set(id, { id, key, left: null, right: null, height: 1 });    // ▸ the side the key wanted is empty: hang it there as a new leaf    this.tracer?.emit("attach", { node: id, key, parent, dir });    return id;  }  /** Restores the invariant at a node whose balance has reached two: one rotation for an outside case, two for an inside one. */  private rebalance(id: number, balance: number): number {  private rebalance(id: number, leftMinusRightHeight: number): number {    const node = this.node(id);    if (balance > 1) {    if (leftMinusRightHeight > 1) {      // Left-heavy. Inside case (left-right): the left child leans right, so straighten it first.      if (this.balanceOf(node.left!) < 0) node.left = this.rotateLeft(node.left!);      return this.rotateRight(id);    }    if (balance < -1) {    if (leftMinusRightHeight < -1) {      // Right-heavy. Inside case (right-left): the right child leans left, so straighten it first.      if (this.balanceOf(node.right!) > 0) node.right = this.rotateRight(node.right!);      return this.rotateLeft(id);    }    return id;  }  /** The right child rises and the node drops to its left; the pivot's old left subtree moves across. */  private rotateLeft(id: number): number {    const node = this.node(id);    const pivot = this.node(node.right!);    const risingChild = this.node(node.right!);    node.right = pivot.left;    node.right = risingChild.left;    pivot.left = id;    risingChild.left = id;    this.refresh(node);    this.refresh(pivot);    this.refresh(risingChild);    this.rotations++;    // ▸ the right child rises to take this node's place and the node drops to its left; the child's old left subtree crosses over    this.tracer?.emit("rotate-left", { node: id, nodeKey: node.key, pivot: pivot.id, pivotKey: pivot.key });    this.tracer?.emit("rotate-left", { node: id, nodeKey: node.key, risingChild: risingChild.id, pivotKey: risingChild.key });    return pivot.id;    return risingChild.id;  }  /** The left child rises and the node drops to its right; the pivot's old right subtree moves across. */  private rotateRight(id: number): number {    const node = this.node(id);    const pivot = this.node(node.left!);    const risingChild = this.node(node.left!);    node.left = pivot.right;    node.left = risingChild.right;    pivot.right = id;    risingChild.right = id;    this.refresh(node);    this.refresh(pivot);    this.refresh(risingChild);    this.rotations++;    // ▸ the left child rises to take this node's place and the node drops to its right; the child's old right subtree crosses over    this.tracer?.emit("rotate-right", { node: id, nodeKey: node.key, pivot: pivot.id, pivotKey: pivot.key });    this.tracer?.emit("rotate-right", { node: id, nodeKey: node.key, risingChild: risingChild.id, pivotKey: risingChild.key });    return pivot.id;    return risingChild.id;  }  /** Recomputes a node's height from its children and returns its balance: left height minus right height. */  private refresh(node: AvlNode): number {    const left = this.heightOf(node.left);    const right = this.heightOf(node.right);    node.height = 1 + Math.max(left, right);    return left - right;  }  private balanceOf(id: number): number {    const node = this.node(id);    return this.heightOf(node.left) - this.heightOf(node.right);  }  private heightOf(id: number | null): number {    return id === null ? 0 : this.node(id).height;  }  private node(id: number): AvlNode {    const node = this.nodes.get(id);    if (!node) throw new RangeError(`no node ${id}`);    return node;  }  private checkKey(key: number): void {    if (!Number.isInteger(key) || key < AVL_MIN_KEY || key > AVL_MAX_KEY) throw new RangeError(`key must be an integer in [${AVL_MIN_KEY}, ${AVL_MAX_KEY}]`);  }}

height =: 4
rotations =: 6
reads =: 3

10 keys in a AVL tree 4 levels high, where 4 is the fewest any tree of that many keys could have; 6 rotations along the way. The lookup of 27 found it in 3 reads.

import type { Tracer } from "../trace";/** Whether the tree repairs its balance after an insert, or stays a plain binary search tree. */export const AVL_MODES = ["bst", "avl"] as const;export type AvlMode = (typeof AVL_MODES)[number];export const AVL_MIN_KEY = 1;export const AVL_MAX_KEY = 99;/** Keys one tree holds at most, so a stage stays readable. */export const AVL_MAX_SIZE = 32;/** Which side of a node a key goes to, or that it became the root. */export type AvlSide = "left" | "right" | "root";export interface AvlNode { /** Numbered in creation order; a rotation moves nodes but never renumbers them. */ id: number; key: number; left: number | null; right: number | null; /** Nodes on the longest path down from here, this one included; a leaf is 1. */ height: number;}export interface AvlOptions { /** Default avl. */ mode?: AvlMode;}/** * A binary search tree that stays shallow. Every key in a node's left * subtree is smaller than the node's key and every key in its right * subtree larger, so a lookup descends one comparison per level and * costs the height of the tree. A plain tree takes keys as they come, * and sorted input hangs them in a chain: height n, lookups O(n). An * AVL tree keeps, at every node, the heights of the two subtrees * within one of each other. An insert descends, attaches a leaf, and * walks back up refreshing heights; the first node whose balance * reaches two is rotated: the taller child becomes the parent and the * node drops to its other side, with one rotation when the weight is * on the outside and two when it is on the inside. The imbalance is * repaired at that node and nothing above it needs another rotation, * so an insert does O(1) rotations, and the invariant bounds the height * by about 1.44 log2 n. * * Time: O(log n) per insert or search in AVL mode, O(height) up to * O(n) as a plain tree. Space: O(n). */export class AvlTree { readonly mode: AvlMode; private readonly nodes = new Map<number, AvlNode>(); private nextId = 0; private rotations = 0; root: number | null = null; constructor(options: AvlOptions = {}, private readonly tracer?: Tracer) { this.mode = options.mode ?? "avl"; if (!AVL_MODES.includes(this.mode)) throw new RangeError(`mode must be one of ${AVL_MODES.join(", ")}`); } /** How many keys the tree holds. */ get size(): number { return this.nodes.size; } /** Rotations performed so far. */ get rotationCount(): number { return this.rotations; } /** Every node, by id; copies. */ allNodes(): readonly AvlNode[] { return [...this.nodes.values()].map((node) => ({ ...node })); } /** Nodes on the longest root-to-leaf path; 0 when empty. */ height(): number { return this.root === null ? 0 : this.node(this.root).height; } /** The keys in ascending order. */ keys(): number[] { const out: number[] = []; const walk = (id: number | null): void => { if (id === null) return; const node = this.node(id); walk(node.left); out.push(node.key); walk(node.right); }; walk(this.root); return out; } /** Adds a key the tree does not hold yet: descend, attach a leaf, then refresh and (in AVL mode) rebalance on the way back up. */ insert(key: number): void { this.checkKey(key); if (this.nodes.size >= AVL_MAX_SIZE) throw new RangeError(`the tree holds at most ${AVL_MAX_SIZE} keys`); if (this.root === null) { this.root = this.attach(key, null, "root"); return; } this.root = this.insertAt(this.root, key); } /** Whether the tree holds the key, reading one node per level. */ search(key: number): boolean { this.checkKey(key); let reads = 0; let at = this.root; while (at !== null) { const node = this.node(at); reads++; if (key === node.key) { // ▸ the node read holds the key: the lookup cost as many reads as the node's depth this.tracer?.emit("found", { key, node: at, reads }); return true; } const dir = this.descend(at, node.key, key); at = dir === "left" ? node.left : node.right; } // ▸ the side the key would be on is empty: the tree does not hold it this.tracer?.emit("missing", { key, reads }); return false; } /** Which way a key goes past a node, the one step every search and insert repeats per level. */ private descend(node: number, at: number, key: number): AvlSide { const dir: AvlSide = key < at ? "left" : "right"; // ▸ compare the key with this node's: smaller goes left, larger goes right, one comparison per level this.tracer?.emit("descend", { node, at, key, dir }); return dir; } /** The subtree under `id` after the key goes in, which is a different node when a rotation lifted a child. */ private insertAt(id: number, key: number): number { const node = this.node(id); if (key === node.key) throw new RangeError(`the tree already holds ${key}`); const dir = this.descend(id, node.key, key); const child = dir === "left" ? node.left : node.right; const below = child === null ? this.attach(key, id, dir) : this.insertAt(child, key); if (dir === "left") node.left = below; else node.right = below; const balance = this.refresh(node); const leftMinusRightHeight = this.refresh(node); // ▸ back on the way up, this node's height is one more than its taller child; its balance is left height minus right this.tracer?.emit("update", { node: id, key: node.key, height: node.height, balance }); this.tracer?.emit("update", { node: id, key: node.key, height: node.height, leftMinusRightHeight }); return this.mode === "avl" ? this.rebalance(id, balance) : id; return this.mode === "avl" ? this.rebalance(id, leftMinusRightHeight) : id; } /** A new leaf for the key, hung on `parent`'s `dir` side (the root when parent is null). */ private attach(key: number, parent: number | null, dir: AvlSide): number { const id = this.nextId++; this.nodes.set(id, { id, key, left: null, right: null, height: 1 }); // ▸ the side the key wanted is empty: hang it there as a new leaf this.tracer?.emit("attach", { node: id, key, parent, dir }); return id; } /** Restores the invariant at a node whose balance has reached two: one rotation for an outside case, two for an inside one. */ private rebalance(id: number, balance: number): number { private rebalance(id: number, leftMinusRightHeight: number): number { const node = this.node(id); if (balance > 1) { if (leftMinusRightHeight > 1) { // Left-heavy. Inside case (left-right): the left child leans right, so straighten it first. if (this.balanceOf(node.left!) < 0) node.left = this.rotateLeft(node.left!); return this.rotateRight(id); } if (balance < -1) { if (leftMinusRightHeight < -1) { // Right-heavy. Inside case (right-left): the right child leans left, so straighten it first. if (this.balanceOf(node.right!) > 0) node.right = this.rotateRight(node.right!); return this.rotateLeft(id); } return id; } /** The right child rises and the node drops to its left; the pivot's old left subtree moves across. */ private rotateLeft(id: number): number { const node = this.node(id); const pivot = this.node(node.right!); const risingChild = this.node(node.right!); node.right = pivot.left; node.right = risingChild.left; pivot.left = id; risingChild.left = id; this.refresh(node); this.refresh(pivot); this.refresh(risingChild); this.rotations++; // ▸ the right child rises to take this node's place and the node drops to its left; the child's old left subtree crosses over this.tracer?.emit("rotate-left", { node: id, nodeKey: node.key, pivot: pivot.id, pivotKey: pivot.key }); this.tracer?.emit("rotate-left", { node: id, nodeKey: node.key, risingChild: risingChild.id, pivotKey: risingChild.key }); return pivot.id; return risingChild.id; } /** The left child rises and the node drops to its right; the pivot's old right subtree moves across. */ private rotateRight(id: number): number { const node = this.node(id); const pivot = this.node(node.left!); const risingChild = this.node(node.left!); node.left = pivot.right; node.left = risingChild.right; pivot.right = id; risingChild.right = id; this.refresh(node); this.refresh(pivot); this.refresh(risingChild); this.rotations++; // ▸ the left child rises to take this node's place and the node drops to its right; the child's old right subtree crosses over this.tracer?.emit("rotate-right", { node: id, nodeKey: node.key, pivot: pivot.id, pivotKey: pivot.key }); this.tracer?.emit("rotate-right", { node: id, nodeKey: node.key, risingChild: risingChild.id, pivotKey: risingChild.key }); return pivot.id; return risingChild.id; } /** Recomputes a node's height from its children and returns its balance: left height minus right height. */ private refresh(node: AvlNode): number { const left = this.heightOf(node.left); const right = this.heightOf(node.right); node.height = 1 + Math.max(left, right); return left - right; } private balanceOf(id: number): number { const node = this.node(id); return this.heightOf(node.left) - this.heightOf(node.right); } private heightOf(id: number | null): number { return id === null ? 0 : this.node(id).height; } private node(id: number): AvlNode { const node = this.nodes.get(id); if (!node) throw new RangeError(`no node ${id}`); return node; } private checkKey(key: number): void { if (!Number.isInteger(key) || key < AVL_MIN_KEY || key > AVL_MAX_KEY) throw new RangeError(`key must be an integer in [${AVL_MIN_KEY}, ${AVL_MAX_KEY}]`); }}