Balanced BSTs and an AVL introduction in Python

Why it matters

A BST is only fast when it is balanced. Every operation you learned in the first three lessons walks one path from the root down, so the cost is the height of the tree. A tree that is balanced has a small height. A tree that is not balanced can be a long chain, and then it is no faster than a plain list. Production libraries use self-balancing trees so that the shape never goes bad, no matter what order the values arrive in. Python's standard library does not include one, so this lesson also shows you a Python tool that gives the same sorted answers for a small amount of data.

This lesson shows you the problem in detail, builds a balanced tree from sorted data, and then introduces the AVL tree, the first self-balancing tree in this course. You will learn the four rotation cases, the code that performs them, and the reason an insert needs at most one fix. By the end you can insert into an AVL tree by hand and read the balance factor of any node.

The problem again

In the first lesson you saw that inserting the values 1 to 7 in increasing order builds a chain. Each new value is larger than every value already in the tree, so it goes to the right of the one before. Here is the tree after all seven inserts.

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7

The height is 7. To search for 7, the walk visits 7 nodes. Searching for 1 is quick, but searching for 7 still walks the entire right side. The shape gives you no help. You have a sorted list with extra links, and the BST advantage is gone.

Compare that with a balanced tree of the same seven values, with 4 at the root and the other values spread evenly:

        4
      /   \
    2       6
   / \     / \
  1   3   5   7

The height is 3. Every value is found in at most 3 steps. The two trees hold exactly the same values, and they differ only in shape, so the shape is what decides the speed. Both trees obey the BST rule, so a correctness test cannot tell them apart. Only a test of speed, or a look at the height, shows the problem.

The everyday version

Think of a bookshelf in a library. If you always add new books at the right end, the shelf quickly becomes a long row that you must walk along to find the newest titles. A librarian who cares about speed keeps the shelf balanced, so that the same number of books sits on either side of the middle. The shelf is then easy to walk. A self-balancing tree does the same job: after each change, it shifts a little to keep the two sides even.

Balanced from sorted data

If you have all the values before you start, you can build a balanced tree directly. The trick is to choose the middle value as the root. The values smaller than the middle go into the left subtree and the values larger go into the right subtree. Then build each half the same way. This is divide and conquer, the idea from the earlier module on that topic, and it runs in O(n) time because each value is placed exactly once.

Here is the method applied to the values 1 to 7.

1. The sorted range is 1 to 7. The middle index is 3, which holds 4. Make 4 the root.
2. The left half is 1, 2, 3. Its middle is 2. Make 2 the left child of 4.
3. Inside that left half, 1 is the left of 2 and 3 is the right of 2.
4. The right half is 5, 6, 7. Its middle is 6. Make 6 the right child of 4.
5. Inside that right half, 5 is the left of 6 and 7 is the right of 6.

The result is the balanced tree from the picture above. Each level of the recursion halves the range, so the height is about log2(n) + 1.

The function works on an index range of a list. The middle is computed as lo + (hi - lo) // 2. Python integers do not overflow, so (lo + hi) // 2 would also work here. The form with lo first is the habit to keep, because languages with fixed-size integers need it.

def from_sorted(a, lo, hi):
    if lo > hi:
        return None
    mid = lo + (hi - lo) // 2
    node = TreeNode(a[mid])
    node.left = from_sorted(a, lo, mid - 1)
    node.right = from_sorted(a, mid + 1, hi)
    return node

The empty range (lo > hi) is the stopping case, and it returns None, which is the empty child. The other lines each place one value and then build the two halves. The program below runs this code on two sorted inputs. The first input has seven values. The second has six, and it shows how the choice of middle affects the root.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def from_sorted(a, lo, hi):
    if lo > hi:
        return None
    mid = lo + (hi - lo) // 2
    node = TreeNode(a[mid])
    node.left = from_sorted(a, lo, mid - 1)
    node.right = from_sorted(a, mid + 1, hi)
    return node
 
 
def height(n):
    if n is None:
        return 0
    return 1 + max(height(n.left), height(n.right))
 
 
n = int(input())
a = [int(x) for x in input().split()][:n]
root = from_sorted(a, 0, n - 1)
print(f"root {root.val}, height {height(root)}")

