Warum bietet die C++ STL keine "Baum" Container an?

Question

Warum bietet der C++ STL keine "Baum"-Container und was ist stattdessen am besten zu verwenden?

Ich möchte eine Hierarchie von Objekten als Baum speichern, anstatt einen Baum als Leistungsverbesserung zu verwenden...

Answer 1

Das Problem ist, dass es keine Einheitslösung gibt. Darüber hinaus gibt es nicht einmal eine Einheits-Schnittstelle für einen Baum. Es ist also nicht einmal klar, welche Methoden eine Baumdatenstruktur bereitstellen sollte, und es ist nicht einmal klar, was ein Baum ist.

Dies erklärt, warum es darauf keine STL-Unterstützung gibt: Die STL ist für Datenstrukturen, die die meisten Menschen benötigen, bei denen im Grunde genommen alle darüber einig sind, was eine vernünftige Schnittstelle und eine effiziente Implementierung ist. Für Bäume gibt es so etwas einfach nicht.

Die grausamen Details

Wenn Sie weiter verstehen möchten, worin das Problem besteht, lesen Sie weiter. Andernfalls sollte der obige Absatz bereits ausreichen, um Ihre Frage zu beantworten.

Ich sagte, dass es nicht einmal eine gemeinsame Schnittstelle gibt. Sie könnten anderer Meinung sein, da Sie eine Anwendung im Kopf haben, aber wenn Sie weiter darüber nachdenken, werden Sie feststellen, dass es unzählige mögliche Operationen mit Bäumen gibt. Sie können entweder eine Datenstruktur haben, die die meisten davon effizient ermöglicht, aber insgesamt komplexer ist und daher einen Overhead für diese Komplexität hat, oder Sie haben eine einfachere Datenstruktur, die nur grundlegende Operationen zulässt, diese aber so schnell wie möglich macht.

Wenn Sie die vollständige Geschichte möchten, schauen Sie sich mein Papier zum Thema an. Dort finden Sie mögliche Schnittstellen, asymptotische Komplexitäten auf verschiedenen Implementierungen und eine allgemeine Beschreibung des Problems und auch verwandte Arbeiten mit weiteren möglichen Implementierungen.

Was ist ein Baum?

Es fängt bereits damit an, was Sie als Baum betrachten:

• Verwurzelt oder unverwurzelt: Die meisten Programmierer wollen verwurzelt sein, die meisten Mathematiker wollen unverwurzelt sein. (Wenn Sie sich fragen, was unverwurzelt bedeutet: A - B - C ist ein Baum, bei dem entweder A, B oder C die Wurzel sein könnte. Ein verwurzelter Baum definiert, welche davon ist. Ein unverwurzelter nicht)
• Einzelwurzel/verbunden oder Mehrwurzeln/getrennt (Baum oder Wald)
• Ist die Geschwisterreihenfolge relevant? Wenn nicht, kann die Baumstruktur intern Kinder bei Aktualisierungen neu ordnen? Wenn ja, ist die Reihenfolge der Geschwister nicht mehr definiert. Aber für die meisten Bäume ist die Geschwisterreihenfolge tatsächlich nicht sinnvoll, und es ist sehr vorteilhaft für einige Aktualisierungen, wenn die Datenstruktur Kinder bei Updates neu anordnen kann.
• Wirklich nur ein Baum oder auch DAG-Kanten (klingt seltsam, aber viele Leute, die zunächst einen Baum wollen, wollen letztendlich einen DAG)
• Gezeichnet oder unbeschriftet? Müssen Sie Daten pro Knoten speichern oder interessiert Sie nur die Baumstruktur (Letzteres kann sehr prägnant gespeichert werden)

Abfrageoperationen

Nachdem wir herausgefunden haben, was wir als Baum definieren, sollten wir Abfrageoperationen definieren: Grundlegende Operationen könnten "zu Kindern navigieren, zum Elternteil navigieren" sein, aber es gibt noch viele weitere mögliche Operationen, z. B.:

• Zum nächsten/vorherigen Geschwister navigieren: Auch wenn die meisten Menschen dies für eine ziemlich grundlegende Operation halten würden, ist es tatsächlich fast unmöglich, wenn Sie nur einen Elternzeiger oder ein Kinderarray haben. Dies zeigt Ihnen bereits, dass Sie je nach benötigten Operationen eine völlig andere Implementierung benötigen.
• In vor-/nach-Reihenfolge navigieren
• Unterbaumgröße: die Anzahl der (transitiven) Nachkommen des aktuellen Knotens (möglicherweise in O(1) oder O(log n), zählen Sie sie also nicht einfach alle auf, um sie zu zählen)
• Die Höhe des Baums im aktuellen Knoten. Das heißt, der längste Pfad von diesem Knoten zu einem Blatt. Wiederum in weniger als O(n).
• Gegeben zwei Knoten, finden Sie den kleinsten gemeinsamen Vorfahren des Knotens (mit O(1) Speicherverbrauch)
• Wie viele Knoten befinden sich zwischen Knoten A und Knoten B in einer Vor- / Nachordnung? (weniger als O(n) Laufzeit)

