Balanced tree
- Algorithms course
- Intermediate
- Lesson 33/80
- 4 min
An AVL tree keeps height difference at most 1.
Balanced tree
An AVL tree is a BST where the difference in height between left and right subtrees (the balance factor) is at most 1 at every node. This provides automatic balance.
The balance factor is height(left) - height(right). It must be -1, 0 or +1. Otherwise a rotation fixes it.
With AVL, search, insert and delete are always O(log n); the O(n) worst case of an unbalanced BST is avoided.
Balance factor computation
For each node the balance factor is bf = height(left) - height(right). After insert and delete this value may change.
If bf > 1 the tree is left-heavy, if bf < -1 right-heavy. These cases require a rotation.
The balance factor shows at a glance whether the tree is skewed; it is the key indicator of AVL.
Practice Balance factor
Write balance_factor(node). height(left) - height(right). 0 if None. Print 1 with root = Node(1); root.left = Node(2); print(balance_factor(root)).
Starter code
def balance_factor(node):
# Balance factorSample solution
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def balance_factor(node):
# Balance factor
if node is None:
return 0
return height(node.left) - height(node.right)
root = Node(1)
root.left = Node(2)
print(balance_factor(root))Expected output
1
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What must the balance factor be in AVL?
- -2 or +2
- -1, 0 or +1 Correct answer
- 0 only
- any value
Explanation: -1, 0 or +1
2 Balance factor
bf = height(node.left) - height(node.____)bf = height(node.left) - height(node.right)Explanation: right is right.
3 Balanced tree: match the terms
| Term | Meaning |
|---|---|
bf = 0 |
Balanced |
bf = +2 |
Left-heavy |
bf = -2 |
Right-heavy |
|bf| > 1 |
Rotate |