BST search and insert

A sorted list finds a key fast with binary search, but inserting a key moves everything after it. A hash table inserts fast, but keeps no order. A binary search tree keeps its keys in order and can also insert quickly, as long as it stays short.

The search tree rule

A binary search tree (BST) is a binary tree with keys in its nodes that obeys one rule at every node:

The rule is about whole subtrees, not just children. In the tree from lesson 1, 7 is in the left subtree of 8, so 7 must be smaller than 8, even though 7 is far below it. Practice TREE-P3 tests exactly this point.

A useful fact follows: an in-order walk of a BST gives the keys in increasing order. Proof by induction: in-order lists the left subtree (sorted, by induction, and all smaller than the root), then the root, then the right subtree (sorted, and all bigger). Joined, that is sorted. So a BST is a sorted list stored as a tree. Keys are usually all different; if a tree must hold repeats, pick one side for them (say, equal keys go right) and keep to it.

Search

At each node, compare the key you want with the node’s key. If they are equal, you are done. If yours is smaller, it can only be in the left subtree; if bigger, only in the right. Either way, one whole subtree is ruled out, as in binary search. Step through a search, then an insert:

def search(root, key):
    node = root
    while node is not None and node.value != key:
        node = node.left if key < node.value else node.right
    return node                     # the node holding key, or None

The smallest key is found by going left until there is no left child; the largest, by going right. All three walk one path down from the root, so they cost O(h), where h is the height.

Insert

To insert a key, search for it. If it is already there, stop. Otherwise the search ends by stepping off the tree, onto a missing child. That empty place is exactly where the key belongs, so a new leaf goes there. Nothing else in the tree moves.

def insert(root, key):
    new = TreeNode(key)
    if root is None:
        return new                  # the new node is the whole tree
    node = root
    while True:
        if key == node.value:
            return root             # already there
        side = 'left' if key < node.value else 'right'
        child = getattr(node, side)
        if child is None:
            setattr(node, side, new)
            return root
        node = child

getattr(node, side) reads the attribute whose name is in the string side, and setattr sets it. They let one piece of code handle both directions. Insert also walks one path: O(h).

Everything depends on the height

The third variant of the figure inserts 1 to 6 in order. Each new key is the biggest so far, so it goes right at every node, and the tree becomes a path of height n − 1. Then search and insert cost O(n), no better than a plain list. Sorted input, which is common in practice, is the worst case.

With keys inserted in a random order, the tree is short on average: a node’s expected depth is about 2 ln n, which is about 1.39 log₂ n, and the expected height is about 4.3 ln n. (Here ln n is the natural logarithm, the power you raise e ≈ 2.718 to in order to get n.) For a million keys, that is a typical depth of about 28 and a height of about 50. But you rarely control the order of the input. The BALT station shows trees that rebalance themselves, keeping h = O(log n) whatever the order.

Here k is the number of keys reported. A BST is the only one of the three that is fast at everything, as long as it is balanced. Choose a hash table when you only need to find keys, and a balanced tree when order matters too.