# 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