AVL Trees

What is an AVL Tree?

An AVL Tree is a self-balancing Binary Search Tree (BST) that uses rotations to keep balance. It determines whether to use a rotation if a given node has an invalid balance factor, which is an additional property that AVL Tree's have

Balance Factor

For any node v, the balance factor is given by: balance (v) = height (left subtree) - height (right subtree)

• balance (v) within {-1,0,1} indicate v is balanced
• balance (v) < -1 indicate that the left subtree is smaller than right subtree
• balance (v) > 1 indicate that the left subtree is larger than right subtree
• A tree is balanced if |balance(v)| <= 1

Diagram

For an AVL Tree Visualization Click Here