Warum gibt es in .NET keine Tree <T> -Klasse?

86

Die Basisklassenbibliothek in .NET verfügt über einige hervorragende Datenstrukturen für Sammlungen (Liste, Warteschlange, Stapel, Wörterbuch), enthält jedoch seltsamerweise keine Datenstrukturen für Binärbäume. Dies ist eine äußerst nützliche Struktur für bestimmte Algorithmen, z. B. solche, die unterschiedliche Durchquerungspfade nutzen. Ich suche eine korrekt geschriebene, kostenlose Implementierung.

Bin ich einfach blind und finde es nicht ... ist es irgendwo in der BCL begraben? Wenn nicht, kann jemand eine kostenlose oder Open-Source-C # /. NET-Bibliothek für Binärbäume empfehlen? Vorzugsweise eine, die Generika verwendet.

EDIT: Um zu klären, wonach ich suche. Ich bin nicht an geordneten Wörterbuchsammlungen interessiert, die intern einen Baum verwenden. Eigentlich interessiert mich ein Binärbaum - einer, der seine Struktur verfügbar macht, sodass Sie beispielsweise Teilbäume extrahieren oder die Knoten nach dem Fixieren durchlaufen können. Idealerweise könnte eine solche Klasse erweitert werden, um das Verhalten spezialisierter Bäume (z. B. Rot / Schwarz, AVL, Ausgeglichen usw.) bereitzustellen.

LBushkin
quelle
Einverstanden. Ich muss gelegentlich (in O (Log N) Zeit) die beiden Knoten finden, die einen Wert gebunden haben (wenn der Wert nicht in der Sammlung gefunden wird). Zum Beispiel enthält die Sammlung (Baum) 13 und 17 (unter anderem) und ich suche nach dem größten kleiner und dem kleinsten größer als 16. Ein Baum könnte dies tun, aber Wörterbücher, sortierte Listen und Hash-Tabellen nehmen O (N) .
Les

Antworten:

31

Du hast recht, es gibt nichts in der BCL. Ich vermute, dies liegt daran, dass die Wahl, ob ein Baum verwendet werden soll, in der Regel ein Implementierungsdetail darstellt und ansonsten eine unkonventionelle Methode für den Zugriff auf Daten darstellt. Das heißt, Sie sagen nicht "binäres Suchelement # 37"; Stattdessen sagst du "Hol mir Element Nr. 37".

Aber haben Sie sich C5 angesehen ? Es ist sehr praktisch und sie haben mehrere Baumimplementierungen ( 1 , 2 , 3 ).

John Feminella
quelle
3
C5 unterstützt Rot-Schwarz-Bäume, nicht B-Baum. Es sind Unterschiede, über die sich die Menschen bewusst sein sollten. B-Tree ist optimaler für einen festplattenbasierten Baum oder einen großen speicherbasierten Baum. Es werden mehr Knoten an derselben Stelle gespeichert, sodass Sie eine bessere Prozessor-Cache-Leistung erzielen und das Schreiben auf die Festplatte schneller lesen können.
Anthony Lambert
68

Sie können Ihre eigenen definieren:

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

Oder ohne Schlüssel:

public class MyTree<V> : HashSet<MyTree<V>>
{
    public V Value { get; set; }
}
Jason
quelle
Dies setzt jedoch voraus, dass Sie wissen, wie viele Baumebenen Sie beim Kompilieren verarbeiten werden. Bin ich falsch?
Veverke
1
Nein, der C # -Compiler unterstützt diese Syntax.
Jason
2
Beachten Sie, dass die Elemente auf diese Weise nicht geordnet sind
Sebastian
@Veverke Vielleicht haben Sie an C ++ - Vorlagen gedacht. .NET-Generika sind Laufzeittypen.
Tom Blodget
Ich bin neugierig. Wie benutzt du das? Praktisch? Irgendeine Probe?
Syaiful Nizam Yahya
39

Was möchten Sie von einer solchen Implementierung?

