使用c#的二叉树字典 [英] binary tree dictionary using c #
问题描述
问候!我需要一个关于如何使用c#中的二叉树创建字典的示例或指南,提前感谢。
Greetings!. I need an example or a guide on how to create a dictionary using binary trees in c #, thanks in advance.
推荐答案
这是二叉树的设计方式: http://en.wikipedia.org/wiki/Binary_tree [ ^ ]。
这是用于二进制文件的方式搜索: http://en.wikipedia.org/wiki/Binary_search_tree [ ^ ]。
如果看一下算法,您将看到密钥需要一个比较标准,但实际上只使用少于的关系。您需要使用允许订购的一组值: http://en.wikipedia.org/wiki/Total_order [ ^ ]。
您需要定义键值的顺序关系。要使make是通用的,您可以定义接口以进行排序(不需要定义''<''运算符,但如果方便的话,您可以这样做)。或者您可以使用已经可用的更复杂和通用的界面:System.IComparable
:
http://msdn.microsoft.com/en-us/library/system.icomparable.aspx [ ^ ]。
同样,如果你想要一个比较运算符,你可以从这个接口派生。您的密钥类型应该实现此接口,然后您可以定义一个通用的节点类型,假设密钥类型是IComparable
,这是使用泛型类型约束完成的:
http://msdn.microsoft.com/en -us / library / bb384067.aspx [ ^ ]。
对于树节点,使用泛型类看起来像这样:
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 isIComparable
, 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...
}
请注意,我建议为节点
类型实现 IComparable
。这样,您就不需要比较键,就能立即比较节点。
这将为您提供一种实用树的文化和便捷方式构建算法和搜索。
字典的界面应与类 System.Collections.Generic.Dictionary<>类相同。
:
http://msdn.microsoft.com/en-us/library/xfhwa508%28v=vs.110%29.aspx [ ^ ]。
没有什么可以发明的,一对一地使用它。算法在第二个链接中描述。祝你好运。
回应Matt T Heffron的好评:
渐近地,这种算法对于大量数据来说并不是最快的;它提供了O(ln N)的计算时间复杂度,而 System.Collections.Generic.Dictionary
(以及另外两个基于的类bucket 存储和哈希函数)的时间复杂度为O(1)。
请参阅:
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/w iki / Asymptote [ ^ ]。
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.
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[^].
这篇关于使用c#的二叉树字典的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!