.NET 4.0中是否有内置的二叉搜索树,还是需要从头开始构建这种抽象数据类型？

编辑

这具体是关于二叉搜索树,而不是一般的抽象数据类型"树".

有谁知道我在哪里可以找到如何在C#中构建一个trie的例子.我正在尝试使用字典/单词列表并用它创建一个trie.

是否有下限功能SortedList<K ,V>？该函数应返回等于或大于指定键的第一个元素.还有其他类支持这个吗？

伙计们 - 请再次阅读这个问题.如果它存在,我不需要返回键的函数.当没有确切的密钥匹配时,我对场景感兴趣.

我对O(log n)时间感兴趣.这意味着我没有foreach循环的问题,而是希望有一个有效的方法来做到这一点.

我对此做了一些测试.

Linq语句既不是编译器也不是运行时机器优化的,因此它们遍历所有集合元素并且速度慢O(n).根据Mehrdad Afshari的回答,这里是一个二进制搜索,它在Keys集合的O(log n)中工作:

public static int FindFirstIndexGreaterThanOrEqualTo<T>(
            this IList<T> sortedCollection, T key
        ) where T : IComparable<T> {
    int begin = 0;
    int end = sortedCollection.Count;
    while (end > begin) {
        int index = (begin + end) / 2;
        T el = sortedCollection[index];
        if (el.CompareTo(key) >= 0)
            end = index;
        else
            begin = index + 1;
    }
    return end;
}