Библиотека базовых классов в .NET имеет отличные структуры данных для коллекций (List, Queue, Stack, Dictionary), но, как ни странно, не содержит никаких структур данных для двоичных деревьев. Это очень полезная структура для определенных алгоритмов, например для тех, которые используют преимущества различных путей обхода. Ищу правильно написанную бесплатную реализацию.
Я просто слепой и не нахожу его ... где-то в BCL? Если нет, может ли кто-нибудь порекомендовать бесплатную или открытую библиотеку C # /. NET для двоичных деревьев? Желательно тот, который использует дженерики.
РЕДАКТИРОВАТЬ: чтобы уточнить, что я ищу. Меня не интересуют упорядоченные коллекции словарей, которые внутренне используют дерево. На самом деле меня интересует двоичное дерево - такое, которое раскрывает свою структуру, чтобы вы могли делать такие вещи, как извлечение поддеревьев или выполнение обхода узлов после исправления. В идеале такой класс может быть расширен для обеспечения поведения специализированных деревьев (например, красный / черный, AVL, сбалансированный и т. Д.).
источник
Ответы:
Вы правы, в BCL ничего нет. Я подозреваю, что это связано с тем, что выбор использования дерева обычно является деталью реализации, а в остальном - нетрадиционным способом доступа к данным. То есть вы не говорите «двоичный поиск элемента № 37»; вместо этого вы говорите: «Дайте мне элемент №37».
Но вы смотрели на C5 ? Это очень удобно, и у них есть несколько реализаций дерева ( 1 , 2 , 3 ).
источник
Вы можете определить свое собственное:
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; } }источник
Что бы вы хотели от такой реализации?
Двоичное дерево? Красно-черный? Радиксное дерево? B-дерево? R-дерево? R * -дерево?
Дерево - это больше шаблон, чем структура данных, и они, как правило, используются там, где важна производительность (поэтому детали реализации, вероятно, тоже имеют значение). Если бы BCL включал какой-то древовидный класс, вам все равно нужно было бы свернуть свой собственный
источник
Я считаю, что
SortedDictionaryпри вставке log (n) получаются характеристики извлечения, которые можно ожидать от структуры древовидных данных.http://msdn.microsoft.com/en-us/library/f7fta44c(VS.80).aspx
источник
SortedSet<T>реализовано как двоичное дерево поиска исх .SortedDictionary<TKey, TValue>внутренне использует,SortedSet<T>так что это тоже бинарное дерево поиска ref .источник
Нет,
Tree<T>в BCL нет никакого « -подобного» типа (что меня тоже всегда озадачивало), но вот хорошая статья, которая проведет вас через реализацию вашего собственного на C #.Я думаю, вы могли бы привести аргумент, что древовидные структуры данных реже используются в приложениях, для которых обычно используется .NET (бизнес-приложения, приложения для перемещения данных и т. Д.). Тем не менее, я согласен с вами, странно, что BCL вообще не имеет реализации.
источник
Эта серия статей оказалась для меня полезной, когда мне пришлось писать свои собственные, особенно части 3 и 4.
Обширное изучение структур данных
источник
Там в TreeNode вы можете использовать. Он не является общим и скрытым в формах Windows и используется с элементом управления treeview, но вы можете использовать его и в другом месте.
источник