Почему в .NET нет класса <T>?

В библиотеке базового класса .NET есть несколько отличных структур данных для коллекций (List, Queue, Stack, Dictionary), но, как ни странно, он не содержит никаких структур данных для двоичных деревьев. Это ужасно полезная структура для определенных алгоритмов, таких как те, которые используют различные пути обхода. Я ищу правильно написанную, свободную реализацию.

Я просто слепой, и не нахожу его... он похоронен где-то в БКЛ? Если нет, может ли кто-то рекомендовать бесплатную или открытую библиотеку С#/.NET для двоичных деревьев? Предпочтительно тот, который использует дженерики.

EDIT: Чтобы уточнить, что я ищу. Меня не интересуют упорядоченные коллекции словарей, которые внутренне используют дерево. Меня действительно интересует двоичное дерево - одно, которое раскрывает его структуру, чтобы вы могли делать такие вещи, как извлечения поддеревьев, или выполнять обходное исправление на узлах. В идеале такой класс может быть расширен, чтобы обеспечить поведение специализированных деревьев (например, Red/Black, AVL, Balanced и т.д.).

Ответ 1

Вы правы, в BCL ничего нет. Я подозреваю, что это связано с тем, что выбор того, следует ли использовать дерево, как правило, представляет собой деталь реализации, а в противном случае - нетрадиционный способ доступа к данным. То есть вы не говорите: "элемент binary-search-for # 37"; вместо этого вы говорите: "Получите элемент № 37".

Но вы посмотрели C5? Это супер-удобно и у них есть несколько реализаций дерева (1, 2, 3).

Ответ 2

Вы можете определить свой собственный:

public class MyTree<K, V> : Dictionary<K, MyTree<K, V>>
{
    public V Value { get; set; }
}

Или без ключа:

public class MyTree<V> : HashSet<MyTree<V>>
{
    public V Value { get; set; }
}

Ответ 3

Что бы вы хотели от такой реализации?

Двоичное дерево? Красно-черный? Дерево Radix? B-дерево? R-дерево? R * -tree?

Дерево - это скорее шаблон, чем структура данных, и они, как правило, используются там, где важна производительность (поэтому детали реализации, вероятно, тоже имеют значение). Если в BCL включен какой-то древовидный класс, вам нужно будет все равно катиться самостоятельно

Ответ 4

Я считаю, что SortedDictionary как вставка log (n), характеристики поиска, которые вы ожидаете от структуры данных дерева.

http://msdn.microsoft.com/en-us/library/f7fta44c(VS.80).aspx

Ответ 5

SortedSet<T> реализуется как дерево двоичного поиска ^ref. SortedDictionary<TKey, TValue> внутренне использует SortedSet<T>, поэтому он также является двоичным деревом поиска ^ref.

Ответ 6

Нет, в BCL нет никакого типа < Tree<T> -like "(что всегда меня озадачивало), но здесь хорошая статья, которая проведет вас через реализацию вашего собственного в С#.

Я думаю, вы могли бы сделать аргумент, что древовидные структуры данных менее часто используются в приложениях, к которым обычно используется .NET(бизнес-приложения, приложения для переноса данных и т.д.). Тем не менее, я согласен с вами, странно, что BCL вообще не имеет реализации.

Ответ 7

Эта серия статей была полезной для меня, когда мне приходилось писать свои собственные, особенно часть 3 и 4.

Обширный анализ структур данных

Ответ 8

Здесь TreeNode, который вы можете использовать. Он не является общим и скрытым в формах окон и используется с элементом управления treeview, но вы также можете использовать его в другом месте.