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

Question

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

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

Спасибо.

Answer 1

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

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

Answer 2

Разорвите TreeSet из коллекции C5.

Answer 3

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

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

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

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