Let's implement a Binary Search Tree, Part V

This is the fifth post in this series

What keeps occurring to me about the BST implementation to this point, is that it looks an awful lot like a dictionary. Consider:

  • We have keys.
  • We have values.
  • You can get values using the key.
  • You can't have the same key twice.

Remarkably like a dictionary. Wouldn't it be nice if our BST implementation was an implementation detail of a IDictionary implementation?

In order for that to work, though, our key - currently, an integer - would need to be comparable. Comparison would also need to be cheap, so while it might be attractive to, say, use a hashing function over each key, given the number of times we're comparing things, that would be terribly effective.

The other question is, do we need the key to be comparable by value or by reference?

FooBar f = new FooBar() { AProperty = 123; BProperty = 321; }
FooBar f1 = new FooBar() { AProperty = 123; BProperty = 321; }

...

myBst[f] = "A Value";
myBst[f1] = "Another Value";

In the example above, myBst[f] and myBst[f1] point to different values, but the keys are bitwise equivalent - but not reference equivalent. They are at different addresses in memory.

But wait. Is this a problem?

Well, it turns out yes, it is. FooBar doesn't implement greater than / less than operators. The Equals operators is determining reference equivalence, but there is no concept of greater than / less than comparison on this type.

We can implement those operators easily enough:

public static bool operator <(FooBar firstType, FooBar otherType)
{
    ...
}

public static bool operator >(FooBar firstType, FooBar otherType)
{
     ...
}

But can we enforce this as a type constraint? We can't require our keys all implement a particular custom interface of our design - operators are static, and static methods can't be defined in an interface. And even if they could be, that'd be a terrible idea, because you'd have to re-implement or specialize all the existing types that are perfectly comparable, like Int32, because it doesn't implement our custom-special interface.

What about IComparable?

Let's see:

  • It defines a CompareTo method that returns a value indicating if something is equal to, less than, or greater than.
  • It's defined on all the intrinsic built in types - int, double, string, etc.

Yes. I think that'd do nicely.

Next up - updated implementation, and by popular request, a GitHub repo for our little implementation.

comments powered by Disqus