Binärer Baum? Rot schwarz? Radixbaum? B-Baum? R-Baum? R * -Baum?

Ein Baum ist eher ein Muster als eine Datenstruktur und wird in der Regel dort verwendet, wo es auf die Leistung ankommt (daher sind wahrscheinlich auch Implementierungsdetails von Bedeutung). Wenn die BCL eine Art Baumklasse enthalten würde, müssten Sie sowieso nur Ihre eigene würfeln

Alun Harford
quelle
1
Beste Antwort für den "Warum" -Teil der Frage.
Joel Coehoorn
Und das sind nur die Suchbäume. Es gibt auch Ausdrucksbäume, Entscheidungsprobleme, ...
Henk Holterman
In der Tat sind die Details der Implementierung von Bedeutung. In meinem Fall möchte ich einige Algorithmen implementieren, die im Rahmen einer Reihe von Transformationen unterschiedliche Durchläufe (Infix, Postfix) für einen organisierten Datensatz durchführen. Eine Baumstruktur ist die eleganteste Art, mein Problem zu lösen.
LBushkin
10
In einem Paralleluniversum stellt jemand die Frage: "Warum gibt es in .Net keine Listentypen?" Und er erhält die Antwort: "Was möchten Sie von einer solchen Implementierung? Ein Array? Eine verknüpfte Liste? Eine Warteschlange? A. Wörterbuch?" Ich denke, das ist keine Antwort.
Rymdsmurf
12

SortedSet<T>wird als binärer Suchbaum ref implementiert . SortedDictionary<TKey, TValue>intern verwendet, SortedSet<T>so ist es auch ein binärer Suchbaum ref .

Matt Brunell
quelle
5
Leider handelt es sich lediglich um Implementierungen geordneter Karten und Listen. Beides ist für die Wiederverwendung als Binärbaum nicht hilfreich - diese Baumstrukturen sind lediglich ein Implementierungsdetail der Sammlung. Ich suche tatsächlich nach einer Klasse, die die Baumstruktur verfügbar macht.
LBushkin
9

Nein, es gibt keinen " Tree<T>ähnlichen" Typ in der BCL (was mich auch immer verwirrt hat), aber hier ist ein guter Artikel , der Sie durch die Implementierung Ihres eigenen in C # führt.

Ich denke, Sie könnten das Argument vorbringen, dass baumbasierte Datenstrukturen in der Art von Anwendungen, für die .NET normalerweise verwendet wird (Geschäftsanwendungen, Apps zum Verschieben von Daten usw.), weniger häufig verwendet werden. Trotzdem stimme ich Ihnen zu, es ist seltsam, dass die BCL überhaupt keine Implementierung hat.

Andrew Hare
quelle
-5

Es gibt einen TreeNode, den Sie verwenden können. Es ist nicht generisch und in Windows-Formularen versteckt und wird mit dem Treeview-Steuerelement verwendet. Sie können es jedoch auch an anderer Stelle verwenden.

Joel Coehoorn
quelle
Ja, aber es hat nur eine Tag-Eigenschaft von System.Object ype. Kein generischer <T> -Parameter
Henk Holterman
3
Ich finde es immer komisch, solche Sachen zu machen. Bei Ihrem speziellen Beispiel ist dies weniger sichtbar. Wenn Benutzer jedoch Klassen aus beispielsweise Abhängigkeiten routinemäßig neu verwenden, kann dies zu schwer zu erklärenden Abhängigkeiten führen und Sie in Schwierigkeiten bringen, wenn sich die neu zugewiesene Klasse auf unerwartete Weise ändert Abhängigkeitsversionen.
Paul Morie
4
Was wäre der Gewinn, wenn man es benutzt? Ein Baumknoten enthält normalerweise keine relevanten Funktionen. Es enthält nur Verweise auf Kinder und schließlich auf Eltern. Kein Grund, eine System.Windows.Forms-Klasse dafür zu missbrauchen! Schreiben Sie es einfach selbst - in einer Minute oder weniger.
Benutzer492238