Balanced tree

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.

Exercise 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)).

Show example 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))

Test yourself

What must the balance factor be in AVL?
- -2 or +2
- -1, 0 or +1
- 0 only
- any value
Show answer

-1, 0 or +1 — -1, 0 or +1

Balance factor

bf = height(node.left) - height(node.____)

Show answer

bf = height(node.left) - height(node.right)

Balanced tree: match the terms

bf = 0

Balanced
bf = +2

Left-heavy
bf = -2

Right-heavy
|bf| > 1

Rotate

Next lesson: Rotation

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies