Adelson-Velsky and Landis Tree (AVL Tree)

• self-balancing binary tree
• uses rotations to maintain balance
• goal: keep height of trees growing in O(log N)

AVL Tree Operations

AVL Tree Inserion

• Insert new key using regular BST insertion algorithm
• Check if tree is out of balance, and rebalance if it is

Balance Factor

• bf = height(left_substree) - height(right_subtree)
• a node is balance if |bf| < 2
• sign tells us direction of inbalance
• a tree is balanced if every node in the tree is balanced

Rebalance

• start from the inserted node, go upwards until hits the first unbalanced node, then go down 2 steps towards the inserted node (3 rotation nodes)
• rotate the three nodes according to their parent-child relations

For more information, please check this website:AVL-Tree