Структура данных 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

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

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

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

Answer 2

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

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