An AVL tree is a self-balancing binary search tree where the heights of the two child subtrees of every node differ by at most one. After each insertion or deletion, the tree checks balance factors and performs single or double rotations to restore balance, guaranteeing O(log n) operations in all cases.
struct Node { int val,h; Node *l,*r; Node(int v):val(v),h(1),l(nullptr),r(nullptr){} };
int h(Node* n){return n?n->h:0;}
int bf(Node* n){return n?h(n->l)-h(n->r):0;}
void upd(Node* n){if(n)n->h=1+max(h(n->l),h(n->r));}
Node* rr(Node* y){Node* x=y->l,*T=x->r;x->r=y;y->l=T;upd(y);upd(x);return x;}
Node* lr(Node* x){Node* y=x->r,*T=y->l;y->l=x;x->r=T;upd(x);upd(y);return y;}
Node* bal(Node* n){
upd(n); int b=bf(n);
if(b>1&&bf(n->l)>=0)return rr(n);
if(b>1){n->l=lr(n->l);return rr(n);}
if(b<-1&&bf(n->r)<=0)return lr(n);
if(b<-1){n->r=rr(n->r);return lr(n);}
return n;
}
Node* insert(Node* n,int v){
if(!n)return new Node(v);
if(v<n->val)n->l=insert(n->l,v);
else if(v>n->val)n->r=insert(n->r,v);
return bal(n);
}Every AVL node stores its height. The balance factor of a node is height(left) - height(right). An AVL tree maintains |balance factor| <= 1 for every node. Violation triggers a rotation.
Four rotation cases: LL (right rotate), RR (left rotate), LR (left-right rotate), RL (right-left rotate). Each rotation rearranges 2-3 nodes to restore balance while preserving the BST property.
Insert as in a normal BST, then walk back up the recursion stack checking and fixing balance at each ancestor. At most one rotation (or double rotation) is needed per insertion.
Because the height of an AVL tree with n nodes is at most 1.44 log₂(n+2), all operations are O(log n) in the worst case — unlike regular BSTs which degenerate to O(n).
Quiz coming soon for this algorithm.