jsschools

AVL Tree

A self-balancing BST that maintains a balance factor of {-1, 0, 1} at every node, guaranteeing O(log n) operations.

Spec ↗

Syntax

class AVLNode {
  constructor(val) { this.val = val; this.left = null; this.right = null; this.height = 1; }
}
class AVLTree { insert(val) { ... } delete(val) { ... } search(val) { ... } }

Parameters

NameTypeRequiredDescription
val number Yes The value to store at this node.

Returns

AVLTree — A self-balancing AVL tree instance.

Examples

function height(n) { return n ? n.height : 0; }
function bf(n) { return n ? height(n.left) - height(n.right) : 0; }
function update(n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }

function rotateRight(y) {
  const x = y.left, T2 = x.right;
  x.right = y; y.left = T2;
  update(y); update(x);
  return x;
}
function rotateLeft(x) {
  const y = x.right, T2 = y.left;
  y.left = x; x.right = T2;
  update(x); update(y);
  return y;
}
function balance(n) {
  update(n);
  const b = bf(n);
  if (b > 1) return bf(n.left) >= 0 ? rotateRight(n) : (n.left = rotateLeft(n.left), rotateRight(n));
  if (b < -1) return bf(n.right) <= 0 ? rotateLeft(n) : (n.right = rotateRight(n.right), rotateLeft(n));
  return n;
}
function insert(root, val) {
  if (!root) return { val, left: null, right: null, height: 1 };
  if (val < root.val) root.left  = insert(root.left, val);
  else if (val > root.val) root.right = insert(root.right, val);
  return balance(root);
}
let root = null;
for (const v of [10, 20, 30, 40, 50, 25]) root = insert(root, v);
console.log(root.val, root.height);
Output 
30 3

// Balance factors after inserting sorted values (no skew)
const vals = [1, 2, 3, 4, 5];
let r = null;
for (const v of vals) r = insert(r, v);
console.log('root:', r.val, 'height:', r.height);
Output 
root: 4 height: 3

Notes

| Operation | Best | Avg | Worst | Space | |----------|---------|---------|---------|-------| | Search | O(log n)| O(log n)| O(log n)| O(n) | | Insert | O(log n)| O(log n)| O(log n)| O(n) | | Delete | O(log n)| O(log n)| O(log n)| O(n) | The balance factor (BF) at each node is `height(left) - height(right)`. AVL allows BF ∈ {-1, 0, 1}. After every insert/delete, at most O(log n) rotations are performed to restore the invariant. AVL trees have stricter balance than Red-Black trees, making lookups slightly faster at the cost of more rotations on write-heavy workloads.

See also