Perché non esiste una classe di albero <T> in .NET?

Question

La libreria di classi base in .NET ha alcune eccellenti strutture dati per le raccolte (Elenco, Coda, Catasta, Dizionario), ma stranamente non contiene alcuna struttura di dati per alberi binari. Questa è una struttura terribilmente utile per determinati algoritmi, come quelli che traggono vantaggio da diversi percorsi trasversali. Sto cercando un'implementazione corretta, scritta e libera.

Sono semplicemente cieco, e non trovandolo ... è sepolto da qualche parte nel BCL? In caso contrario, qualcuno può raccomandare una libreria C# /. NET libera o open-source per alberi binari? Preferibilmente uno che impiega generici.

MODIFICA: Per chiarire quello che sto cercando. Non sono interessato alle raccolte di dizionari ordinate che usano internamente un albero. In realtà sono interessato a un albero binario, uno che espone la sua struttura in modo che tu possa fare cose come estrarre sottostrutture, o eseguire traversal post-fix sui nodi. Idealmente, una tale classe potrebbe essere estesa per fornire i comportamenti di alberi specializzati (ad esempio Rosso/Nero, AVL, Bilanciato, ecc.).

Answer 1

Hai ragione, non c'è nulla nel BCL. Sospetto che ciò sia dovuto al fatto che la scelta di utilizzare un albero è in genere un dettaglio di implementazione ed è altrimenti un modo non convenzionale per accedere ai dati. Cioè, non dici "binary-search-for element # 37"; invece, dici "prendimi l'elemento # 37".

Ma hai dato un'occhiata a C5? È super pratico e ha diverse implementazioni di alberi (1, 2, 3).

Answer 2

No, non c'è alcun tipo "Tree<T> -like" nel BCL (qualcosa che mi ha sempre perplesso) ma here is a good article che vi guiderà attraverso l'implementazione del proprio in C#.

Immagino che si possa argomentare che le strutture di dati ad albero sono utilizzate meno comunemente nel tipo di applicazioni per le quali .NET viene solitamente utilizzato (app aziendali, applicazioni di spostamento dati, ecc.). Comunque, sono d'accordo con te, è strano che il BCL non abbia alcuna implementazione.

Answer 3

C'è uno TreeNode che è possibile utilizzare. Non è generico e nascosto nei moduli di Windows e utilizzato con il controllo TreeView, ma è possibile utilizzarlo anche altrove.

Answer 4

Credo che SortedDictionary come il log (n) inserire, caratteristiche di recupero che ci si aspetterebbe da una struttura dei dati dell'albero.

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

Answer 5

SortedSet<T> è implementato come un albero binario di ricerca ^ref. SortedDictionary<TKey, TValue> utilizza internamente SortedSet<T> quindi è anch'esso un albero di ricerca binario ^ref.

Answer 6

Cosa vorresti da una simile implementazione?

Albero binario? Rosso-nero? Albero Radix? B-tree? R-tree? R * -tree?

Un albero è più un modello che una struttura di dati e tendono ad essere utilizzati laddove le prestazioni sono importanti (quindi anche i dettagli di implementazione sono importanti). Se il BCL incluso una sorta di albero di una classe, dovreste solo rotolare il proprio comunque

Answer 7

Si potrebbe definire il proprio:

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

o senza chiave:

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

Answer 8

Questa serie di articoli è stato utile per me quando ho dovuto scrivere i miei specialmente le parti 3 e 4.

An Extensive Examination of Data Structures