Type 7 and then 1 2 3 4 5 6 7. The output is:

root 4, height 3

Now type 6 and then 1 2 3 4 5 6. The output is:

root 3, height 3

With six values, the middle index is 2, which holds 3. The left half has two values and the right half has three, so the right side is one level deeper. The height is 3 either way. A balanced tree does not need equal halves. It needs halves that differ in size by at most one, which is what this choice of middle gives.

This method is perfect when all the data is known in advance. A tree that receives a stream of inserts and deletes cannot be rebuilt each time. That is the job of the next section.

The balance factor

To keep a tree balanced while values change, you need a number that says how unbalanced each node is. The usual number is the balance factor. For a node, it is the height of the left subtree minus the height of the right subtree.

• A node with a left subtree of height 2 and a right subtree of height 1 has balance factor 1.
• A node with two subtrees of equal height has balance factor 0.
• A node with a left subtree of height 1 and a right subtree of height 3 has balance factor -2.

An AVL tree is a BST where every node has a balance factor of -1, 0 or 1. The name comes from its inventors, Adelson-Velsky and Landis, who described it in 1962. The rule means that the two sides of any node differ in height by at most one. Such a tree has a height of at most about 1.44 log2(n), which keeps every operation logarithmic even in the worst case.

When an insert or delete makes a balance factor reach 2 or -2, the tree must be repaired. The repair is a rotation.

Rotations: the seesaw

A rotation is a small local change. It moves one node up and one node down, and it keeps the BST order. Picture a seesaw. If one side is too heavy, you slide the pivot toward the heavy side so that the weight evens out. The seesaw is still the same seesaw, but the pivot has moved.

Here is a left rotation at the node 10, which has a right child 20 that has a right child 30. The tree is too heavy on the right.

Before: 10 has right child 20, and 20 has right child 30
 
    10
      \
       20
         \
          30
 
After a left rotation at 10: 20 becomes the root
 
        20
       /  \
     10    30

Check the order after the rotation. The values 10 and 30 are both on the correct side of 20: 10 is smaller, and 30 is larger. Nothing was lost, and the height went from 3 to 2.

A right rotation is the mirror image. It moves the left child up, and it is used when the tree is too heavy on the left.

Inside the code, a rotation changes only a few links. In the left rotation above, the pivot is x, which is 10, and its new root is y, which is 20. The link x.right is set to y.left, which was None here. Then y.left is set to x. The two nodes are updated for height, and y is returned as the new root of this part of the tree.

Why a rotation keeps the order

A rotation must not break the BST rule, and it does not, for a simple reason. Look at the left rotation on 10 and 20 again. Before the rotation, 10 is the parent and 20 is its right child. The subtree between them, which holds all the values larger than 10 and smaller than 20, is the left subtree of 20. After the rotation, that same subtree becomes the right subtree of 10. It still holds values larger than 10 and smaller than 20, so its place in the order has not changed. Only the parent of that subtree changed, and the order is the same.

The same argument works for every rotation. Each subtree that moves keeps the values it held, and each one stays between the same two nodes in sorted order. That is why a rotation changes the shape without changing the inorder walk. You can check this in the program: the four cases end with the same tree. Its preorder is 20 10 30, and its inorder walk is 10 20 30.

The four cases

The tree gets unbalanced at a node in one of four shapes. The shape is named by the path from the unbalanced node down to the new node that caused the problem. A path is written as two letters: L for left and R for right. Here are the four shapes and the fix for each.

The first two cases need one rotation, because the path goes one way. The last two need two rotations. In a left-right shape, the node's left child leans to the right, so a single right rotation would only move the problem. First straighten the child with a left rotation. Then the shape is left-left, and one right rotation finishes the job.

Let us trace each case with the values that cause it. Each one inserts three values into an empty AVL tree. The rebalancing step happens on the third insert.

Left-left. Insert 30, then 20, then 10. After 30 and 20, the root 30 has a left child 20. Inserting 10 makes 20 have a left child 10. The balance factor at 30 is 2. The path is left, left. Rotate right at 30. The root becomes 20, with 10 on the left and 30 on the right.

