Frage Kann jeder gültige rot-schwarze Baum existieren?


Angenommen, Sie haben eine rot-schwarzer Baum das ist ein gültiger binärer Suchbaum und verletzt keine dieser Regeln:

  • Ein Knoten ist entweder rot oder schwarz.
  • Die Wurzel ist schwarz.
  • Alle Blätter (NIL) sind schwarz.
  • Beide Kinder jedes roten Knotens sind schwarz.
  • Jeder einfache Pfad von einem gegebenen Knoten zu einem seiner Nachkommenblätter enthält dieselbe Anzahl von schwarzen Knoten.

Ein solcher rot-schwarzer Baum sieht so aus: enter image description here

Hat jeder mögliche Baum, der diese Einschränkungen erfüllt, eine Sequenz von Einfügungen und Löschungen, so dass der Rot-Schwarz-Baum erzeugt wird?

Ich stelle diese Frage, weil ich darüber nachdenke, einen Blogartikel über Rot-Schwarz-Bäume zu schreiben, und ich möchte einige Beispiele nennen.

Wenn Sie ein Gegenbeispiel testen möchten: Hier ist eine Rot-Schwarz-Baum-Implementierung in Python mit einer implementierten Funktion zum Erzeugen des Bildes.

Um die Frage zu klären: Wir machen ein Spiel.

  • Ich zeichne einen rot-schwarzen Baum, der alle Einschränkungen erfüllt.
  • Sie müssen eine Reihenfolge von Einfügungen und Löschungen finden, so dass Sie mit meinem rot-schwarzen Baum enden.

Kann ich einen rot-schwarzen Baum zeichnen, damit du nicht gewinnen kannst?

Die Farben sind wichtig! Wenn der Baum eine andere Form oder andere Farben hat, ist es nicht derselbe rot-schwarze Baum.

Sie sollten zumindest wissen, wie Sie diese zwei rot-schwarzen Bäume erzeugen: enter image description here enter image description here

Beachten Sie, dass dies nur ein Test für Sie ist, wenn es funktionieren könnte. Wenn Sie nur wissen, wie Sie diese zwei rot-schwarzen Bäume bekommen, können Sie diese Frage nicht beantworten!


11
2017-07-25 09:48


Ursprung


Antworten:


Ich glaube, dass das Einfügen der Knoten in die Breite-zuerst-Traversierung (Ebene-Reihenfolge) jeden rot-schwarzen Baum ergeben wird.

http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal

Da Sie sie in die Ebenenreihenfolge einfügen, können Sie keinen Baum haben, der weniger ausgeglichen ist als der ursprüngliche Baum. Es sind keine Löschvorgänge erforderlich, und beim Einfügen werden keine Drehungen benötigt. In Ihrem Beispiel sollten Sie sie in der folgenden Reihenfolge einfügen:

13,8,17,1,11,15,25,6,22,27

Bearbeiten: Während dies einen binären Suchbaum mit den richtigen Werten und der richtigen Form erzeugt, erzeugt dies möglicherweise nicht die richtigen Farben ... es hängt von der Implementierung der Einfügefunktion ab. Der Grund ist, dass die Definition von rot-schwarzen Bäumen Variationen in der Farbe von Knoten zulässt, wenn der Baum mehr als einen Knoten hat und voll ist und alle Blätter dieselbe Tiefe haben - nach der Definition von Wikipedia ist dies ein "perfekter" Binärbaum:

http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

Angenommen, der Baum hat drei Knoten mit den Werten {1,2,3}, wobei "2" die Wurzel ist und per Definition schwarz ist. Knoten {1,3} können entweder schwarz oder beide rot sein, ohne die rot-schwarzen Regeln zu verletzen. Eine perfekt gültige Implementierung einer rot-schwarzen Einfügung könnte also erkennen, wann der Baum "perfekt" ist und jeden Knoten schwarz färben. Solch eine Implementierung würde verhindern, jemals in der Lage zu sein, einen Baum zu konstruieren, der zum Beispiel auf jeder Ebene abwechselnd schwarz und rot wechselt.

