Unit 25: Balanced Trees

Keeping a tree from leaning.

Unit 25 of 31 in Python for kids. Its 4 lessons are When a Tree Falls Over, Straightening It Out, Fixing As You Go and Balance Master — below is everything each one explains, and a question or two from it to try.

Every sample on this page was run through real Python before it shipped, and prints exactly what it says it prints.

This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.

📉 When a Tree Falls Over

Sorted input ruins a search tree

Insert numbers already in order and every one goes right. The tree becomes a straight line — a linked list wearing a tree costume — and the fast search is gone.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

leaning = None
for n in [1, 2, 3, 4, 5]:
    leaning = insert(leaning, n)

balanced = None
for n in [3, 2, 4, 1, 5]:
    balanced = insert(balanced, n)

print(height(leaning))
print(height(balanced))

It prints

5
3

Height is the thing that matters

A search never takes more steps than the tree is tall. Keeping the tree short *is* keeping it fast — so the whole job is stopping it from leaning.

Python

print("10 values, leaning : up to 10 steps")
print("10 values, balanced: up to 4 steps")
print("1000 values, balanced: up to 10 steps")

It prints

10 values, leaning : up to 10 steps
10 values, balanced: up to 4 steps
1000 values, balanced: up to 10 steps

Measuring the lean

The balance factor of a node is the height of its left side take away the height of its right. 0 means even, and anything beyond -1 or 1 means that node has tipped too far.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

def balance(node):
    return height(node.left) - height(node.right)

root = Node(3)
root.left = Node(2)
root.left.left = Node(1)

print(balance(root))
print(balance(root.left))

It prints

2
1

Try it yourself

Why is a tall thin tree slow?

It uses more memory
A search has to walk down nearly every node, instead of throwing half away each step
It cannot be sorted
It is not slow

A node has a balance factor of 2. What does that mean?

It has two children
Its left side is two taller than its right — it is leaning left too far
It holds the value 2
It is perfectly balanced

Answer them in the app

🔄 Straightening It Out

Lifting the middle one up

Three nodes in a line can be re-hung so the middle becomes the top. Nothing is added or removed — only three pointers change, and the BST rule still holds.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

# 3 -> 2 -> 1 leaning left
root = Node(3)
root.left = Node(2)
root.left.left = Node(1)

new_root = root.left
root.left = new_root.right
new_root.right = root

print(new_root.value)
print(new_root.left.value, new_root.right.value)

It prints

2
1 3

That is a rotation

Those three lines are a right rotation, and they are the whole trick. Written as a function it works on any node that is leaning left.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

def rotate_right(node):
    new_root = node.left
    node.left = new_root.right
    new_root.right = node
    return new_root

root = Node(5)
root.left = Node(3)
root.left.left = Node(1)

root = rotate_right(root)
print(root.value, root.left.value, root.right.value)

It prints

3 1 5

And the mirror image

A left rotation is exactly the same with left and right swapped, for a node leaning right.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

def rotate_left(node):
    new_root = node.right
    node.right = new_root.left
    new_root.left = node
    return new_root

root = Node(1)
root.right = Node(3)
root.right.right = Node(5)

root = rotate_left(root)
print(root.value, root.left.value, root.right.value)

It prints

3 1 5

Try it yourself

What does a rotation change?

The values in the tree
Only which node points at which — the values and their order stay the same
The number of nodes
Nothing at all

What does this print?

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

def rotate_right(node):
    new_root = node.left
    node.left = new_root.right
    new_root.right = node
    return new_root

r = Node(10)
r.left = Node(5)
r.left.left = Node(2)
r = rotate_right(r)
print(r.value)

Answer them in the app

🩹 Fixing As You Go

An AVL tree checks itself after every insert

An AVL tree is a BST that, every time you add something, looks at the balance on the way back up and rotates whenever a node has tipped past 1.

Python

print("insert -> walk back up -> check balance -> rotate if needed")

It prints

insert -> walk back up -> check balance -> rotate if needed

The simple lean: one rotation

When a node leans left and its left child also leans left, one right rotation fixes it. This is the "left-left" case.

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

def height(n):
    return 0 if n is None else 1 + max(height(n.left), height(n.right))

def rotate_right(node):
    new_root = node.left
    node.left = new_root.right
    new_root.right = node
    return new_root

root = Node(3)
root.left = Node(2)
root.left.left = Node(1)
print(height(root))
root = rotate_right(root)
print(height(root))

It prints

3
2

The awkward lean: two rotations

When a node leans left but its child leans *right*, one rotation is not enough. Rotate the child left first to make it a simple lean, then rotate the node right. This is "left-right".

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

def rotate_left(node):
    r = node.right
    node.right = r.left
    r.left = node
    return r

def rotate_right(node):
    l = node.left
    node.left = l.right
    l.right = node
    return l

# 3 leans left, its child 1 leans right
root = Node(3)
root.left = Node(1)
root.left.right = Node(2)

root.left = rotate_left(root.left)
root = rotate_right(root)
print(root.value, root.left.value, root.right.value)

It prints

2 1 3

Try it yourself

A node leans left, and its left child leans right. What is needed?

One right rotation
Rotate the child left, then the node right
One left rotation
Nothing

Answer it in the app

🏆 Balance Master

Try it yourself

What does this print?

Python

class Node:
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

def height(n):
    return 0 if n is None else 1 + max(height(n.left), height(n.right))

r = Node(5)
r.left = Node(3)
r.left.left = Node(1)
print(height(r.left) - height(r.right))

Answer it in the app