Dlaczego w .NET nie ma klasy Tree <T>?

Biblioteka klas bazowych w .NET ma doskonałe struktury danych dla kolekcji (lista, kolejka, stos, słownik), ale, co dziwne, nie zawiera żadnych struktur danych dla drzew binarnych. Jest to bardzo przydatna struktura dla niektórych algorytmów, na przykład wykorzystujących różne ścieżki przejścia. Szukam poprawnie napisanej, darmowej realizacji.

Czy jestem po prostu ślepy i nie znajduję go ... czy to jest zakopane gdzieś w BCL? Jeśli nie, czy ktoś może polecić darmową lub otwartą bibliotekę C # / .NET dla drzew binarnych? Najlepiej taki, który wykorzystuje leki generyczne.

EDYCJA: Aby wyjaśnić, czego szukam. Nie interesują mnie uporządkowane zbiory słowników, które wewnętrznie używają drzewa. Właściwie interesuje mnie drzewo binarne - takie, które ujawnia swoją strukturę, dzięki czemu można robić takie rzeczy, jak wyodrębnianie poddrzew lub przeprowadzanie przemierzania węzłów po naprawie. W idealnym przypadku taka klasa mogłaby zostać rozszerzona, aby zapewnić zachowanie wyspecjalizowanych drzew (np. Red / Black, AVL, Balanced, itp.).

Masz rację, w BCL nie ma nic. Podejrzewam, że dzieje się tak dlatego, że wybór, czy użyć drzewa, jest zwykle szczegółem implementacji, a poza tym jest niekonwencjonalnym sposobem dostępu do danych. Oznacza to, że nie mówisz „binarnego wyszukiwania elementu nr 37”; zamiast tego mówisz „zdobądź element # 37”.

Ale czy spojrzałeś na C5 ? Jest to bardzo przydatne i ma kilka implementacji drzew ( 1 , 2 , 3 ).

Możesz zdefiniować własne:

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

Lub bez klucza:

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

Czego byś chciał od takiej realizacji?

Drzewo binarne? Czerwony czarny? Drzewo Radix? B-drzewo? R-drzewo? R * -drzewo?

Drzewo jest bardziej wzorcem niż strukturą danych i jest zwykle używane tam, gdzie liczy się wydajność (więc szczegóły implementacji prawdopodobnie też mają znaczenie). Gdyby BCL zawierało jakąś klasę drzewa, i tak musiałbyś rzucić tylko własną

Uważam, że SortedDictionaryjako wstawka log (n), parametry pobierania, których można oczekiwać od struktury danych drzewa.

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

SortedSet<T>jest implementowany jako binarne drzewo wyszukiwania ^ref . SortedDictionary<TKey, TValue>wewnętrznie korzysta z SortedSet<T>tego, więc jest również binarnym drzewem wyszukiwania ^ref .

Nie, Tree<T>w BCL nie ma żadnego typu „ -podobnego” (coś, co zawsze mnie również intrygowało), ale tutaj jest dobry artykuł , który przeprowadzi Cię przez proces implementacji własnego w C #.

Myślę, że można argumentować, że struktury danych oparte na drzewach są rzadziej używane w aplikacjach, do których zwykle używa się platformy .NET (aplikacje biznesowe, aplikacje do przenoszenia danych itp.). Mimo to zgadzam się z tobą, to dziwne, że BCL w ogóle nie ma implementacji.

Ta seria artykułów była dla mnie pomocna, gdy musiałem napisać własną, zwłaszcza część 3 i 4.

Obszerne badanie struktur danych

Istnieje TreeNode, którego możesz użyć. Nie jest on ogólny i ukryty w formularzach systemu Windows i używany z kontrolką treeview, ale można go również używać w innym miejscu.