Overview of AVL Trees:

AVL stands for Adelson-Velsky and Landis (the people who created it), and is a self balancing binary tree.

• Utilizes balance factor, or bf
• bf = height of left subtree - height of right subtree
• A node is balanced if the absolute value of bf is less than 2
• A tree is balanced if every node in the tree is balanced

Insertion Algorithm Steps:

1. Insert new value using regular BST algorithm
2. Recompile balance factor of every node from new node to oldest parent
3. Then, if the tree is unbalanced, align nodes for the appropriate rotation if needed
4. Rotate the upper two nodes of the alignment in the balancing direction

Learn more