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

Question

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

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

РЕДАКТИРОВАТЬ: Чтобы уточнить, что я ищу. Меня не интересуют упорядоченные словарные коллекции, которые внутренне используют дерево. Я на самом деле интересуюсь бинарным деревом - тем, которое раскрывает его структуру, чтобы вы могли делать такие вещи, как извлечение поддеревьев или выполнение обхода после исправления узлов. В идеале такой класс может быть расширен, чтобы обеспечить поведение специализированных деревьев (например, Red / Black, AVL, Balanced и т. Д.).

Answer 1

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

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; }
}

Answer 2

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

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

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

Answer 3

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

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

Answer 4

Я полагаю, что SortedDictionary в качестве вставки журнала (n) извлекает характеристики, которые можно ожидать от Tree Data Stucture.

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

Answer 5

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

Answer 6

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

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

Answer 7

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

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

Answer 8

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