Right-right. Insert 10, then 20, then 30. The root 10 has a right child 20, and 20 has a right child 30. The balance factor at 10 is -2. Rotate left at 10. The root becomes 20.

Left-right. Insert 30, then 10, then 20. The root 30 has a left child 10, and 10 has a right child 20. The balance factor at 30 is 2. A single right rotation at 30 would lift 10 to the top, and then 10 would still lean right with 30 and 20 piled under it, so the tree would still be lopsided. Instead, first rotate left at 10. That lifts 20 into the left child spot of 30, and now the path is left, left. Rotate right at 30. The root becomes 20, with 10 on the left and 30 on the right.

Right-left. Insert 10, then 30, then 20. The root 10 has a right child 30, and 30 has a left child 20. The balance factor at 10 is -2. Rotate right at 30, so that 20 takes the place of 30 as the right child of 10. Now the path is right, right. Rotate left at 10. The root becomes 20, with 10 on the left and 30 on the right.

Each of the four cases ends with the same tree: root 20, left child 10, right child 30. That is no accident. Each case is a different route to the same balanced shape. The result is always a root with two children whose heights differ by at most one.

The program below runs the four cases and prints the preorder walk after each one. Preorder means node, then left, then right. Every case prints the same walk, because every case ends with the same balanced tree.

class AvlNode:
    def __init__(self, val):
        self.val = val
        self.height = 1
        self.left = None
        self.right = None
 
 
def h(n):
    return 0 if n is None else n.height
 
 
def update(n):
    n.height = 1 + max(h(n.left), h(n.right))
 
 
def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    update(y)
    update(x)
    return x
 
 
def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    update(x)
    update(y)
    return y
 
 
def rebalance(n):
    update(n)
    bf = h(n.left) - h(n.right)
    if bf > 1:
        if h(n.left.left) < h(n.left.right):
            n.left = rotate_left(n.left)
        return rotate_right(n)
    if bf < -1:
        if h(n.right.right) < h(n.right.left):
            n.right = rotate_right(n.right)
        return rotate_left(n)
    return n
 
 
def insert(n, v):
    if n is None:
        return AvlNode(v)
    if v < n.val:
        n.left = insert(n.left, v)
    elif v > n.val:
        n.right = insert(n.right, v)
    else:
        return n
    return rebalance(n)
 
 
def preorder(n, out):
    if n is None:
        return
    out.append(n.val)
    preorder(n.left, out)
    preorder(n.right, out)
 
 
def show(name, values):
    root = None
    for v in values:
        root = insert(root, v)
    out = []
    preorder(root, out)
    print(f"{name} (inserts {values}): " + " ".join(str(v) for v in out) + f" height {root.height}")
 
 
show("left-left", [30, 20, 10])
show("right-right", [10, 20, 30])
show("left-right", [30, 10, 20])
show("right-left", [10, 30, 20])

Its output is:

left-left (inserts [30, 20, 10]): 20 10 30 height 2
right-right (inserts [10, 20, 30]): 20 10 30 height 2
left-right (inserts [30, 10, 20]): 20 10 30 height 2
right-left (inserts [10, 30, 20]): 20 10 30 height 2

All four lines end with the same balanced tree. Each line shows the height 2, which is the height of a three-node tree in this course's counting. The show function prints the list of inserts with {values}, which is how Python shows a list. f"..." is an f-string, so the text inside the braces is replaced by the value of the expression.

The AVL insert in code

The insert function is the one you saw in the first lesson, with two additions. Each node stores its height, and after every recursive insert the function checks the balance and rotates if needed. The code below is the full AVL insert, built from the parts you have already seen.

def insert(n, v):
    if n is None:
        return AvlNode(v)
    if v < n.val:
        n.left = insert(n.left, v)
    elif v > n.val:
        n.right = insert(n.right, v)
    else:
        return n                    # duplicate: nothing changes
    return rebalance(n)             # fix this node on the way back up

The function is recursive, so the rebalance happens on the way back up the path. The insert went down to the new leaf, and each node on that path is checked as the calls return. The first node that is out of balance is the one that matters. Once the rotation at that node is done, the subtree is balanced again and the nodes above it are also balanced, because the height of the subtree is the same as before the insert. That is why one rotation, or one double rotation, is always enough for an insert.

