What is an AVL tree?

  • An AVL tree is a self-balancing data structure that adheres to the same guidelines as a Binary Search Tree. However, the AVL tree has additional properties:
    • Height of left and right subtree can differ no greater than 1
  • BalanceFactor(X) = Height(RightSubtree(x) - Height(LeftSubtree(X))



Let x be our offending node.

If the tree is left-heavy If the left child of x is right-heavy perform a LR @ x’s left child. perform a RR @ x else perform a RR @ x

If the tree is right-heavy If the right child of x is left-heavy perform a RR @ x’s right child perform a LR @ x else perform a LR @ x

Code Implementation:

node *rotateLeft(node *x)
	node *newRoot, *orphan;

	// x's right child becomes the new root. 
	newRoot = x->right 

	// x's right child is about to take x as its left child.
	// as such we must store x's left child as it is orphaned
	orphan = newRoot->left;

	// x moves down and to the left to become the left child of the new root. 
	newRoot->left = x; 

	// Now x, having lost its right child, adopts any orphan that might exist. Notice that if an oprhan is NULL, we end up setting x's right child to NULL. 
	x->right = orphan; 

	return newRoot; 


  1. Insert BST Style.
  2. Fix bad balance-factors as we go.


  1. Delete node BST Style.
  2. Perform rotations to fix bad balance-factors.


  1. Search for the value BST Style.

Runtime considerations

Insertion: O(log n)