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

Je suis à la recherche d'une mise en œuvre d'un Red-Black Tree en C#, avec les caractéristiques suivantes:La mise en œuvre de l'arbre rouge-noir en C#

Recherche, Insérer et Supprimer dans O (log n).
Le type de membre doit être générique.
Support dans Comparer(T), pour trier T par différents champs dedans.
La recherche dans l'arborescence doit se faire avec le champ spécifique, donc elle n'acceptera pas T, mais elle acceptera le type de champ qui la classe.
La recherche ne devrait pas être seulement une valeur exacte. Devrait soutenir la recherche de l'inférieur/supérieur.

Merci. Rip le TreeSet à partir des librairies de collection C5

Source

2009-11-09 Alon Gubkin

Répondant à votre autre question, nommée "Book or Teacher", le * vraiment * meilleur moyen d'apprendre la programmation est * d'écrire des programmes *. Écrivez celui-ci par vous-même et ensuite vous apprendrez quelque chose. –

@Pavel: Je pourrais écrire ceci, mais je cherche quelque chose de prêt, afin que je puisse continuer à développer les côtés principaux de mon programme, et accélérer le développement. –

Vous venez de décrire SortedDictionary<T, U>, à l'exception de la recherche binaire suivante, la plus basse et la plus élevée, que vous pouvez implémenter sans trop de difficultés.

Y a-t-il des raisons spécifiques pour lesquelles SortedDictionary est insuffisant pour vous?

Source

2009-11-09 19:47:04 mquander

* "que vous pouvez implémenter vous-même sans trop de difficultés." * Je ne crois pas que vous puissiez facilement étendre SortedDictionary. En regardant les métadonnées, et en essayant simplement de l'étendre, les pièces internes nécessaires ne semblent pas être accessibles. Ai-je tort? – Catskul

Voulez-vous dire le SortedDictionary implémente un arbre rouge-noir? Si vous le faites, où avez-vous trouvé cela? Je ne vois aucune mention de cela sur les pages MSDN. – comecme

Oui; Je viens de le vérifier en parcourant la classe dans Reflector. En interne, il place les clés dans un 'SortedSet ', qui est implémenté comme un arbre rouge/noir. Je ne suis pas sûr d'où j'en ai entendu parler - j'ai l'impression qu'une ancienne version de la documentation MSDN est allée plus en détail sur l'implémentation de 'SortedDictionary' contrairement à' SortedList'. Aussi, euh, je ne suis pas exactement sûr pourquoi je pensais qu'il pourrait facilement l'étendre.Il n'est pas clair qu'il pourrait. Tant pis. – mquander

Source

2009-11-09 19:46:44

Ceci est exactement le OrderedDictionary dans PowerCollections. C'est à peu près identique à SortedDictionary (arbre noir rouge avec des génériques) avec l'ajout de la possibilité de définir une clé de début/fin et d'analyser toutes les valeurs dans cette plage. SortedDicionary permet uniquement d'afficher une fonction GetEnumerator() qui commence au début de la collection et n'autorise qu'un appel MoveNext(), donc même si vous utilisez LINQ, il n'y a rien de magique: il commence au début et exécute votre expression sur chaque nœud, dans l'ordre, jusqu'à ce qu'il trouve ceux correspondant à votre expression LINQ.

OrderedDictionary a une fonction qui obtient un énumérateur à ou avant une clé particulière et qui fait la recherche dans O (log n). Un mot de prudence cependant: l'énumérateur dans le PowerCollections OrderedDictionary est implémenté en utilisant "yield" et les performances d'utilisation et d'énumération de la mémoire sont au moins O (n^2) ... vous pouvez changer l'implémentation vous-même pour le rendre mettre en place un recenseur traditionnel et ces deux problèmes disparaissent. Je vais soumettre ce patch à Codeplex si je peux trouver l'heure.

Source

2013-02-11 19:09:00 huntharo

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

Répondre

Questions connexes