Stellen Sie sich einen rot-schwarzen Baum vor. Gibt es immer eine Sequenz von Einfügungen und Löschungen, die es schafft?

Nehmen wir die folgende Definition eines rot-schwarzen Baums an:

1. Es ist ein binärer Suchbaum.
2. Jeder Knoten ist entweder rot oder schwarz gefärbt. Die Wurzel ist schwarz.
3. Zwei durch eine Kante verbundene Knoten können nicht gleichzeitig rot sein.
4. Hier sollte eine gute Definition eines NIL-Blattes sein, wie im Wiki. Das NIL-Blatt ist schwarz gefärbt.
5. Ein Pfad von der Wurzel zu einem beliebigen NIL-Blatt enthält die gleiche Anzahl schwarzer Knoten.

Frage

Angenommen, Sie haben die Operationen insertund deletefür den rot-schwarzen Baum implementiert . Wenn Sie nun einen gültigen rot-schwarzen Baum erhalten, gibt es immer eine Folge von insertund deleteOperationen, die ihn aufbauen?

Motivation

Diese Frage wird durch diese Frage und die Diskussion aus dieser Frage motiviert .

Persönlich glaube ich, dass, wenn Sie sich einen gültigen rot-schwarzen Baum vorstellen, der nur aus schwarzen Knoten besteht (was impliziert, dass Sie sich einen perfekt ausbalancierten Baum vorstellen), es eine Folge von insertund deleteOperationen gibt, die ihn aufbauen. Jedoch,

1. Ich weiß nicht, wie ich das genau beweisen soll
2. Ich interessiere mich auch für den allgemeineren Fall

Die Einfüge- und Löschvorgänge in einem Rot-Schwarz-Baum umfassen den Ausgleich, der zum Beibehalten der Rot-Schwarz-Eigenschaften erforderlich ist.

Das Problem bei nicht (links- oder rechts-) geneigten rotschwarzen Bäumen besteht darin, dass es mehrere Möglichkeiten gibt, die Rotschwarzheit nach dem grundlegenden Löschen oder Einfügen wiederherzustellen.
Es ist nicht das Einfügen oder Löschen, das den Baum transformiert, sondern das anschließende Neuausgleichen und Drehen, um die rote Schwärze des Baums zu erhalten / wiederherzustellen.

Die Grundbeschreibung des rot-schwarzen Baumes schreibt nicht vor, welche der möglichen Routen zu nehmen sind.
Es kann sein, dass es nicht möglich ist, herauszufinden, wie ein gegebener rot-schwarzer Baum genau rekonstruiert werden kann, da das Neuausgleichen nicht deterministisch sein muss.

Dies wurde mit nach links geneigten rot-schwarzen Bäumen "gelöst".
Es gibt nur eine Möglichkeit, den Abgleich durchzuführen. So kann jeder schiefe rot-schwarze Baum mit Einfügungen und Löschungen rekonstruiert werden, da die Neuausrichtung / Rotation auf eine spezifisch deterministische Weise erfolgt.

Dies bedeutet nicht, dass linke RB-Bäume besser oder effizienter sind, was sie einerseits durch die Verwendung deterministischer Ausgleichsregeln gewinnen, andererseits durch komplexeren Ausgleichscode verlieren.

Laut @ Antons Kommentar:
Es gibt einen Algorithmus, der die Operation Einfügen und Löschen verwendet, um einen gültigen rot-schwarzen Baum zu erstellen, der nur aus schwarzen Knoten besteht. Es verwendet Einfügungen / Löschungen, um einen Baum der Höhe zu erstellen . Zuerst können wir einen perfekt ausbalancierten rot-schwarzen Baum mit Einfügungen erstellen , dann mit Einfügungen und der gleichen Anzahl von Löschungen, in die er neu gezeichnet wird ein ganz schwarzer Baum. Der Trick dabei ist, mal die unterste rote Schicht des Baumes nach oben zu schieben, bis sie die Wurzel erreicht.h 2 h + 1 - 1 h ∗ 2 h - 1$(h+2)⋅2^{h}−1$$h$$2^{h+1}−1$$h∗2^{h-1}$$h$

Ich denke, ein vollständiger Auswuchtalgorithmus wie Day-Stout-Warren wäre jedoch effizienter.