The rebalance function does the work. It first updates the height of the node. Then it computes the balance factor from the heights of the children. If the factor is greater than 1, the left side is too heavy. It then checks whether the left child leans right (the left-right case), and if so, it rotates that child left first. Finally, it rotates right at the node. The right side has the mirror-image code.

The helper h(n) returns 0 for None, so that a missing child counts as height 0. This is what makes a leaf have height 1 and a node with one child have height 2.

Tracing an AVL insert

The best way to see the method work is to follow a single sorted insert. Insert 1, 2 and 3 into an empty AVL tree.

After 1, the tree is one node. After 2, the root 1 has a right child 2. The balance factor of 1 is -1, which is allowed.

After 3, the root 1 has a right child 2, and 2 has a right child 3. The balance factor of 1 is -2. This is the right-right case, so rotate left at 1. The root becomes 2, with 1 on the left and 3 on the right. The tree is perfectly balanced.

Now insert 4. It goes to the right of 2, then to the right of 3. The node 3 now has height 2, while the left child 1 has height 1. At the root 2, the left height is 1 and the right height is 2, so the balance factor is -1. That is allowed, so nothing is rotated.

Insert 5 next. It goes right of 2, right of 3, and right of 4. Now node 3 has a right child 4, and 4 has a right child 5. The balance factor at 3 is -2. This is the right-right case at node 3, so rotate left at 3. The subtree rooted at 3 becomes a subtree rooted at 4, with 3 on the left and 5 on the right. Now the root 2 has a left child 1 (height 1) and a right child 4 (height 2). Its balance factor is -1, so no more repair is needed.

Insert 6 and 7 in the same way, and the tree ends up with root 4. The rotations happen at the lowest unbalanced node each time, and each one moves the tree a step toward balance.

Heights after every insert

The table of heights makes the insert easy to follow. The program below prints the tree after each of the seven inserts. Each node is shown as its value, then its stored height in parentheses, in preorder. The output is the real output of that program.

after 1: 1(1)
after 2: 1(2) 2(1)
after 3: 2(2) 1(1) 3(1)
after 4: 2(3) 1(1) 3(2) 4(1)
after 5: 2(3) 1(1) 4(2) 3(1) 5(1)
after 6: 4(3) 2(2) 1(1) 3(1) 5(2) 6(1)
after 7: 4(3) 2(2) 1(1) 3(1) 6(2) 5(1) 7(1)

Read the step after 3 first. The root is 2 with height 2, the left leaf 1 has height 1, and the right leaf 3 has height 1. The balance factor at 2 is 0. The step after 4 is the first time the root's balance factor is -1, at 2, because its right side (node 3, height 2) is one level taller than its left side (node 1, height 1). That is allowed.

The step after 5 is where a rotation happened. Before the insert of 5, node 3 had height 2. The insert of 5 made the path 2, 3, 4, 5 with heights that would reach a balance factor of -2 at 3, so the rotation at 3 lifted 4 above 3. The output shows the result: 4 is now the subtree root under 2, with height 2, and its children 3 and 5 both have height 1.

The step after 7 has root 4 with height 3. The left subtree of 4 has root 2 with height 2, and the right subtree has root 6 with height 2. Every node in the output has a balance factor of -1, 0 or 1, which you can check by subtracting the right height from the left height at each node.

The program that prints this table is the insert code above with a loop around it. It adds each node's stored height to a list while it walks the tree in preorder, and it prints one line per insert.

Running the AVL insert on input

The program below reads a list of values, inserts them into an AVL tree, and prints the preorder walk and the height. It is the same tree code as the rotation program, with input added.

Type 7 and then 1 2 3 4 5 6 7. The output is:

preorder: 4 2 1 3 6 5 7
height: 3

Now type 7 and then 7 6 5 4 3 2 1. The output is the same, because the AVL tree ends up with the same shape regardless of the order of the sorted run. That property is what you want from a self-balancing tree: the input order no longer decides the speed.

class AvlNode:
    def __init__(self, val):
        self.val = val
        self.height = 1
        self.left = None
        self.right = None
 
 