Edit 2: Da beide Rot-Schwarz-Bäume mögliche Eingaben sind (alle drei Knoten schwarz und Knoten 1 und 3 rot), stellt sich die Frage, ob Löschungen notwendig sind. Wenn es eine Lösung gibt, sind Löschungen notwendig. Die Frage in meinem Kopf ist nun, ob es nur eine Möglichkeit gibt, eine rot-schwarze Baumeinfügung / -löschung zu implementieren. Wenn es mehr als eins gibt und wenn sie unterschiedliche Bäume ergeben, dann müsste der Spieler des Spiels die Implementierung verstehen, um die Reihenfolge von Einfügungen und Löschungen zu spezifizieren, um einen gegebenen rot-schwarzen Baum zu konstruieren. Ich weiß nicht genug über die Implementierung von rot-schwarzen Bäumen, um die Frage zu beantworten, ob es nur einen Weg gibt, sie zu implementieren, oder ob es mehr als einen gibt.


5
2017-08-04 20:37



Ich denke, der Zweig der Mathematik, der sich mit dieser Art von Problem beschäftigt, ist die Graphentheorie, und in einigen graphentheoretischen Papieren, die Eigenschaften von Rotschwarz und anderen ausgeglichenen Bäumen verifizieren, werde ich zu diesem Papier geführt: http://www.math.unipd.it/~baldan/Papers/Soft-copy-pdf/cosmicah05.pdf und http://www.math.unipd.it/~baldan/Papers/Soft-copy-pdf/cosmicah05.pdf und dieses Papier http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.1161&rep=rep1&type=pdf sollten sie in der Lage sein, Ihre Fragen zu den abstrakten Eigenschaften zu beantworten. Oder helfen Sie zumindest, Ihre Frage so zu formulieren, dass sie zu noch besseren Ressourcen führt.


3
2017-07-31 05:49



Wenn ein Baum diesen Regeln folgt:

  • Ein Knoten ist entweder rot oder schwarz.
  • Die Wurzel ist schwarz.
  • Alle Blätter (NIL) sind schwarz.
  • Beide Kinder jedes roten Knotens sind schwarz.
  • Jeder einfache Pfad von einem gegebenen Knoten zu einem seiner Nachkommenblätter enthält dieselbe Anzahl von schwarzen Knoten.

Es wird ein ausgewogener Binärbaum sein und kann Rot-Schwarz-Baum genannt werden.

Die Einfügung und Löschung von Rot-Schwarz-Bäumen haben spezielle Bedingungen und Regeln. Wenn Baum wie in Ihrem Beispiel dem Algorithmus der RB-Baumeinfügung und -löschung folgt, wird es immer ein RB-Baum sein. Während des Einfügens und Löschens wird ein unsymmetrischer Binärbaum immer in einen ausgeglichenen Baum zurückversetzt, indem Knotenfarbe, Drehknoten oder Zweig geändert werden.


3
2017-08-04 06:38



Ich denke, was Sie hier verlangen, ist ein formeller Beweis, ob irgendein willkürlicher, legitimer rot-schwarzer Baum durch eine Reihe von Einfügungen und Löschungen konstruiert werden kann, vorausgesetzt, der Baum wird nach jeder Operation neu gewichtet. Ich werde einen solchen Beweis nicht versuchen, aber ich denke, ich habe eine Idee, wie Sie einen solchen Beweis konstruieren könnten.

Ich würde erschöpfend alle möglichen Unterbäume behandeln, die alle legalen Permutationen um einen einzelnen Knoten beinhalten, und beweisen, dass er konstruiert werden kann. Damit:

  • schwarzer Knoten
    • kein Elternteil
      • linkes Kind null
        • richtiges Kind null
        • richtiges Kind nicht null
      • linkes Kind nicht null
        • richtiges Kind null
        • richtiges Kind nicht null
    • ist das linke Kind
      • das gleiche wie oben
    • ist das richtige Kind
      • das gleiche wie oben
  • roter Knoten (kann kein Elternteil haben)
    • ist das linke Kind
      • das gleiche wie oben
    • ist das richtige Kind
      • das gleiche wie oben

Und dann müssen Sie einen induktiven Schritt erstellen, der zeigt, dass jeder beliebige Baum eine Permutation der oben gezeigten Fälle ist. Es scheint ziemlich geradlinig zu sein, wenn ich es so formuliere, aber wie ich in meinem Kommentar erwähnt habe, bin ich viel zu rostig, um den tatsächlichen Beweis anzugehen.


3
2017-08-04 19:32