La bibliothèque de classes de base dans .NET a d'excellentes structures de données pour les collections (liste, file d'attente, pile, dictionnaire), mais curieusement, elle ne contient aucune structure de données pour les arbres binaires. C'est une structure terriblement utile pour certains algorithmes, tels que ceux qui tirent parti de différents chemins de traversée. Je recherche une implémentation gratuite et correctement écrite.
Suis-je simplement aveugle et ne le trouve pas ... est-il enterré quelque part dans la BCL? Sinon, quelqu'un peut-il recommander une bibliothèque C # / .NET gratuite ou open-source pour les arbres binaires? De préférence, celui qui utilise des génériques.
EDIT: Pour clarifier ce que je recherche. Je ne suis pas intéressé par les collections de dictionnaires ordonnées qui utilisent en interne un arbre. Je suis en fait intéressé par un arbre binaire - un arbre qui expose sa structure afin que vous puissiez faire des choses comme extraire des sous-arbres ou effectuer une traversée post-correction sur les nœuds. Idéalement, une telle classe pourrait être étendue pour fournir les comportements d'arbres spécialisés (c'est-à-dire rouge / noir, AVL, équilibré, etc.).
la source
Réponses:
Vous avez raison, il n'y a rien dans la BCL. Je soupçonne que cela est dû au fait que le choix d'utiliser ou non un arbre est généralement un détail de mise en œuvre et est par ailleurs un moyen non conventionnel d'accéder aux données. C'est-à-dire que vous ne dites pas "élément de recherche binaire # 37"; au lieu de cela, vous dites "récupérez-moi l'élément n ° 37".
Mais avez-vous jeté un œil à C5 ? C'est très pratique et ils ont plusieurs implémentations d'arbre ( 1 , 2 , 3 ).
la source
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; } }la source
Que souhaiteriez-vous d'une telle implémentation?
Arbre binaire? Rouge noir? Arbre Radix? B-arbre? R-tree? R * -arbre?
Un arbre est plus un modèle qu'une structure de données, et ils ont tendance à être utilisés là où les performances sont importantes (donc les détails d'implémentation comptent probablement aussi). Si la BCL incluait une sorte de classe d'arbre, vous n'auriez de toute façon qu'à rouler la vôtre
la source
Je crois qu'en
SortedDictionarytant qu'insertion log (n), les caractéristiques de récupération que vous attendez d'une structure de données d'arbre.http://msdn.microsoft.com/en-us/library/f7fta44c(VS.80).aspx
la source
SortedSet<T>est implémenté comme un arbre de recherche binaire réf .SortedDictionary<TKey, TValue>utilise en interneSortedSet<T>donc c'est aussi un arbre de recherche binaire réf .la source
Non, il n'y a pas de type "
Tree<T>-like" dans la BCL (quelque chose qui m'a toujours aussi perplexe) mais voici un bon article qui vous guidera dans l'implémentation du vôtre en C #.Je suppose que vous pourriez faire valoir que les structures de données basées sur des arbres sont moins couramment utilisées dans le type d'applications pour lesquelles .NET est habituellement utilisé (applications d'entreprise, applications de transfert de données, etc.). Pourtant, je suis d'accord avec vous, il est étrange que la BCL n'ait aucune implémentation.
la source
Cette série d'articles m'a été utile lorsque j'ai dû écrire la mienne, en particulier les parties 3 et 4.
Un examen approfondi des structures de données
la source
Il y a un TreeNode que vous pouvez utiliser. Ce n'est pas générique et caché dans les formulaires Windows et utilisé avec le contrôle treeview, mais vous pouvez également l'utiliser ailleurs.
la source