Binary search trees

Building, inserting and searching, O(log n) against O(n), trees stored in arrays, and deletion in outline.

A4.6Trees and graphsA level30 min

At GCSE, binary search needed a sorted list. A sorted list is quick to search but slow to change: inserting an item in the middle means shifting everything after it along. A binary search tree keeps data in order and also lets new items go straight in, and it is the starting point for the search trees that databases and programming language libraries use to keep ordered collections.

The rule

A binary search tree (BST) is a binary tree in which, for every node:

• every key in its left subtree is smaller than the node's key, and
• every key in its right subtree is larger (or equal, if duplicates are allowed and sent right).

The rule holds at every node, for the whole subtree, not only between a node and its two children.

Building a tree by inserting

To insert a key, start at the root. If the key is smaller than the node's key, go left; otherwise go right. Repeat until the way you want to go is empty, and put the new node there. BugBot's camera saw markers in the order 17, 8, 31, 4, 12, 23, 40, 10, and each id was inserted as it was seen:

Inserting 10, the last key: 10 is less than 17, so go left to 8. 10 is more than 8, so go right to 12. 10 is less than 12 and 12 has no left child, so 10 becomes the left child of 12.

The first key inserted is always the root, and the shape of the tree depends on the order the keys arrive in.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

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

def insert(node, key):
    """Insert key into the subtree at node, and return that subtree's root."""
    if node is None:
        return Node(key)                          # an empty place: the new node goes here
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    return node

def search(node, key):
    """How many keys are compared before key is found, or None if it is not there."""
    compared = 0
    while node is not None:
        compared = compared + 1
        if key == node.key:
            return compared
        if key < node.key:
            node = node.left
        else:
            node = node.right
    return None

root = None
for marker in [17, 8, 31, 4, 12, 23, 40, 10]:
    root = insert(root, marker)

for target in [23, 10, 25]:
    print("search", target, "->", search(root, target))

Run this in the simulator

Searching

A search follows exactly the path an insert would. Compare the target with the node: if they are equal, stop; if the target is smaller, go left; if larger, go right. If the way is empty, the key is not in the tree. Every comparison rules out a whole subtree.

Searching for 25 follows the same path, then goes right from 23 into an empty place: not found, after 3 comparisons.

How fast is it?

A search makes at most one comparison per level, so at most the height of the tree plus one. In a balanced tree every level is as full as it can be, and a balanced tree of n keys has a height of about log₂ n. Searching it is O(log n): a balanced tree of 1,000,000 keys needs at most 20 comparisons.

The catch is the order of insertion. Insert keys that are already in order and every new key goes right: the tree is degenerate, no better than a linked list, and search is O(n).

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

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

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

def height(node):
    """Edges on the longest path down from node; -1 for an empty tree."""
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

in_order = None
for k in range(1, 16):
    in_order = insert(in_order, k)

balanced = None
for k in [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]:
    balanced = insert(balanced, k)

print("15 keys inserted in order: height", height(in_order))
print("15 keys, middle first:     height", height(balanced))

Run this in the simulator

The same 15 keys give a height of 14 or of 3: a worst-case search of 15 comparisons or 4. Self-balancing trees, such as AVL trees and red-black trees, rearrange nodes as keys are inserted so the height stays close to log₂ n; they are beyond the A level specifications, but they are what real libraries use.

A tree in arrays

Exam questions often store a binary tree in arrays, or an array of records, where each pointer is an array index and a special value such as -1 means "no child". Here is the marker tree, with the nodes in the order they were inserted:

The root is at index 0. To go left from 12, at index 4, follow its left pointer to index 7, which holds 10. Inserting a key writes it into the next free row with -1 in both pointers, then changes one pointer in its parent. Nothing else moves, which is the whole advantage over a sorted array.

Deleting, in outline

Deleting is harder than inserting, because the tree must still obey the rule afterwards. There are three cases:

1. A leaf, such as 10: remove it and set its parent's pointer to null.
2. A node with one child, such as 12, whose only child is 10: point the parent straight at the child. 8's right pointer now leads to 10.
3. A node with two children, such as the root, 17: find its in-order successor, the smallest key in its right subtree (go right once, then left as far as possible: 31, then 23). Copy 23 into the root, then delete the old 23 from the right subtree, which is always case 1 or case 2. The new root is 23, with 8 on its left and 31 on its right. Using the largest key in the left subtree (the in-order predecessor) works equally well.

In array form a deleted row can be kept on a list of free rows and reused by the next insert.

Task: a search tree in arrays

Store a binary search tree in three lists that grow together: key, left and right. A node is an index into them: key[i] is its key, and left[i] and right[i] hold the indexes of its children, or -1 for no child. The root is index 0. Write insert(k) that appends k as a new node with -1 in both pointers and links it into the tree, sending a key left when it is smaller than a node's key and right otherwise. Insert every key in KEYS, in order. Print left: followed by the values in left separated by single spaces, then right: and the values in right the same way. Then write search(k), which walks down from the root. Print search 45: followed by every key it compared, separated by single spaces, then found or not found, and the same for 55.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

KEYS = [50, 30, 70, 20, 40, 60, 80, 35, 45, 65]
key = []
left = []
right = []

def insert(k):
    key.append(k)
    left.append(-1)
    right.append(-1)

Challenges

1. Insert KEYS in ascending order instead. What do left and right look like, and how many keys does search(80) compare?
2. Write smallest() that follows left pointers from the root until it cannot go further. Why must that be the smallest key?
3. On paper, delete 30 from the task's tree using its in-order successor, and write out the three lists afterwards.