Let's implement a Binary Search Tree, Part IV

on Let's Implement, C#

This is the fourth post in this series

To this point, we've implement addition, removal, and search.

At this point, I was going to implement a series of tests, but I think I'll wait for a later post to cover that. Let's clean up our implementation a bit instead.

Notice that to this point, Node has been declared public:

 public class Node
 {
     ...
 }

Node, though, is an implementation detail. When you call Search(), you don't get back a Node, you get a bool indicating the result of your search and an out param pointing at the found value.

Let's make Node a private to the BinarySearchTree class:

public class BinarySearchTree
{
    private class Node
    {
        ...
    }
    ...
}

Excellent. Now our implementation detail is hidden from view.

Something else that's bothered me; our implementation stores values as object. This is handy, since any managed type can be referenced or boxed as an object reference, but is less handy since dealing with this means the caller is likely going to have to do a lot of casting for no real reason.

It's likely a safe assumption that any given instance of our binary search tree is type consistent on the stored value - i.e. every node contains a different value and key, but the type of each value is the same.

Let's implement a generic form of our BinarySearchTree.

The modifications are many, but fairly straightforward. Essentially, BinarySearchTree now requires a type parameter, as does Node; any type we initialize a default value for our Node value, previously we used null, but since we aren't constraining our type parameter to a nullable type (a BST of integers is perfectly legit), we'll used default(T) to get an appropriate default value in those cases.

Complete code listing:

public class BinarySearchTree<T>
{
    Node<T> _root;

    public bool Add(int key, T value)
    {
        if (null == _root)
        {
            _root = new Node<T>()
            {
                Key = key,
                Value = value
            };

            return true;
        }

        return _root.Add(key, value);
    }

    public bool Remove(int key)
    {
        bool returnValue;

        if (null == _root)
            returnValue = false;
        else if (_root.Key == key)
        {
            Node<T> temporaryRoot = new Node<T> { 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;
    }

    public bool Search(int searchKey, out T value)
    {
        value = default(T);

        return _root != null && _root.Search(searchKey, out value);
    }

    private class Node<TValue>
    {
        public Node<TValue> Left { get; set; }
        public Node<TValue> Right { get; set; }
        public TValue Value { get; set; }
        public int Key { get; set; }

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

        public bool Remove(int key, Node<TValue> 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<TValue> 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!");
        }

        public bool Search(int searchKey, out TValue value)
        {
            value = default(TValue);

            if (Key == searchKey)
            {
                value = Value;
                // Hey! It's us!
                return true;
            }

            if (Key < searchKey)
            {
                if (Left == null)
                {
                    return false;
                }

                return Left.Search(searchKey, out value);
            }

            if (Key > searchKey)
            {
                if (Right == null)
                {
                    return false;
                }

                return Right.Search(searchKey, out value);
            }

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

        public bool Add(int key, TValue value)
        {
            if (this.Key == key)
                return false; // Cannot add the same key twice

            if (this.Key < key)
            {
                // The specified key is less than the current key; place node on the left of this node
                if (null == Left)
                {
                    Left = new Node<TValue>()
                    {
                        Key = key,
                        Value = value
                    };

                    return true;
                }
                else
                {
                    // Left already has a node.
                    return Left.Add(key, value);
                }
            }
            else if (Key > key)
            {
                // The specified key is more than the current key; place node on the right of this node
                if (null == Right)
                {
                    Right = new Node<TValue>()
                    {
                        Key = key,
                        Value = value
                    };

                    return true;
                }
                else
                {
                    // Right already has a node.
                    return Right.Add(key, value);
                }
            }

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

Next up, let's take a look at the standard .NET container interfaces; wouldn't it be handy if the fact our binary search tree was a binary search tree was nothing more than an implementation detail?

comments powered by Disqus