Я ищу встроенную реализацию двоичного дерева поиска в .NET 4. Есть ли она?
Есть ли реализация двоичного дерева поиска в .NET 4?
Ответы (5)
Класс SortedDictionary<K,V> использует дерево, это то, что вам нужно?
См. Этот ответ SO для обсуждения.
person
Henk Holterman
schedule
12.10.2010
Другой вариант - использовать список и отсортировать его. Затем вы можете использовать метод BinarySearch для поиска элементов. Чтобы поддерживать отсортированный список, вы можете использовать индекс, возвращаемый BinarySearch, для вставки в. Если возвращаемый индекс отрицательный, используйте дополнение (оператор ~) в качестве места вставки, если возвращенный индекс положительный, вы можете вставить в это место (если вы не хотите установить подобное поведение, и в этом случае не вставляйте вообще).
person
pstrjds
schedule
12.10.2010
Это обеспечивает ту же семантику поиска, но основная структура по-прежнему представляет собой простой старый список, а не BST.
- person Steve Townsend; 12.10.2010
Хороший звонок, не подумал, когда разместил это (только 1 чашка кофе на тот момент). Я использую список с BinarySearch и дополнительную вставку индекса, чтобы получить семантику поиска BST. Стоит почитать внимательнее :)
- person pstrjds; 12.10.2010
Класс TreeDictionary реализует интерфейс ISortedDictionary и представляет словарь пар (ключ, значение) или записей с использованием упорядоченного сбалансированного двоичного дерева красного и черного цвета. Доступ к записи, удаление записи и вставка записи занимают время O (вход в систему). Перечисление ключей, значений или записей древовидного словаря следует за порядком ключей, определяемым компаратором ключей.
person
QrystaL
schedule
12.10.2010
http://code.google.com/p/self-balancing-avl-tree/. Сбалансированная реализация дерева AVL с операциями объединения и разделения, а также SortedDictinary и SortedMultiDictionary на основе дерева AVL.
person
ros
schedule
10.10.2012