def h(n):
    return 0 if n is None else n.height
 
 
def update(n):
    n.height = 1 + max(h(n.left), h(n.right))
 
 
def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    update(y)
    update(x)
    return x
 
 
def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    update(x)
    update(y)
    return y
 
 
def rebalance(n):
    update(n)
    bf = h(n.left) - h(n.right)
    if bf > 1:
        if h(n.left.left) < h(n.left.right):
            n.left = rotate_left(n.left)
        return rotate_right(n)
    if bf < -1:
        if h(n.right.right) < h(n.right.left):
            n.right = rotate_right(n.right)
        return rotate_left(n)
    return n
 
 
def insert(n, v):
    if n is None:
        return AvlNode(v)
    if v < n.val:
        n.left = insert(n.left, v)
    elif v > n.val:
        n.right = insert(n.right, v)
    else:
        return n
    return rebalance(n)
 
 
def preorder(n, out):
    if n is None:
        return
    out.append(n.val)
    preorder(n.left, out)
    preorder(n.right, out)
 
 
n = int(input())
values = [int(x) for x in input().split()][:n]
root = None
for v in values:
    root = insert(root, v)
 
out = []
preorder(root, out)
print("preorder: " + " ".join(str(v) for v in out))
print("height: " + str(h(root)))

The shape the program prints for both inputs is 4 2 1 3 6 5 7. In the first lesson, the BST built from the same values in the same order was a chain of height 7. The AVL version has height 3. This is the payoff of the rotations.

Step through the walk above on the balanced tree. Compare its visit order with the preorder printed by the program. Preorder visits the root first, then the whole left side, then the whole right side.

Python has no built-in balanced tree

You rarely write an AVL tree in production. Some languages ship a sorted map built on a balanced tree. Java has TreeMap, which uses a red-black tree, a close relative of AVL with a looser balance rule. Python's standard library has no such class. A dict keeps keys in insertion order, not in sorted order, and it cannot answer "what is the largest key below 35".

For a small amount of data, the bisect module gives the same answers with a sorted list. bisect works on a list that is already sorted. It returns the position where a value would go, in a time that grows with the logarithm of the list length. The price is that an insert into the middle of a list moves the items after it, so inserts cost O(n). That is fine for a few thousand keys, and it is the reason a real sorted map needs a tree.

The program below answers three questions for a small price list. floor returns the largest key that is less than or equal to x. ceiling returns the smallest key that is greater than or equal to x. A None result means there is no such key. The program uses bisect.insort to keep the key list sorted as it reads the data.

Type 4 and then the four pairs 10 apple, 30 pear, 50 plum and 70 fig, one per line. Then type 3 and the three queries 35, 5 and 80, one per line.

import bisect
 
n = int(input())
keys = []
prices = {}
for _ in range(n):
    key_text, name = input().split()
    key = int(key_text)
    bisect.insort(keys, key)
    prices[key] = name
 
q = int(input())
for _ in range(q):
    x = int(input())
    i = bisect.bisect_right(keys, x)
    floor = keys[i - 1] if i > 0 else None
    j = bisect.bisect_left(keys, x)
    ceiling = keys[j] if j < len(keys) else None
    print(f"{x}: floor {floor}, ceiling {ceiling}")
 
print(f"first {keys[0]}, last {keys[-1]}")
print("keys below 50:", [k for k in keys if k < 50])

With that input, the output is:

35: floor 30, ceiling 50
5: floor None, ceiling 10
80: floor 70, ceiling None
first 10, last 70
keys below 50: [10, 30]

The first query, 35, falls between 30 and 50, so the floor is 30 and the ceiling is 50. The query 5 is below every key, so there is no floor, and Python prints None. The query 80 is above every key, so there is no ceiling. The list comprehension [k for k in keys if k < 50] builds the list of keys below 50 in one line.

bisect_right returns the position just after any equal key, so keys[i - 1] is the largest key that is less than or equal to x. bisect_left returns the position of the first key that is greater than or equal to x, so keys[j] is the ceiling. Both functions are the same kind of walk as the BST search, done on an array.

AVL or red-black?

