Let's implement a Binary Search Tree, Part III

on Let's Implement, C#

For part one, see Let's implement a Binary Search Tree

For part two, see Let's implement a Binary Search Tree, Part II

At this point in the series, we've defined our base tree structure and node structure, and implemented the necessary methods to implement additions to our tree and searches on our tree. (see Part I or Part II for a code listing),

Let's implement deletion.

At first blush, this might not seem to be a big deal, but in fact deletion in a binary search tree is a bit more involved that the other operations we've looked at to this point. Each node in our tree can have two children, but only one parent; therefore, in the case where the node we want to delete has multiple children, we've got a problem. Consider the following tree:

Deletion Tree

Note that in our implementation, left values are always increasing in value, while right values are always decreasing in value from any node. For example, consider node 15 - we know by definition, that no values larger than 15 will exist on the right side of the subtree formed by node 15's children; we also know that no values lower than 15's parent will exist on the right side 15's node. By definition, node 15's right side children must be less than 15, greater than 10, and less than the node 15's left side node (20).

As a result, we'll find the smallest value on the left side of node 15's children, and use that as our replacement node. The smallest value on the left side of the node will maintain our desired properties of our tree.

public Node FindMinimum()
{
    return null == Left ? this : Left.FindMinimum();
}

Now that we can find the minimum value node for any subtree, let's implement deletion.

First up, let's handle deletion in the tree itself.

public bool Remove(int key)
{
    bool returnValue;

    if (null == _root)
        returnValue = false;
    else if (_root.Key == key)
    {
        Node temporaryRoot = new Node { Left = _root };

        // Parent the current root node by our temporary root

        returnValue = _root.Remove(key, temporaryRoot);

        _root = temporaryRoot.Left;
    }
    else
    {
        returnValue = _root.Remove(key, null);
    }

    return returnValue;
}   

Now, let's implement removal within the nodes themselves.

public bool Remove(int key, Node parent)
{
    if (Key < key)
    {
        return Left != null && Left.Remove(key, this);
    }

    if (Key > key)
    {
        return Right != null && Right.Remove(key, this);
    }

    if (Key == key)
    {
        if (Left != null && Right != null)
        {
            // We have two children
            Node minNode = Left.FindMinimum();

            Key = minNode.Key;
            Value = minNode.Value;

            // Remove "ourselves" from the right subtree branch.
            Left.Remove(Key, this);
        }
        else if (parent.Left == this)
        {
            // We're on the left side of our parent - meaning our key is greater than our parent
            // Set our parents left key to our left key if we have one, otherwise, set it to our right key
            parent.Left = Left ?? Right;
        } 
        else if (parent.Right == this)
        {
            // We're on the right side of our parent - meaning our key is less than our parent
            // Set our parents right key to our right key if we have one, otherwise, set it to our left key.
            parent.Right = Right ?? Left;
        }

        return true;
    }

    throw new InvalidOperationException("Something horrible happened!");
}

Let's try it out.

static void Main(string[] args)
{
    var bst = new BinarySearchTree();

    bst.Add(10, "ten");
    bst.Add(15, "fifteeen");
    bst.Add(5, "five");
    bst.Add(20, "twenty");
    bst.Add(12, "twelve");
    bst.Add(13, "thirteen");
    bst.Add(11, "eleven");

    bst.Print();

    Console.WriteLine("Removing node 15...");

    // Delete node 15
    bst.Remove(15);

    // Tree should now have now have 
    // a root of 10, with a right child of 5 and
    // a left child of 20, with a right child of 12

    bst.Print();
}

This produces an output of:

10
5
15
12
11
13
20
Removing node 15...
10
5
20
12
11
13  

Looks good.

Next up, let's implement traversal / enumeration of the tree, and start thinking about tests.


The following code is the code used to print the tree; it's not terribly interesting, and we won't be including it in our finished implementation only because it's only useful for the ad-hoc testing we're doing for this particular post.

On the tree itself:

public void Print()
{
    if (_root != null)
    {
        _root.Print();
    }
}

On the node:

public void Print()
{
    Console.WriteLine(Key);

    if (Right != null)
    {
        Right.Print();
    }

    if (Left != null)
    {
        Left.Print();
    }
}
comments powered by Disqus