Successor and deletion

Finding the next bigger key, and deleting a key, are the two harder jobs in a search tree. They are linked: the hard case of deletion is solved by the next bigger key, called the successor.

Smallest, largest, next

In a BST, the smallest key is at the end of the path that always goes left, and the largest at the end of the path that always goes right. The successor of a key is the next bigger key in the tree: the key that comes right after it in in-order. The predecessor is the next smaller one.

def smallest(node):
    while node.left is not None:
        node = node.left
    return node

Finding the successor

There are two cases, depending on whether the node has a right subtree.

1. It has a right subtree. Every key bigger than the node, and close to it, is in there. The successor is the smallest key in the right subtree: go right once, then left as far as possible. In the lessons’ tree, the successor of 3 is 4 (right to 6, then left to 4).
2. It has no right subtree. Then the successor is above it: the nearest ancestor that the node is in the left subtree of. In the tree, 7 has no right child. Going up, 7 is right of 6, and 6 is right of 3, but 3 is left of 8. So the successor of 7 is 8.

Without parent links, case 2 is found by searching from the root and remembering the last node where the search went left:

def successor(root, key):
    best, node = None, root
    while node is not None:
        if key < node.value:
            best = node             # a candidate; look for a smaller one
            node = node.left
        else:
            node = node.right
    return best                     # None if key is the largest

This version handles both cases at once, and even works for a key that is not in the tree. Each step goes one level down: O(h).

Deleting: three cases

First find the node, keeping track of its parent. Then what you do depends on how many children the node has. Step through all three:

• No children: remove it, by setting the parent’s link to None.
• One child: the child takes the node’s place. Link the parent straight to the child. The child’s whole subtree was on the correct side of the parent before, and still is.
• Two children: the node cannot just be cut out, since it has two subtrees to hand on and only one place to put them. Instead, copy its successor’s key into it, and delete the successor’s old node.

Why is the two-children case correct, and why does it end?

• The successor s is the smallest key in the right subtree. So s is bigger than every key in the left subtree (they are all smaller than the deleted key), and smaller than every other key in the right subtree. Putting s in the node keeps the rule.
• The successor’s node has no left child: a left child would be an even smaller key in the right subtree. So removing it is one of the two easy cases. There is no chain of further deletions.

Using the predecessor (the largest key in the left subtree) works just as well. Practice TREE-P4 asks for the successor so that the tests can check one exact shape. Some libraries switch between the two, so that many deletions do not make one side of the tree lopsided.

Sorted containers in Python

Python has no search tree in its standard library. For ordered data, the usual tools are a sorted list kept in order with the bisect module (BSRC), and heapq when you only need the smallest item (HEAP station). Inserting into a sorted list is O(n), but the moving is done in C, so it is fast for lists of up to about a million items.

The widely used third-party package sortedcontainers offers SortedList, SortedDict and SortedSet. Inside, it is a list of sorted lists, not a tree, and it is often faster than a tree in Python. Other languages ship balanced trees: Java’s TreeMap and C++’s std::map are red-black trees (BALT station).