Implementação da Vermelho-Preto Árvore em C #

Question

Eu estou procurando uma implementação de um árvore Vermelho-Preto em C #, com características o seguinte:

• Search, Inserir e Excluir em O (log n).
• Membros tipo deve ser genérico.
• Suporte em Comparer (T) , para classificar T por diferentes campos em que.
• Pesquisando na árvore deve ser com o campo específico, por isso não vai aceitar T, mas vai aceitar o tipo de campo classificando-o.
• Searching não deve ser apenas valor exato. Devem apoiar a pesquisa a mais elevada inferior /.

Obrigado.

Answer 1

Você na maior parte apenas descrito SortedDictionary<T, U> , exceto para a próxima menor /-mais elevado seguinte pesquisa valor binário, o que você pode implementar em seu próprio país sem muita dificuldade.

Tem razões lá específicas que SortedDictionary é insuficiente para você?

Answer 2

Rip o TreeSet de libs coleta C5.

Answer 3

Este é exatamente o OrderedDictionary em PowerCollections. É praticamente idêntico ao SortedDictionary (árvore rubro-negra com os genéricos) com a adição da capacidade de definir uma chave chave de início / fim e digitalizar todos os valores nesse intervalo.

SortedDicionary só permite que expõe uma função GetEnumerator () que começa no início da coleção e só permite que uma chamada MoveNext (), assim mesmo se você usar o LINQ não é nada mágico acontece: ela começa no início e vai a sua expressão em cada nó, na ordem, até encontrar aqueles que correspondem à sua expressão LINQ.

OrderedDictionary tem uma função que recebe um enumerador em ou antes de uma tecla particular e que faz a pesquisa em O (N log N).

Uma palavra de cautela, porém: o recenseador na PowerCollections OrderedDictionary é implementado utilizando o "rendimento" e o uso de memória e desempenho de enumeração é de pelo menos O (n ^ 2) ... você pode alterar a implementação mesmo para torná-lo implementar um recenseador tradicional e ambos estes problemas vão embora. Vou alegam que patch para Codeplex se eu nunca pode encontrar o tempo.