AVL Trees
This page will cover the basics on the AVL Tree
The AVL is a type of
Binary Search Tree
Insertion Steps
- Use regular BST insertion
- Check if out of balance (Balance Factor), rebalance if skewed
What is Balance Factor?
- Balance Factor (BF) = height(left subtree) - height(right subtree)
- For a node to be balanced, its |BF| must be less than two
- A positive BF means it has more nodes to the left, vice versa
- A tree is "balanced" if and only if every node follows the BF rule
How do I repair the tree?
Pick three nodes
- The Unbalanced Node
- Child of Unbalanced Node
- Child of the Child
Follow the path to the added node when choosing these three