Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C#
Greetings!. I need an example or a guide on how to create a dictionary using binary trees in c #, thanks in advance.
Posted 29-Apr-13 10:50am
Comments
Matt T Heffron at 29-Apr-13 16:05pm
   
Binary trees are described all over the internet.
What have you *tried* and what are your *specific problems*?
Member 10005238 at 29-Apr-13 16:10pm
   
my problem is to insert the words to keep them in the dictionary, I just stored a word.
Sergey Alexandrovich Kryukov at 29-Apr-13 16:26pm
   
I answered in considerable detail, but you should read the links. I wonder, what have you done so far?
—SA
Member 10005238 at 29-Apr-13 17:09pm
   
Thanks, I think I have almost ready!
Sergey Alexandrovich Kryukov at 29-Apr-13 17:12pm
   
Very good. You are very welcome.
Good luck, call again.
—SA

1 solution

Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

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; // anything you need to put in 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>; // use it for comparison with "this"
            // implement comparison between @object and this
            // take into account that @object can be null
            // and that @object can be of different type
        }
 
        // implement constructors, operations with left, right, etc...

    }
 
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
  Permalink  
v4
Comments
Matt T Heffron at 29-Apr-13 19:55pm
   
Good answer! The only thing you failed to mention was that, unless computing a Hash of a Node is substantially less efficient than the comparison, the System.Collections.Generic.Dictionary<> will probably be more efficient.
Sergey Alexandrovich Kryukov at 29-Apr-13 20:20pm
   
Thank you, Matt.
I know. Well, this is a good point. System.Collections.Generic.Dictionary provides O(1), while binary tree search — O(ln N), apparently. I guess, you never can say everything in one Quick Answer... :-)
—SA
Sergey Alexandrovich Kryukov at 29-Apr-13 20:28pm
   
I added, the info on what you mentioned (which already was mentioned in already linked articles); and it added 4 links, but then it would need a link on bucket presentation like in Dictionary (I don't know a link, do you?)...
—SA

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



Advertise | Privacy | Mobile
Web03 | 2.8.1411022.1 | Last Updated 29 Apr 2013
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100