Two self-balancing trees are common in practice, and each one is a good answer to a different question. Both give O(log n) search, insert and delete in the worst case. The table compares them as a learner would use them.

In plain words: an AVL tree spends a little more work on each change, so that each lookup is a little faster. A red-black tree spends less work on each change, and it accepts a slightly taller tree in return. Java chose the second option for TreeMap. Neither choice is wrong. When you need to pick one in an interview, say which one you would use and why, and name the trade-off.

Common mistakes

Mistake 1: forgetting to update heights after a rotation. The rotation moves links, but each node also stores its height. If you skip update(y) and update(x) in the rotation, the heights are wrong, and the balance factors that come after are wrong too. The tree may look right for a short test and then rotate in the wrong place on a longer one. Always update the lower node first, then the upper one, because the upper node's height depends on the lower one.

Mistake 2: rotating the wrong way. A left-heavy node needs a right rotation. Students often mix the two because the names sound alike. A quick check is to ask which child is heavy, then rotate toward the other side. If the left child is heavy, rotate right, which lifts the left child up.

Mistake 3: a single rotation for a left-right shape. A left-right shape looks like a left-left shape from the top, and the balance factor is the same. A single right rotation does not fix it, as the example below shows. Here is a tree with root 30, left child 10 and 20 as the right child of 10, rotated once on the right at 30:

def build_left_right():
    r = AvlNode(30)
    r.left = AvlNode(10)
    r.left.right = AvlNode(20)
    update(r.left)
    update(r)
    return r
 
 
t = rotate_right(build_left_right())
out = []
preorder(t, out)
print(out)

The output is:

[10, 30, 20]

The preorder shows 10 at the top with 30 on its right, and 20 under 30. The balance factor at the root is now -2, so the tree is still lopsided. Look at the child first: if the child leans the other way, rotate the child before rotating the node.

Mistake 4: reading a child that is None. Reading n.left.height when n.left is None stops the program. The message is:

AttributeError: 'NoneType' object has no attribute 'height'

The message says that the value None has no attribute height. The helper h(n) exists to avoid this. Always call h(n.left), not n.left.height. The same care is needed when checking n.left.left and n.left.right in the rebalance code: the rebalance is only entered when n.left is not None, because a balance factor above 1 needs a left child.

Mistake 5: believing a BST is always fast. A plain BST that receives sorted input is a chain. The fix is not to hope for random input. The fix is either to build from sorted data as in this lesson, or to use a self-balancing tree for the inserts.

Mistake 6: a lookup with no answer, used as a number. None is the answer when no key is small enough. If the program does arithmetic with that answer, Python stops with this message:

import bisect
 
keys = [10]
i = bisect.bisect_right(keys, 5)
floor = keys[i - 1] if i > 0 else None
print(floor + 1)

The output is:

TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

The message says that None cannot be added to an integer. Check for None first, and only then use the value as a number.

Debugging walkthrough

Suppose an AVL tree looks wrong after many inserts, and you want to find the node that breaks the rule. Add a checker that walks the whole tree and returns False as soon as one node has a balance factor outside -1 to 1. This is a tool for finding bugs, not part of the insert.

def is_balanced(n):
    if n is None:
        return True
    bf = h(n.left) - h(n.right)
    if bf > 1 or bf < -1:
        return False
    return is_balanced(n.left) and is_balanced(n.right)

Call it after every insert in a test. The first insert that makes it return False is the one to study. Draw the tree just before that insert, and walk through the rebalance by hand. You will usually find either a missing height update or a rotation in the wrong direction. The checker also tells you where to add a print statement, because it names the first bad node.

A second debugging tool is the height itself. Print n.height for each node in the preorder walk. If a parent's height is not one more than its taller child, a height was not updated.

Variations and edge cases

