Pourquoi n'y a-t-il pas d'arbre <T> classe en .NET?

Question

La bibliothèque de classes de base .NET a quelques excellentes structures de données pour les collections (Liste de, File, Pile, Dictionnaire), mais curieusement il ne contient pas de structures de données pour des arbres binaires. C'est terriblement structure utile pour certains algorithmes, tels que ceux qui tirent profit de différentes traversée de chemins. Je suis à la recherche d'un écrit correctement, gratuit de mise en œuvre.

Suis-je tout simplement aveugle, et ne pas trouver il... est-il enterré quelque part dans la BCL? Si non, quelqu'un peut-il recommander un libre ou open-source C#/.NET-library pour les arbres binaires? De préférence un qui emploie des génériques.

EDIT: Pour clarifier ce que je suis à la recherche pour. Je ne suis pas intéressé dans l'ordre du dictionnaire des collections utiliser à l'interne d'un arbre. Je suis effectivement intéressé par un arbre binaire qui expose sa structure, de sorte que vous pouvez faire des choses comme l'extrait de sous-arborescences, ou effectuer un post-fix de la traversée sur les nœuds. Idéalement, une telle classe peut être étendu pour fournir les comportements spécialisés arbres (ie. Rouge/Noir, AVL, Équilibré, etc).

Answer 1

Vous pouvez définir le vôtre:

 public class MyTree<K, V> : Dictionary<K, MyTree<K, V>>
{
    public V Value { get; set; }
}
 

Ou sans clé:

 public class MyTree<V> : HashSet<MyTree<V>>
{
    public V Value { get; set; }
}
 

Answer 2

Que voudriez-vous d'une telle implémentation?

Arbre binaire? Rouge noir? Arbre Radix? B-arbre? R-arbre? R * -tree?

Une arborescence est plus un motif qu'une structure de données, et elles ont tendance à être utilisées lorsque les performances sont importantes (les détails de la mise en œuvre ont donc aussi de l'importance). Si la BCL incluait une sorte de classe d’arbres, vous n’auriez de toute façon que le vôtre

Answer 3

Vous avez raison, il n'y a rien dans la BCL. Je soupçonne que c'est parce que le choix de l'utilisation d'un arbre est généralement un détail d'implémentation, et est par ailleurs une façon non conventionnelle pour accéder aux données. Qui est, vous ne dites pas, "binaire de recherche pour l'élément #37"; au lieu de cela, dites-vous, "me élément #37".

Mais avez-vous pris un coup d'oeil à C5? C'est super-pratique et ils ont plusieurs arbres implémentations (1, 2, 3).

Answer 4

Je crois que SortedDictionary lorsque le log (n) insère, les caractéristiques de récupération que vous pouvez attendre d’une structure de données arborescente.

http://msdn.microsoft.com/en-us/library/f7fta44c(VS.80).aspx

Answer 5

SortedDictionary<TKey, TValue> est en réalité un arbre binaire. SortedList<T> est aussi.

Si vous souhaitez exposer les détails de manière plus arborescente, vous devriez pouvoir créer une classe générique contenant un SortedList<T> possédant l'interface que vous recherchez:

 public class Tree<T>
{
   private SortedList<T> _TreeImplementation;

   // Tree interface methods, delegate storage and 
   // retrieval to _TreeImplementation.
}