AVL tree

O(log n)

An AVL tree is a self-balancing binary search tree. It stores a height at every node and, after inserting, walks back up to the root checking each node's balance factor — the height of its left subtree minus its right. If that ever exceeds 1, the node is too lopsided and a rotation fixes it: a single rotation for the LL or RR cases, a double (rotate the child first) for LR or RL. These local restructurings keep the whole tree's height within ~1.44·log₂(n), so search, insert, and delete are all guaranteed O(log n) — unlike a plain BST, which degenerates into an O(n) chain on sorted input. Watch the tree snap back into balance as each value goes in.

Binary search tree
Press ▶ to run
Edit the input and press Play

How it works

  1. Insert the value like an ordinary BST, remembering the path down.
  2. Walk back up, updating each ancestor's height.
  3. Where a node's subtrees differ in height by more than one, rotate to rebalance.
  4. LL/RR need one rotation; LR/RL rotate the child first, then the node.

Pseudocode

1avlInsert(v):                       # O(log n)2  insert v like a normal BST, remembering the path3  walk back up the path, updating heights:4    balance = height(left) − height(right)5    if balance > 1:  rotate right (LL), or left-then-right (LR)6    if balance < −1: rotate left (RR), or right-then-left (RL)7  → height stays O(log n), so search never degrades