我们都知道Dictionary<TKey, TValue>查找元素非常快,其实现原理是:将你TKey的值散列到数组的指定位置,将TValue的值存入对应的位置,
由于取和存用的是同一个算法,所以就很容易定位到TValue的位置,花费的时间基本上就是实现散列算法的时间,跟其中元素的个数没有关系,
故取值的时间复杂度为O(1)。
集合无非都是基于最基础语法的数组[],先欲分配,然后向其中添加元素,容量不够就创建一个2倍容量的数组,将之前的元素赋值过来,将之前的数组回收,
但基于散列算法的集合这点上有点不同,他并不是每次创建一个2倍容量的数组,为了让元素均匀的分布到数组上,数组的容量是这么增长的:3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,1103...
以质数的方式增长。由于每次扩充数组的容量较小,如果要向其中添加很多元素的话,程序员又没有预先分配内存,那就会出现多次数组的创建、复制和回收。
一直想做个有用的东西出来,让想用的人用,又能让自己练练手,于是这次做了一个基于二叉查找树的集合,我们知道在二叉查找树中查询元素的最优时间复杂度是O(logN)即在满二叉树的情况下,最坏时间复杂度是O(n)即除叶子节点外每个节点只有一个子节点,
查找元素它也是很快的哦,而且查找的时候都只是做Int型的比较,而Dictionary<TKey, TValue>是基于一个散列算法,当然基于二插查找树的集合也有自身的缺点:
1:元素必须实现接口IBinaryTree,其属性CompareValue主要用于比较生成二叉查找树
2:元素必须是可以new的,即不支持基础类型int,char,string等
3:每个节点都有左右两个子节点,他们只是起到指针的作用,指向该节点的子节点,只需占用额外的少量内存
4:基本上都是基于递归实现,元素过多的话,会栈溢出,至于原因请看我的这篇博客
优点是常用的一些功能都有,功能如下,练手吗,但会一直优化下去
public class BinaryTree<T> : IDisposable, IEnumerable<T>, IEnumerable where T :IBinaryTree, new()
{
public BinaryTree();
public BinaryTree(IEnumerable<T> list);//将一个数组构造成二插查找树
public BinaryTree(T root); //指定跟节点
public int Count { get; }//元素个数
public T this[IBinaryTree iBinaryTree] { get; }//数组索引直接访问元素
public void Add(T t);//添加元素
public void Clear();//清除所有元素
public bool Contains(T iBinaryTree);//是否包含自定元素
public void Dispose();//释放资源,支持using
public T Find(IBinaryTree iBinaryTree);//查找元素
public T Find(IBinaryTree iBinaryTree, TreeNode<T> node);//在指定的节点下查找元素
public T FindMax();//最大元素
public T FindMin();//最小元素
public T FindMin(TreeNode<T> node);//在指定的节点下查找最小元素
public IEnumerator<T> GetEnumerator();//返回所有元素,支持foreach
public TreeNode<T> Remove(T t);//删除元素
public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node);//在指定的节点下删除元素
public IEnumerable<T> Sort();//排序(升序)
public IEnumerable<T> ToList();//返回所有元素
}
作者:陈太汉
博客:http://www.cnblogs.com/hlxs/
本文转自啊汉博客园博客,原文链接:http://www.cnblogs.com/hlxs/archive/2012/03/15/2397542.html