La mise en œuvre de l'arbre rouge-noir en C #

Question

Je suis à la recherche d'une mise en œuvre d'un Arbre Rouge-Noir en C #, avec les caractéristiques suivantes:

• Recherche, Insérer et Supprimer dans O (log n).
• Les membres de type devrait être générique.
• Support en Comparer (T) , pour le tri par différents T champs en elle.
• Recherche dans l'arbre doit être avec le champ spécifique, il n'acceptera T, mais il va accepter le type de champ de tri il.
• Recherche ne doit pas être seulement une valeur exacte. Devrait soutenir la recherche l'inférieur / supérieur.

Merci.

Answer 1

Vous venez de décrire la plupart SortedDictionary<T, U> , sauf pour la prochaine plus bas / nouvelle valeur la plus élevée recherche binaire, que vous pouvez mettre en œuvre sur votre propre sans trop de difficulté.

Y at-il des raisons spécifiques SortedDictionary est insuffisante pour vous?

Answer 2

Rip la TreeSet de libs collection C5.

Answer 3

Ceci est exactement le OrderedDictionary dans PowerCollections. Il est à peu près identique à SortedDictionary (arbre noir rouge avec les génériques) avec l'ajout de la possibilité de définir une clé de touche début / fin et analyser toutes les valeurs dans cette plage.

SortedDicionary ne permet expose une fonction GetEnumerator () qui commence au début de la collecte et permet seulement un appel MoveNext (), même si vous utilisez LINQ il n'y a rien de magique qui se passe: il commence au début et exécute votre expression sur chaque nœud unique, dans l'ordre, jusqu'à ce qu'il trouve ceux correspondant à votre expression LINQ.

OrderedDictionary a une fonction qui obtient un énumérateur avant ou une touche particulière et qui fait la recherche en O (log n).

Un mot d'avertissement cependant: le recenseur dans le PowerCollections OrderedDictionary est mis en œuvre en utilisant le « rendement » et l'utilisation de la mémoire et les performances d'énumération est au moins O (n ^ 2) ... vous pouvez changer la mise en œuvre vous-même pour le rendre mettre en œuvre un recenseur traditionnel et ces deux problèmes disparaissent. Je vais soumettre ce patch à Codeplex si je peux toujours trouver le temps.