Summary - AVL tree
- Algorithms course
- Intermediate
- Lesson 36/80
- 4 min
Reinforce AVL logic with a mini task.
Summary - AVL tree
AVL: |bf| ≤ 1 at every node. When balance breaks a rotation (right, left, double) fixes it. Insert/delete/search are always O(log n).
Four cases: left-left (right), right-right (left), left-right (double), right-left (double). Rotation is O(1), BST property preserved.
AVL is ideal for frequent search and rare insert; for frequent insert red-black trees are preferred.
Practice Summary: AVL height
Write height(node). In AVL height ≤ 1.44 log n. Print 1 with root = Node(1); root.left = Node(2); print(height(root)).
Starter code
def height(node):
# HeightSample solution
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def height(node):
# Height
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
root = Node(1)
root.left = Node(2)
print(height(root))Expected output
1
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - AVL tree: match the terms
| Term | Meaning |
|---|---|
Balance |
|bf| ≤ 1 |
Left-left |
Right rotate |
Right-right |
Left rotate |
Cost |
O(log n) |
2 Balance factor bound
Question
|bf| ____ 1
Answer
|bf| <= 1Explanation: <= is right.
3 When is AVL preferred?
- Frequent search, rare insert Correct answer
- No insert at all
- Always
- Frequent insert, rare search
Explanation: Frequent search, rare insert