Структура данных C # с функциональностью SortedDictionary () и node.Next ()?

Question

Как построить / получить структуру данных со следующими возможностями:

• Хранит (ключ, значение) узлы, ключи реализуют IComparable.
• Быстрая (log N) вставка и поиск.
• Быстрый (log N) метод для получения следующего более высокого / следующего более низкого узла из любого узла. [ПРИМЕР: если вставленные ключевые значения (7, кошка), (4, собака), (12, страус), (13, золотая рыбка), а затем, если keyVal ссылается на (7, кошка), keyVal.Next () должна возвращать ссылку на ( 12, страус).

Конечно, было бы достаточно и решения с нумератором из произвольного ключа. Обратите внимание, что стандартной функциональности SortedDictionary будет недостаточно, поскольку может быть возвращен только перечислитель по всему набору, что делает нахождение keyVal.next в худшем случае требующим N операций.

Может ли самоанализованное сбалансированное двоичное дерево поиска (красно-черное дерево) быть оснащено функциональностью node.next ()? Есть хорошие рекомендации для этого? Какие-нибудь менее трудоемкие решения?

Answer 1

OrderedDictionary в PowerCollections предоставляет функцию «получить итератор, начиная с или до ключа», для которой требуется O (log N) времени, чтобы вернуть первое значение. Это позволяет очень быстро, скажем, сканировать 1000 элементов, которые находятся ближе к середине набора из 50 миллионов элементов (что с помощью SortedDictionary потребовало бы угадать начало или конец, оба из которых являются одинаково плохим выбором и потребовали бы итератор около 25 миллионов предметов). OrderedDictionary может сделать это только с 1000 повторяющимися элементами.

Существует проблема в OrderedDictionary, хотя и в том, что он использует yield, который вызывает производительность O (n ^ 2) и нехватку памяти при итерации набора из 50 миллионов элементов в 32-битном процессе. Для этого есть довольно простое решение, о котором я расскажу позже.

Answer 2

У меня когда-то были похожие требования, и я не смог найти что-то подходящее.Поэтому я реализовал дерево AVL.Вот несколько советов, чтобы сделать это с учетом производительности:

1. Не используйте рекурсию для обхода дерева (вставьте, обновите, удалите, затем).Лучше использовать массив стека для хранения пути к корню, который необходим для балансировки операций.
2. Не хранить родительские узлы.Все операции начнутся с корневого узла и пройдут дальше.Родители не нужны, если реализуются тщательно.
3. Чтобы найти узел Next () существующего, обычно сначала вызывается Find ().Стек, создаваемый этим, должен быть повторно использован для Next () than.

Следуя этим правилам, я смог реализовать дерево AVL.Он работает очень эффективно даже для очень больших наборов данных.Я хотел бы поделиться, но это потребовало бы некоторых модификаций, так как он не хранит значения (очень легко) и не полагается на IComparable, но на фиксированные ключи типа int.