Quelle est la structure d'arbre devrais-je utiliser pour l'indexation?

Question

Je pense à expérimenter avec l'aide d'une structure d'arbre pour l'indexation que je veux tester si elle est plus rapide que mon implémentation actuelle d'indexation qui est essentiellement un hachage basée recherche.

J'ai lu sur diverses questions et des articles sur la performance des arbres B, AVL et arbres rouges noirs et ne peut pas vraiment voir beaucoup de différence entre les performances sage.

Quelle est la structure arbre ce que les gens recommander et pourquoi? Idéalement, il devrait avoir une implémentation .Net existante disponible si je ne suis pas opposé à la mise en œuvre ma propre si nécessaire

Answer 1

Un bon Hashtable est presque toujours plus rapide qu'un arbre. Le grand avantage de l'arbre est que vous pouvez l'utiliser pour interroger les plages et pour la commande. Donc, si vous n'avez pas besoin de ces fonctionnalités, je préfère regarder dans l'optimisation de votre solution de hachage.

SortedDictionary<K,V> est AFAIK arboricoles Axée.

Answer 2

Un arbre binaire est pas équilibré. Ne l'utilisez pas.

Un arbre AVL est mieux équilibré qu'un arbre rouge-noir; il a plus rapide recherche.

Beaucoup plus important encore, l'algorithme AVL est simple et comprehendable. Ceci est, IME, pas le cas pour l'algorithme rouge-noir. Vous ne pouvez pas mettre en œuvre des algorithmes que vous ne comprenez pas, ou plutôt, vous pouvez les mettre en œuvre aveuglément, ce qui est bien revient à mon avis à -not- pouvoir les mettre en œuvre.