This is how the binary tree is designed:
http://en.wikipedia.org/wiki/Binary_tree[
^].
This is how it is used for binary search:
http://en.wikipedia.org/wiki/Binary_search_tree[
^].
If you look at the algorithms, you will see that keys need a comparison criterion, but only "less then" relationship is actually used. You need to use the set of values that allows for the ordering:
http://en.wikipedia.org/wiki/Total_order[
^].
You need to define the order relationship for the the key values. To make is generic, you can define the interface for ordering (there is no a big need to define the '<' operator, but you can do it if it is convenient for your). Or you can use the more complex and general interface which is already available:
System.IComparable
:
http://msdn.microsoft.com/en-us/library/system.icomparable.aspx[
^].
Again, you can derive from this interface, if you want a comparison operator. Your key type should implement this interface, and then you can define a generic your node type assuming that the key type is
IComparable
, which is done using the
generic type constraint:
http://msdn.microsoft.com/en-us/library/bb384067.aspx[
^].
For a tree node, use generic class would look like this:
class Node<KEY_TYPE, VALUE_TYPE> : IComparable where KEY_TYPE : System.IComparable {
KEY_TYPE key;
VALUE_TYPE data;
Node<KEY_TYPE, VALUE_TYPE> left, right;
int IComparable.CompareTo(object @object) {
Node<KEY_TYPE, VALUE_TYPE> nodeObject = @object as Node<KEY_TYPE, VALUE_TYPE>;
}
}
Note that I suggested to implement
IComparable
also for the
Node
type. This way, you won't need to compare keys, will be able to compare nodes, immediately.
This will give you a cultured and convenient way to implement tree building algorithm and search.
The interface of your dictionary should identical to the one of the class
System.Collections.Generic.Dictionary<>
:
http://msdn.microsoft.com/en-us/library/xfhwa508%28v=vs.110%29.aspx[
^].
There is nothing to invent, use it one-to-one. The algorithms are described in the second link. Good luck.
[EDIT]
In response to a good note by Matt T Heffron:
Asymptotically, this algorithm is not the fastest for big volumes of data; it provides
computational time complexity of O(ln N), while
System.Collections.Generic.Dictionary
(and two more classes based on
bucket storage and
hash function) has time complexity of O(1).
Please see:
http://en.wikipedia.org/wiki/Big_O_notation[
^],
http://en.wikipedia.org/wiki/Time_complexity[
^],
http://en.wikipedia.org/wiki/Asymptotic_complexity[
^],
http://en.wikipedia.org/wiki/Asymptote[
^].
—SA