• Inserting a duplicate. The insert returns the same node, so the tree is unchanged. The else branch handles it, and no rebalance is needed.
• Deleting from an AVL tree. Deletion removes a node as in the second lesson, then walks back up the path, rebalancing each node. Unlike insert, deletion can need a rotation at several levels of the path, one for each node that goes out of balance, so it is more work. The rule and the four cases are the same.
• Red-black trees. Java's TreeMap uses this variant. It uses colours and a looser balance rule, which means it rotates less often on inserts and deletes, while search is a little slower than in an AVL tree. Neither is always better; both are O(log n) in the worst case.
• Building from sorted data. The from_sorted function gives a perfectly balanced tree in one pass, which is faster than inserting one by one. Use it when the data is known in advance.
• Very large values or many nodes. A balanced tree's height grows as log2(n), so a tree with a million nodes has a height of about 20, and an AVL tree stays under about 30. Each operation therefore takes about 20 steps even at that size.

Real-world and interview uses

Balanced trees are everywhere that a sorted, changing collection is needed. Databases use balanced trees for indexes, so that a lookup by a key does not scan the whole table. Operating systems use them to track memory regions. Sorted maps in many languages are built on these trees, and their floor and ceiling queries are what a scheduler or a calendar uses to find the next or previous event. In Python the same question is usually answered with bisect on a sorted list, or with a third-party sorted container.

In interviews, two questions come up often. The first is "convert a sorted array into a height-balanced BST", which is the from_sorted function. The answer is O(n) time, O(log n) space for the recursion, and a note that the middle choice keeps the two halves within one level of each other. The second is "explain AVL trees". A good answer names the balance factor, states the rule that it must stay in -1 to 1, describes the four rotation cases in plain words, and says that an insert needs at most one rebalance. Give the cost as O(log n) for search, insert and delete in the worst case, and say that this is the reason for balancing at all.

Practice

1. Insert 10, 20 and 30 into an AVL tree by hand, one at a time. Hint: after 30, the root 10 has balance factor -2 with a right-right shape, so rotate left at 10.

2. A node has a left subtree of height 3 and a right subtree of height 1. What is its balance factor, and does the tree need a fix? Hint: subtract the right height from the left height, then compare with 1.

3. Which rotation fixes the insert sequence 30, 10, 20? Hint: 10 is the left child of 30 and 20 is the right child of 10, so the shape is left-right.

4. Build a balanced BST from the sorted values 2, 4, 6, 8, 10, 12, 14, 16, 18. Write down the root and the height. Hint: the middle of nine values is the fifth one, which is 10.

5. Write count_nodes(n) that returns the number of nodes. Hint: an empty tree has zero nodes, and every other node adds one to the counts of its two subtrees.

def count_nodes(n):
    if n is None:
        return 0
    return 1 + count_nodes(n.left) + count_nodes(n.right)

6. Write is_bst_ordered(n) that checks the BST rule for a plain tree using an inorder walk that stores the previous value. Hint: this is the inorder method from the validation lesson.

prev = None
 
 
def is_bst_ordered(n):
    global prev
    if n is None:
        return True
    if not is_bst_ordered(n.left):
        return False
    if prev is not None and n.val <= prev:
        return False
    prev = n.val
    return is_bst_ordered(n.right)

7. Predict the height after inserting 1, 2, 3, 4 into an AVL tree. Hint: the tree after 3 is perfectly balanced with root 2, and 4 goes under 3.

8. Explain in two sentences why a single rotation is enough after an insert. Hint: the lowest node that is out of balance is fixed, and the height of its subtree goes back to what it was before the insert.

9. Write a function get_height(n) that returns the height and works on None. Hint: the helper already does this, so the function is one line.

def get_height(n):
    return h(n)

10. Use the bisect approach to find the key closest to 42 in the sorted list [10, 40, 45, 60]. Say whether the floor or the ceiling is closer, and what you would answer if the two were at the same distance. Hint: 42 is 2 away from 40 and 3 away from 45, so the nearest is 40, found by the floor.

What you now know

• A BST's speed depends on its height, not only on its values. A chain of n values has height n, and a balanced tree has height about log2(n).
• A balanced tree can be built directly from sorted data by choosing the middle value as the root at each step.
• An AVL tree keeps a balance factor of -1, 0 or 1 at every node, and it uses rotations to repair any node that goes beyond that.
• The four cases are left-left and right-right (one rotation), and left-right and right-left (two rotations). Each one ends with the same balanced shape.
• Python has no built-in balanced tree. For small sorted data, bisect on a list answers floor and ceiling questions, and its inserts cost O(n).