Ich betonte, dass das Interessante hier ist, ob diese Methoden besser als O(n) durchgeführt werden können, da das einfache Aufzählen des gesamten Baums immer eine Option ist. Je nach Anwendung kann es absolut entscheidend sein, dass einige Operationen schneller als O(n) sind, oder es ist Ihnen möglicherweise völlig egal. Nochmals, je nach Bedarf benötigen Sie vollkommen unterschiedliche Datenstrukturen hier.

Aktualisierungsoperationen

Bisher habe ich nur über Abfrageoperationen gesprochen. Aber jetzt zu Updates. Auch hier gibt es verschiedene Möglichkeiten, wie ein Baum aktualisiert werden könnte. Je nach Bedarf benötigen Sie eine mehr oder weniger ausgeklügelte Datenstruktur:

• Blattaktualisierungen (einfach): Löschen oder Hinzufügen eines Blattknotens
• Innerer Knotenaktualisierungen (schwieriger): Verschieben oder Löschen eines inneren Knotens und seine Kinder zu den Kindern seines Elternteils machen
• Unterbaumaktualisierungen (schwieriger): Verschieben oder Löschen eines in einem Knoten verwurzelten Unterbaums

Um Ihnen nur eine Vorstellung zu geben: Wenn Sie ein Kinderarray speichern und Ihre Geschwisterreihenfolge wichtig ist, kann sogar das Löschen eines Blattes O(n) sein, da alle Geschwister dahinter im Kinderarray seines Elternteils verschoben werden müssen. Wenn Sie stattdessen nur einen Elternzeiger haben, ist das Löschen eines Blattes trivialerweise O(1). Wenn es Ihnen nicht um die Reihenfolge der Geschwister geht, ist es auch O(1) für das Kinderarray, da Sie die Lücke einfach mit dem letzten Geschwister im Array ersetzen können. Dies ist nur ein Beispiel dafür, wie verschiedene Datenstrukturen Ihnen recht unterschiedliche Update-Fähigkeiten bieten können.

Das Verschieben eines ganzen Unterbaums ist wiederum trivialerweise O(1) im Falle eines Elternzeigers, kann aber O(n) sein, wenn Sie eine Datenstruktur haben, die alle Knoten z. B. in der Vorordnung speichert.

Dann gibt es noch orthogonale Überlegungen, welche Iteratoren gültig bleiben, wenn Sie Aktualisierungen durchführen. Einige Datenstrukturen müssen alle Iteratoren im gesamten Baum ungültig machen, selbst wenn Sie ein neues Blatt einfügen. Andere machen nur Iteratoren im Teil des Baums ungültig, der verändert wird. Andere behalten alle Iteratoren (außer denen für gelöschte Knoten) gültig.

Platzüberlegungen

Baumstrukturen können sehr prägnant sein. Grob gesagt reichen etwa zwei Bits pro Knoten aus, wenn Sie Speicher sparen müssen (z. B. DFUDS oder LOUDS, siehe diese Erklärung für das Wesentliche). Aber natürlich ist schon ein Elternzeiger naiv betrachtet bereits 64 Bits. Wenn Sie sich stattdessen für eine gut navigierbare Struktur entscheiden, benötigen Sie möglicherweise eher 20 Bytes pro Knoten.

Mit viel Raffinesse kann man auch eine Datenstruktur bauen, die nur einige Bits pro Eintrag benötigt, effizient aktualisiert werden kann und dennoch alle Abfrageoperationen asymptotisch schnell ermöglicht, aber das ist ein Ungetüm von Struktur, das sehr komplex ist. Ich habe einmal einen praktischen Kurs gegeben, in dem ich Graduierte dieses Papier implementieren ließ. Einige von ihnen konnten es in 6 Wochen (!) implementieren, andere sind gescheitert. Und obwohl die Struktur großartige Asymptotik hat, macht ihre Komplexität sie für sehr einfache Operationen ziemlich aufwändig.

Wieder einmal gibt es keine Einheitslösung.

Schlussfolgerung

Ich habe 5 Jahre daran gearbeitet, die beste Datenstruktur zum Darstellen eines Baums zu finden, und obwohl ich einige entwickelt habe und es eine Menge verwandte Arbeit gibt, war mein Fazit, dass es keine gibt. Je nach Anwendungsfall wird eine hochentwickelte Datenstruktur von einem einfachen Elternzeiger übertroffen. Selbst die Definition der Schnittstelle für einen Baum ist schwierig. Ich habe versucht, in meinem Papier eine zu definieren, muss aber zugeben, dass es verschiedene Anwendungsfälle gibt, in denen die von mir definierte Schnittstelle zu eng oder zu umfangreich ist. Daher bezweifle ich, dass dies jemals in der STL landen wird, da es einfach zu viele Stellknöpfe gibt.

Answer 2

