11.1.1 Recursive search and insert

Bot searching and insertion can be implemented as recursive function too, and it is instructive to see how to to that. And since we showed the set operations contains and add above, we will show how to implement recursive versions of the map operations get and put.

datatype BSTMap implements Map:
    ...
    get(key):
        return getHelper(root, key)

    getHelper(node, key):
        if node is null:
            return null
        else if key < node.key:
            return getHelper(node.left, key)
        else if key > node.key:
            return getHelper(node.right, key)
        else if key == node.key:
            return node.value

datatype BSTMap implements Map:
    ...
    put(key, value):
        root = putHelper(root, key, value)

    putHelper(node, key, value):
        if node is null:
            size = size + 1
            return new BSTNode(key, value)
        else if key < node.key:
            node.left = putHelper(node.left, key, value)
        else if key > node.key:
            node.right = putHelper(node.right, key, value)
        else if key == node.key:
            node.value = value
        return node

11.1.2 Removing from a BST

Removing a node from a BST is a bit trickier than inserting a node, but it is not complicated if all of the possible cases are considered individually. Before tackling the general node removal process, we need a useful companion method, largestNode, which returns a pointer to the node containing the maximum value in a subtree.

function largestNode(node):
    while node.right is not null:
        node = node.right
    return node

This time we will show a recursive implementation of remove. For this we need a recursive helper function which we initially call with the root of the tree.

datatype BSTMap:
    ...
    remove(key):
        root = removeHelper(root, key)

Now we are ready for the removeHelper method. Removing a node with given key value $R$ from the BST requires that we first find $R$ and then remove it from the tree. So, the first part of the remove operation is a search to find $R$. Once $R$ is found, there are several possibilities. If $R$ has no children, then $R$’s parent has its pointer set to null. If $R$ has one child, then $R$’s parent has its pointer set to $R$’s child. The problem comes if $R$ has two children. One simple approach, though expensive, is to set $R$’s parent to point to one of $R$’s subtrees, and then reinsert the remaining subtree’s nodes one at a time. A better alternative is to find a value in one of the subtrees that can replace the value in $R$.

Thus, the question becomes: Which value can substitute for the one being removed? It cannot be any arbitrary value, because we must preserve the BST property without making major changes to the structure of the tree. Which value is most like the one being removed? The answer is the least key value greater than the one being removed, or else the greatest key value less than (or equal to) the one being removed. If either of these values replace the one being removed, then the BST property is maintained.

When duplicate node values do not appear in the tree, it makes no difference whether the replacement is the greatest value from the left subtree or the least value from the right subtree. If duplicates are stored in the left subtree, then we must select the replacement from the left subtree. To see why, call the least value in the right subtree $L$. If multiple nodes in the right subtree have value $L$, selecting $L$ as the replacement value for the root of the subtree will result in a tree with equal values to the right of the node now containing $L$. Selecting the greatest value from the left subtree does not have a similar problem, because it does not violate the Binary Search Tree Property if equal values appear in the left subtree.

The code for removal is shown here. Note that the helper function returns the updated subtree, and we have to make sure to update the child pointers to this updated tree.

    removeHelper(node, key):
        if node is null:
            return null
        else if key < node.key:
            node.left = removeHelper(node.left, key)
            return node
        else if key > node.key:
            node.right = removeHelper(node.right, key)
            return node
        else if key == node.key:
            if node.left is null:
                size = size - 1
                return node.right
            else if node.right is null:
                size = size - 1
                return node.left
            else:
                predecessor = largestNode(node.left)
                node.key = predecessor.key
                node.value = predecessor.value
                node.left = removeHelper(node.left, predecessor.key)
                return node

datatype BSTMap:
    ...
    remove(key):
        parent = null
        node = root
        while node is not null:
            parent = node
            if key < node.key:
                node = node.left
            else if key > node.key:
                node = node.right
            else: // key == node.key
                break  // we found the key so break out of the loop
        if node is null:
            return  // the key is not in the tree, so do nothing

        // node to be deleted has at most one child
        if node.left is null or node.right is null:
            // newNode will replace the node to be deleted
            if node.left is null:
                newNode = node.right
            else: // node.right is null
                newNode = node.left

            if parent is null:
                root = newNode  // the node to be deleted is the root, so update the root
            else if node == parent.left:
                parent.left = newNode  // node is a left child, so make newNode a left child
            else: // node == parent.right
                parent.right = newNode  // node is a right child, so make newNode a right child

            node = None

        // node to be deleted has two children
        else:
            predecessorParent = null
            predecessor = node.left
            while predecessor.right is not null:
                predecessorParent = predecessor
                predecessor = predecessor.right

            node.key = predecessor.key
            node.value = predecessor.value

            if predecessorParent is null:
                node.left = predecessor.left
            else:
                predecessorParent.right = predecessor.left

11.1.3 Analysis

The cost for contains, get, add, and put is the depth of the node found or inserted. The cost for remove is the depth of the node being removed, or in the case when this node has two children, the depth of the node with smallest value in its right subtree. Thus, in the worst case, the cost for any one of these operations is the depth of the deepest node in the tree. This is why it is desirable to keep BSTs balanced, that is, with least possible height. If a binary tree is balanced, then the height for a tree of $n$ nodes is approximately $\log n$. However, if the tree is completely unbalanced, for example in the shape of a linked list, then the height for a tree with $n$ nodes can be as great as $n$. Thus, a balanced BST will in the average case have operations costing $O(\log n)$, while a badly unbalanced BST can have operations in the worst case costing $O(n)$. Consider the situation where we construct a BST of $n$ nodes by inserting records one at a time. If we are fortunate to have them arrive in an order that results in a balanced tree (a “random” order is likely to be good enough for this purpose), then each insertion will cost on average $O(\log n)$, for a total cost of $O(n \log n)$. However, if the records are inserted in order of increasing value, then the resulting tree will be a chain of height $n$. The cost of insertion in this case will be $\sum_{i=1}^{n} i \in O(n^2)$.

Traversing a BST costs $O(n)$ regardless of the shape of the tree. Each node is visited exactly once, and each child pointer is followed exactly once. For example, if we want to print the nodes in ascending order we can perform an inorder traversal (Section 8.4), which then will take time linear in the size of the tree.

While the BST is simple to implement and efficient when the tree is balanced, the possibility of its being unbalanced is a serious liability. There are techniques for organising a BST to guarantee good performance. Two examples are the AVL tree (see Section 11.3) and the splay tree (see Section 11.4). There also exist other types of search trees that are guaranteed to remain balanced, such as the red-black tree or the 2-3 Tree.

11.1.4 Guided information flow

When writing a recursive method to solve a problem that requires traversing a binary tree, we want to make sure that we are visiting the required nodes (no more and no less).

So far, we have seen several tree traversals that visited every node of the tree. We also saw the BST search, insert, and remove routines, that each go down a single path of the tree. Guided traversal refers to a problem that does not require visiting every node in the tree, though it typically requires looking at more than one path through the tree. This means that the recursive function is making some decision at each node that sometimes lets it avoid visiting one or both of its children. The decision is typically based on the value of the current node. Many problems that require information flow on binary search trees are “guided” in this way.