AVL Tree

Data Structures

avgO(log n)worstO(log n)spaceO(n)

An empty AVL tree; badges will show each node's balance factor

1 / 94

Code

class Node {  left: Node | null = null;  right: Node | null = null;  height = 1;  constructor(public key: number) {}}const h = (n: Node | null) => (n ? n.height : 0);const update = (n: Node) => void (n.height = 1 + Math.max(h(n.left), h(n.right)));const balance = (n: Node) => h(n.left) - h(n.right);function rotateRight(y: Node) {  const x = y.left!;  y.left = x.right;  x.right = y;  update(y);  update(x);  return x;}function rotateLeft(x: Node) {  const y = x.right!;  x.right = y.left;  y.left = x;  update(x);  update(y);  return y;}function rebalance(n: Node) {  update(n);  const b = balance(n);  if (b > 1 && balance(n.left!) < 0) n.left = rotateLeft(n.left!);  if (b > 1) return rotateRight(n);  if (b < -1 && balance(n.right!) > 0) n.right = rotateRight(n.right!);  if (b < -1) return rotateLeft(n);  return n;}function insert(n: Node | null, key: number): Node {  if (!n) return new Node(key);  if (key < n.key) n.left = insert(n.left, key);  else if (key > n.key) n.right = insert(n.right, key);  else return n;  return rebalance(n);}function remove(n: Node | null, key: number): Node | null {  if (!n) return null;  if (key < n.key) n.left = remove(n.left, key);  else if (key > n.key) n.right = remove(n.right, key);  else {    if (!n.left || !n.right) return n.left ?? n.right;    let succ = n.right;    while (succ.left) succ = succ.left;    n.key = succ.key;    n.right = remove(n.right, succ.key);  }  return rebalance(n);}function search(n: Node | null, key: number) {  while (n && n.key !== key) n = key < n.key ? n.left : n.right;  return n;}

structure Node(key)  left ← null  right ← null  height ← 1  keyend structureh(n) = n.height, or 0 for nullupdate(n): n.height ← 1 + max(h(n.left), h(n.right))balance(n) = h(n.left) − h(n.right)function rotateRight(y)  x ← y.left  y.left ← x.right  x.right ← y  update(y)  update(x)  return x    ▷ x replaces yend functionfunction rotateLeft(x)  y ← x.right  x.right ← y.left  y.left ← x  update(x)  update(y)  return y    ▷ y replaces xend functionfunction rebalance(n)  update(n)  b ← balance(n)  if b > 1 and balance(n.left) < 0 then n.left ← rotateLeft(n.left)    ▷ Left-Right  if b > 1 then return rotateRight(n)    ▷ Left-Left  if b < −1 and balance(n.right) > 0 then n.right ← rotateRight(n.right)    ▷ Right-Left  if b < −1 then return rotateLeft(n)    ▷ Right-Right  return nend functionfunction insert(n, key)  if n = null then return Node(key)  if key < n.key then n.left ← insert(n.left, key)  else if key > n.key then n.right ← insert(n.right, key)  else return n    ▷ duplicate  return rebalance(n)end functionfunction remove(n, key)  if n = null then return null  if key < n.key then n.left ← remove(n.left, key)  else if key > n.key then n.right ← remove(n.right, key)  else    if n has at most one child then return that child    succ ← n.right    while succ.left ≠ null do succ ← succ.left    n.key ← succ.key    n.right ← remove(n.right, succ.key)  end if  return rebalance(n)end functionfunction search(n, key)  while n ≠ null and n.key ≠ key do n ← n.left if key < n.key else n.right  return nend function

Variables

n=0

Counters

comparisons: 0
rotations: 0

Starting contents0 values

Operations11 / 40

1. insert(10)
2. insert(20)
3. insert(30)
4. insert(25)
5. insert(28)
6. insert(5)
7. insert(4)
8. insert(35)
9. insert(32)
10. delete(20)
11. search(28)

How it works

A self-balancing BST: every node's subtrees differ in height by at most one. After each insert or delete the heights are updated on the way back up, and any node that tips out of balance is fixed with one or two rotations, so every operation stays O(log n).

Complexity

Best: O(log n)
Average: O(log n)
Worst: O(log n)
Space: O(n)

AVL Tree

How it works

Complexity

Search algorithms