Реализация Красно-черного дерева на C#

Question

Я ищу реализацию a Красно-Черное Дерево в C #, со следующими функциями:

• Поиск, вставка и удаление в O (журнал n).
• Тип элементов должен быть общим.
• Поддержка в Устройство сравнения (T), для сортировки T по разным полям в нем.
• Поиск в дереве должен осуществляться по определенному полю, поэтому он не будет принимать T, но он будет принимать тип поля, сортирующий его.
• Поиск не должен заключаться только в точном значении.Должен поддерживать поиск по более низкому / более высокому.

Спасибо.

Answer 1

Вы в основном только что описали SortedDictionary<T, U>, за исключением двоичного поиска со следующим наименьшим / следующим по величине значением, который вы могли бы реализовать самостоятельно без особых трудностей.

Существуют ли конкретные причины, по которым SortedDictionary для вас этого недостаточно?

Answer 2

Скопируйте набор деревьев из библиотек коллекции C5.

Answer 3

Это именно тот OrderedDictionary, который используется в PowerCollections.Он практически идентичен SortedDictionary (красно-черное дерево с обобщениями) с добавлением возможности устанавливать начальный ключ / конечный ключ и сканировать все значения в этом диапазоне.

SortedDicionary позволяет предоставлять только функцию GetEnumerator(), которая запускается в начале коллекции и разрешает только вызов MoveNext(), поэтому, даже если вы используете LINQ, ничего волшебного не происходит:он начинается с начала и запускает ваше выражение на каждом отдельном узле по порядку, пока не найдет те, которые соответствуют вашему выражению LINQ.

OrderedDictionary имеет функцию, которая получает перечислитель по определенному ключу или перед ним и которая выполняет поиск в O (log n).

Однако одно предостережение:перечислитель в PowerCollections OrderedDictionary реализован с использованием "yield", а использование памяти и производительность перечисления составляют не менее O (n ^ 2)...вы можете сами изменить реализацию, чтобы она реализовывала традиционный перечислитель, и обе эти проблемы исчезнут.Я отправлю этот патч в Codeplex, если когда-нибудь смогу выкроить время.