Die std::map basiert auf einem Rot-Schwarz-Baum. Sie können auch andere Container verwenden, um Ihnen bei der Implementierung Ihrer eigenen Baumtypen zu helfen.

Answer 3

Auf eine gewisse Weise ist std::map ein Baum (es müssen die gleichen Leistungseigenschaften wie ein balancierter binärer Baum haben), zeigt aber nicht andere Baumfunktionalitäten. Wahrscheinlich wurde die wahrscheinliche Begründung für das Nicht-Einbeziehen einer echten Baumdatenstruktur einfach dadurch bestimmt, dass nicht alles in der STL enthalten ist. Die STL kann als Rahmenwerk betrachtet werden, das bei der Implementierung eigener Algorithmen und Datenstrukturen verwendet wird.

Generell, wenn es eine grundlegende Bibliotheksfunktionalität gibt, die Sie möchten, die nicht in der STL enthalten ist, schauen Sie sich BOOST an.

Andernfalls gibt es eine Menge von Bibliotheken da draußen, je nach den Anforderungen Ihres Baumes.

Answer 4

Alle STL-Behälter werden extern als "Sequenzen" mit einem Iterationsmechanismus dargestellt. Bäume folgen nicht diesem Idiom.

Answer 5

Ich denke, es gibt mehrere Gründe, warum es keine STL-Bäume gibt. Primär sind Bäume eine Form von rekursiver Datenstruktur, die, wie ein Container (Liste, Vektor, Menge), sehr unterschiedliche Feinstrukturen aufnehmen können und dies die richtigen Entscheidungen schwierig macht. Sie lassen sich auch sehr einfach in einfacher Form mit der STL konstruieren.

Ein endlicher Wurzelbaum kann als Container betrachtet werden, der einen Wert oder eine Nutzlast, sagen wir eine Instanz einer Klasse A, und eine möglicherweise leere Sammlung von verwurzelten Teilbäumen enthält; Bäume mit leerer Sammlung von Teilbäumen werden als Blätter betrachtet.

template
struct unordered_tree : std::set, A
{};

template
struct b_tree : std::vector, A
{};

template
struct planar_tree : std::list, A
{};

Man muss ein wenig über die Iteratorgestaltung usw. nachdenken und welche Produkt- und Koproduktoperationen man zwischen den Bäumen zulässt und effizient definiert - und die ursprüngliche STL muss gut geschrieben sein - so dass der leere Satz, Vektor oder Listencontainer im Standardfall wirklich leer von jeder Nutzlast ist.

Bäume spielen eine wesentliche Rolle in vielen mathematischen Strukturen (siehe die klassischen Arbeiten von Butcher, Grossman und Larsen; auch die Arbeiten von Connes und Kriemer, um Beispiele zu sehen, wie sie verbunden werden können und wie sie verwendet werden, um aufzuzählen). Es ist nicht richtig zu denken, dass ihre Rolle einfach darin besteht, bestimmte andere Operationen zu erleichtern. Sie erleichtern diese Aufgaben vielmehr aufgrund ihrer grundlegenden Rolle als Datenstruktur.

Allerdings gibt es neben Bäumen auch "Ko-Bäume"; die oben genannten Bäume haben alle die Eigenschaft, dass wenn man die Wurzel löscht, man alles löscht.

Betrachten Sie Iteratoren auf dem Baum, wahrscheinlich würden sie als einfacher Stapel von Iteratoren realisiert, zu einem Knoten und seinem Elternteil, ... bis zur Wurzel.

template
struct node_iterator : std::stack{
operator*() {return *back();}
...};

Allerdings können Sie so viele haben, wie Sie wollen; gemeinsam bilden sie einen "Baum", aber alle Pfeile zeigen in Richtung zur Wurzel, dieser Ko-Baum kann durch Iteratoren in Richtung des trivialen Iterators und der Wurzel durchiteriert werden; er kann jedoch nicht quer oder nach unten navigiert werden (die anderen Iteratoren sind ihm nicht bekannt), noch kann das Ensemble der Iteratoren gelöscht werden, außer man behält alle Instanzen im Auge.

Bäume sind unglaublich nützlich, sie haben viel Struktur, was es zu einer ernsten Herausforderung macht, den definitiv richtigen Ansatz zu finden. Meiner Meinung nach ist das der Grund, warum sie nicht in der STL implementiert sind. Außerdem habe ich in der Vergangenheit gesehen, dass Leute religiös wurden und die Idee einer Art von Container, der Instanzen ihres eigenen Typs enthält, als herausfordernd empfanden - aber sie müssen sich damit auseinandersetzen - das ist, was ein Baumtyp darstellt - er ist ein Knoten, der eine möglicherweise leere Sammlung von (kleineren) Bäumen enthält. Die aktuelle Sprache erlaubt es ohne Herausforderung, solange der Standardkonstruktor für Container keinen Speicher auf dem Heap (oder sonst wo) für ein B allokiert, usw.

**

Ich persönlich würde mich freuen, wenn dies in guter Form seinen Weg in den Standard finden würde.

**