Spreizbäume sind die selbstausgleichenden oder selbstangepassten binären Suchbäume. Mit anderen Worten können wir sagen, dass die Spreizbäume die Varianten der binären Suchbäume sind. Voraussetzung für die Splay-Bäume ist, dass wir über die binären Suchbäume Bescheid wissen sollten.

Wie wir bereits wissen, beträgt die zeitliche Komplexität eines binären Suchbaums in jedem Fall. Die zeitliche Komplexität eines binären Suchbaums beträgt im Durchschnitt O(logn) und die Zeitkomplexität beträgt im schlimmsten Fall O(n). In einem binären Suchbaum ist der Wert des linken Teilbaums kleiner als der Wurzelknoten und der Wert des rechten Teilbaums größer als der Wurzelknoten. in einem solchen Fall wäre die zeitliche Komplexität O(logn) . Wenn der Binärbaum links- oder rechtsschief ist, wäre die Zeitkomplexität O(n). Um die Schiefe zu begrenzen, wird die AVL und Rot-Schwarzer Baum kam ins Bild, haben O(logn ) Zeitkomplexität für alle Operationen in allen Fällen. Wir können diese Zeitkomplexität auch verbessern, indem wir praktischere Implementierungen durchführen, also den neuen Baum Was ist ein Splay-Baum?

Ein Spreizbaum ist ein selbstausgleichender Baum, aber AVL- und Rot-Schwarz-Bäume sind dann auch selbstausgleichende Bäume. Was den Spreizbaum einzigartig macht, sind zwei Bäume. Es verfügt über eine zusätzliche Eigenschaft, die es einzigartig macht: die Spreizbarkeit.

Ein Spreizbaum enthält die gleichen Operationen wie ein Binärer Suchbaum , d. h. Einfügen, Löschen und Suchen, aber es enthält auch eine weitere Operation, nämlich Spreizen. Also. Auf alle Operationen im Spreizbaum folgt Spreizung.

Spreizbäume sind keine streng ausbalancierten Bäume, aber sie sind ungefähr ausbalancierte Bäume. Lassen Sie uns den Suchvorgang im Spreizbaum verstehen.

Angenommen, wir möchten 7 Elemente im Baum durchsuchen, was unten gezeigt wird:

Um ein beliebiges Element im Spreizbaum zu durchsuchen, führen wir zunächst die standardmäßige binäre Suchbaumoperation durch. Da 7 kleiner als 10 ist, befinden wir uns links vom Wurzelknoten. Nachdem wir den Suchvorgang durchgeführt haben, müssen wir eine Spreizung durchführen. Spreizen bedeutet hier, dass die Operation, die wir an einem beliebigen Element ausführen, nach einigen Neuanordnungen zum Wurzelknoten werden sollte. Die Neuordnung des Baumes erfolgt durch die Rotationen.

Hinweis: Der Spreizbaum kann als selbstangepasster Baum definiert werden, in dem jede an dem Element ausgeführte Operation den Baum neu anordnet, sodass das Element, an dem die Operation ausgeführt wurde, zum Wurzelknoten des Baums wird.

Rotationen

Es gibt sechs Arten von Rotationen, die zum Spreizen verwendet werden:

1. Zick-Rotation (Rechtsdrehung)
2. Zackendrehung (Linksdrehung)
3. Zig Zag (Zig gefolgt von Zag)
4. Zag Zick (Zag gefolgt von Zick)
5. Zig Zick (zwei Rechtsdrehungen)
6. Zag Zag (zwei Linksdrehungen)

Erforderliche Faktoren für die Auswahl einer Rotationsart

Die folgenden Faktoren werden bei der Auswahl einer Rotationsart berücksichtigt:

• Hat der Knoten, den wir drehen möchten, einen Großelternknoten?
• Ist der Knoten linkes oder rechtes Kind des Elternknotens?
• Ist der Knoten linkes oder rechtes Kind des Großelternteils?

Fälle für die Rotationen

Fall 1: Wenn der Knoten keinen Großelternknoten hat und es sich um das rechte Kind des Elternknotens handelt, führen wir die Linksrotation durch; andernfalls wird die Rechtsdrehung durchgeführt.

Fall 2: Wenn der Knoten einen Großelternknoten hat, dann basierend auf den folgenden Szenarien: Die Drehung würde durchgeführt werden:

Szenario 1: Wenn der Knoten rechts vom übergeordneten Knoten liegt und der übergeordnete Knoten auch rechts vom übergeordneten Knoten liegt, dann Zick-Zick-Rechts-Rechts-Rotation ist durchgeführt.

Szenario 2: Wenn sich der Knoten links von einem übergeordneten Knoten befindet, der übergeordnete Knoten jedoch rechts von seinem übergeordneten Knoten, dann Zick-Zack-Rechts-Links-Rotation ist durchgeführt.

Szenario 3: Wenn der Knoten rechts vom übergeordneten Knoten liegt und der übergeordnete Knoten rechts vom übergeordneten Knoten liegt, dann Zick-Zick-Links-Links-Rotation ist durchgeführt.

Szenario 4: Wenn sich der Knoten rechts von einem übergeordneten Knoten befindet, der übergeordnete Knoten jedoch links von seinem übergeordneten Knoten, dann Zick-Zack-Rechts-Links-Rotation ist durchgeführt.

Lassen Sie uns nun die obigen Rotationen anhand von Beispielen verstehen.

Um den Baum neu anzuordnen, müssen wir einige Drehungen durchführen. Im Spreizbaum gibt es folgende Arten von Rotationen:

Zick-Rotationen

Die Zick-Zack-Rotationen werden verwendet, wenn das zu durchsuchende Element entweder ein Wurzelknoten oder das untergeordnete Element eines Wurzelknotens (d. h. das linke oder das rechte untergeordnete Element) ist.

Die folgenden Fälle können während der Suche im Spreizbaum vorhanden sein:

Fall 1: Wenn das Suchelement ein Wurzelknoten des Baums ist.

Fall 2: Wenn das Suchelement ein untergeordnetes Element des Stammknotens ist, gibt es zwei Szenarios:

1. Wenn es sich bei dem Kind um ein Linkskind handelt, wird die Rechtsdrehung durchgeführt, die sogenannte Zick-Rechts-Drehung.
2. Wenn es sich bei dem Kind um ein Rechtskind handelt, wird die Linksdrehung durchgeführt, die sogenannte Zickzack-Linksdrehung.

Schauen wir uns die beiden oben genannten Szenarien anhand eines Beispiels an.

Betrachten Sie das folgende Beispiel:

Im obigen Beispiel müssen wir 7 Elemente im Baum suchen. Wir werden die folgenden Schritte ausführen:

Schritt 1: Zuerst vergleichen wir 7 mit einem Wurzelknoten. Da 7 kleiner als 10 ist, handelt es sich um ein linkes Kind des Wurzelknotens.

Schritt 2: Sobald das Element gefunden ist, führen wir das Spreizen durch. Die Rechtsdrehung wird durchgeführt, sodass 7 zum Wurzelknoten des Baums wird, wie unten gezeigt:

Betrachten wir ein anderes Beispiel.

Im obigen Beispiel müssen wir 20 Elemente im Baum durchsuchen. Wir werden die folgenden Schritte ausführen:

Schritt 1: Zuerst vergleichen wir 20 mit einem Wurzelknoten. Da 20 größer als der Wurzelknoten ist, handelt es sich um ein rechtes Kind des Wurzelknotens.

Schritt 2: Sobald das Element gefunden ist, führen wir das Spreizen durch. Die Linksdrehung wird durchgeführt, sodass das 20. Element zum Wurzelknoten des Baums wird.

Zick-Zick-Rotationen

Manchmal kommt es vor, dass das zu durchsuchende Objekt sowohl einen Elternteil als auch einen Großelternteil hat. In diesem Fall müssen wir zum Spreizen vier Rotationen durchführen.

Lassen Sie uns diesen Fall anhand eines Beispiels verstehen.

Angenommen, wir müssen ein Element im Baum suchen, der unten gezeigt wird:

Schritt 1: Zuerst müssen wir eine Standard-BST-Suchoperation durchführen, um das 1-Element zu durchsuchen. Da 1 kleiner als 10 und 7 ist, befindet es sich links vom Knoten 7. Daher hat Element 1 sowohl ein Elternelement, d. h. 7, als auch ein Großelternelement, d. h. 10.

Schritt 2: In diesem Schritt müssen wir das Spreizen durchführen. Wir müssen Knoten 1 mithilfe einiger Drehungen zum Wurzelknoten machen. In diesem Fall können wir nicht einfach eine Zick- oder Zack-Rotation durchführen; Wir müssen eine Zick-Zack-Rotation implementieren.

Um Knoten 1 als Wurzelknoten zu machen, müssen wir zwei Rechtsdrehungen durchführen, die als Zick-Zack-Rotationen bekannt sind. Wenn wir die Rechtsdrehung durchführen, bewegt sich Knoten 10 nach unten und Knoten 7 nach oben, wie in der folgenden Abbildung dargestellt:

Auch hier führen wir eine Zickzack-Rechtsdrehung durch, Knoten 7 bewegt sich nach unten und Knoten 1 bewegt sich nach oben, wie unten gezeigt:

Wie wir in der obigen Abbildung sehen, ist Knoten 1 zum Wurzelknoten des Baums geworden; Daher ist die Suche abgeschlossen.

Angenommen, wir möchten im folgenden Baum nach 20 suchen.

Um 20 zu suchen, müssen wir zwei Linksdrehungen durchführen. Im Folgenden sind die Schritte aufgeführt, die zum Durchsuchen von 20 Knoten erforderlich sind:

Schritt 1: Zuerst führen wir die Standard-BST-Suchoperation durch. Da 20 größer als 10 und 15 ist, befindet es sich rechts von Knoten 15.

Schritt 2: Der zweite Schritt besteht darin, das Spreizen durchzuführen. In diesem Fall würden zwei Linksdrehungen durchgeführt. Bei der ersten Drehung bewegt sich Knoten 10 nach unten und Knoten 15 nach oben, wie unten gezeigt:

Bei der zweiten Drehung nach links bewegt sich Knoten 15 nach unten und Knoten 20 wird zum Wurzelknoten des Baums, wie unten gezeigt:

Wie wir beobachtet haben, werden zwei Linksdrehungen durchgeführt; Daher wird es als Zick-Zick-Linksrotation bezeichnet.

Zick-Zack-Rotationen

Bisher haben wir gelesen, dass sowohl Eltern als auch Großeltern entweder in einer RR- oder LL-Beziehung stehen. Jetzt sehen wir die RL- oder LR-Beziehung zwischen dem Elternteil und dem Großelternteil.

Lassen Sie uns diesen Fall anhand eines Beispiels verstehen.

Angenommen, wir möchten 13 Elemente im unten gezeigten Baum durchsuchen:

Schritt 1: Zuerst führen wir eine Standard-BST-Suchoperation durch. Da 13 größer als 10, aber kleiner als 15 ist, ist Knoten 13 das linke Kind von Knoten 15.

Schritt 2: Da sich Knoten 13 links von Knoten 15 und Knoten 15 rechts von Knoten 10 befindet, besteht eine RL-Beziehung. Zuerst führen wir die Rechtsdrehung an Knoten 15 durch, und 15 bewegt sich nach unten und Knoten 13 nach oben, wie unten gezeigt:

Dennoch ist Knoten 13 nicht der Wurzelknoten und 13 befindet sich rechts vom Wurzelknoten, daher führen wir eine Linksdrehung durch, die als Zackenrotation bezeichnet wird. Der Knoten 10 wird nach unten verschoben und 13 wird zum Wurzelknoten, wie unten gezeigt:

Wie wir im obigen Baum sehen können, ist Knoten 13 zum Wurzelknoten geworden; Daher ist die Suche abgeschlossen. In diesem Fall haben wir zuerst die Zickzack-Rotation und dann die Zack-Rotation durchgeführt; Daher spricht man von einer Zick-Zack-Rotation.

Zick-Zack-Rotation

Lassen Sie uns diesen Fall anhand eines Beispiels verstehen.

Angenommen, wir möchten 9 Elemente im Baum durchsuchen, der unten gezeigt wird:

Schritt 1: Zuerst führen wir die Standard-BST-Suchoperation durch. Da 9 kleiner als 10, aber größer als 7 ist, ist es das rechte Kind von Knoten 7.

Schritt 2: Da sich Knoten 9 rechts von Knoten 7 und Knoten 7 links von Knoten 10 befindet, besteht eine LR-Beziehung. Zuerst führen wir die Linksdrehung an Knoten 7 durch. Knoten 7 bewegt sich nach unten und Knoten 9 nach oben, wie unten gezeigt:

Dennoch ist der Knoten 9 kein Wurzelknoten und 9 befindet sich links vom Wurzelknoten, daher führen wir die Rechtsdrehung durch, die als Zick-Zack-Rotation bekannt ist. Nach der Rechtsdrehung wird Knoten 9 zum Wurzelknoten, wie unten gezeigt:

Wie wir im obigen Baum sehen können, ist Knoten 13 ein Wurzelknoten; Daher ist die Suche abgeschlossen. In diesem Fall haben wir zuerst die Zickzackdrehung (Linksdrehung) und dann die Zickzackdrehung (Rechtsdrehung) durchgeführt, daher spricht man von einer Zickzackdrehung.

Vorteile des Splay-Baums

• Im Spreizbaum müssen wir die zusätzlichen Informationen nicht speichern. Im Gegensatz dazu müssen wir in AVL-Bäumen den Ausgleichsfaktor jedes Knotens speichern, der zusätzlichen Platz benötigt, und Rot-Schwarz-Bäume erfordern außerdem die Speicherung eines zusätzlichen Informationsbits, das die Farbe des Knotens angibt, entweder Rot oder Schwarz.
• Es ist der schnellste Typ eines binären Suchbaums für verschiedene praktische Anwendungen. Es wird verwendet in Windows NT- und GCC-Compiler .
• Es bietet eine bessere Leistung, da die Knoten, auf die häufig zugegriffen wird, näher an den Wurzelknoten rücken, wodurch auf die Elemente in Spreizbäumen schneller zugegriffen werden kann. Es wird in der Cache-Implementierung verwendet, da die zuletzt aufgerufenen Daten im Cache gespeichert werden, sodass wir für den Zugriff auf die Daten nicht auf den Speicher zurückgreifen müssen und es weniger Zeit in Anspruch nimmt.

Nachteil des Splay-Baums

Der größte Nachteil des Spreizbaums wäre, dass die Bäume nicht streng ausbalanciert sind, d. h. sie sind grob ausbalanciert. Manchmal sind die Spreizbäume linear, sodass eine O(n)-Zeitkomplexität erforderlich ist.

Einfügevorgang im Splay-Baum

Im Einfügen Bei der Operation fügen wir zunächst das Element in den Baum ein und führen dann die Spreizoperation für das eingefügte Element durch.

15, 10, 17, 7

Schritt 1: Zuerst fügen wir Knoten 15 in den Baum ein. Nach dem Einfügen müssen wir eine Spreizung durchführen. Da 15 ein Wurzelknoten ist, müssen wir kein Spreizen durchführen.

Schritt 2: Das nächste Element ist 10. Da 10 kleiner als 15 ist, ist Knoten 10 das linke Kind von Knoten 15, wie unten gezeigt:

Jetzt treten wir auf spreizen . Um 10 als Wurzelknoten zu erstellen, führen wir die Rechtsdrehung durch, wie unten gezeigt:

Schritt 3: Das nächste Element ist 17. Da 17 größer als 10 und 15 ist, wird es das rechte Kind von Knoten 15.

Jetzt führen wir das Spreizen durch. Da 17 sowohl einen Elternteil als auch einen Großelternteil hat, werden wir Zick-Zack-Rotationen durchführen.

In der obigen Abbildung können wir beobachten, dass 17 zum Wurzelknoten des Baums wird. Daher ist die Einfügung abgeschlossen.

Schritt 4: Das nächste Element ist 7. Da 7 kleiner als 17, 15 und 10 ist, bleibt Knoten 7 untergeordnetes Element von 10.

Jetzt müssen wir den Baum spreizen. Da 7 sowohl ein Elternteil als auch ein Großelternteil hat, führen wir zwei Rechtsdrehungen durch, wie unten gezeigt:

Trotzdem ist Knoten 7 kein Wurzelknoten, sondern ein linkes Kind des Wurzelknotens, d. h. 17. Wir müssen also noch eine Rechtsdrehung durchführen, um Knoten 7 wie unten gezeigt zu einem Wurzelknoten zu machen:

Algorithmus für den Einfügungsvorgang

 Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n) 

Im obigen Algorithmus ist T der Baum und n der Knoten, den wir einfügen möchten. Wir haben eine temporäre Variable erstellt, die die Adresse des Wurzelknotens enthält. Wir werden die while-Schleife ausführen, bis der Wert von temp NULL wird.

Sobald das Einfügen abgeschlossen ist, wird das Spreizen durchgeführt

Algorithmus für den Spreizvorgang

 Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y 

In der obigen Implementierung ist x der Knoten, an dem die Drehung durchgeführt wird, während y das linke Kind des Knotens x ist.

Implementierung von left.rotation(T, x)

 left.rotation(T, x) y=x->right x->right = y->left y->left = x return y 

In der obigen Implementierung ist x der Knoten, an dem die Drehung durchgeführt wird, und y ist das rechte Kind des Knotens x.

Löschung im Splay-Baum

Da wir wissen, dass Spreizbäume die Varianten des binären Suchbaums sind, ähnelt der Löschvorgang im Spreizbaum dem BST, der einzige Unterschied besteht jedoch darin, dass auf den Löschvorgang in Spreizbäumen der Spreizvorgang folgt.

Arten von Löschungen:

Es gibt zwei Arten von Löschungen in den Spreizbäumen:

1. Bottom-up-Spreizung
2. Spreizung von oben nach unten

Bottom-up-Spreizung

Beim Bottom-Up-Spreizen löschen wir zunächst das Element aus dem Baum und führen dann das Spreizen auf dem gelöschten Knoten durch.

Lassen Sie uns das Löschen im Splay-Baum verstehen.

Angenommen, wir möchten 12, 14 aus dem unten gezeigten Baum löschen:

Java wandelt Zeichen in Zeichenfolge um

• Zuerst führen wir einfach den Standard-BST-Löschvorgang durch, um 12 Elemente zu löschen. Da 12 ein Blattknoten ist, löschen wir den Knoten einfach aus dem Baum.

Der Löschvorgang ist noch nicht abgeschlossen. Wir müssen den übergeordneten Knoten des gelöschten Knotens spreizen, d. h. 10. Wir müssen eine Leistung erbringen Spreizen(10) auf dem Baum. Wie wir im obigen Baum sehen können, befindet sich 10 rechts von Knoten 7 und Knoten 7 links von Knoten 13. Wir führen also zuerst die Linksdrehung an Knoten 7 und dann die Rechtsdrehung an Knoten durch 13, wie unten gezeigt:

Dennoch ist Knoten 10 kein Wurzelknoten; Knoten 10 ist das linke Kind des Wurzelknotens. Wir müssen also die richtige Drehung am Wurzelknoten durchführen, d. h. 14, um Knoten 10 zu einem Wurzelknoten zu machen, wie unten gezeigt:

• Jetzt müssen wir das 14. Element aus dem Baum löschen, was unten gezeigt wird:

Da wir wissen, dass wir den internen Knoten nicht einfach löschen können. Wir werden den Wert des Knotens entweder durch ersetzen inorder Vorgänger oder ungeordneter Nachfolger . Angenommen, wir verwenden einen Inorder-Nachfolger, bei dem wir den Wert durch den niedrigsten Wert ersetzen, der im rechten Teilbaum vorhanden ist. Der niedrigste Wert im rechten Teilbaum von Knoten 14 ist 15, daher ersetzen wir den Wert 14 durch 15. Da Knoten 14 zum Blattknoten wird, können wir ihn einfach wie unten gezeigt löschen:

Der Löschvorgang ist jedoch noch nicht abgeschlossen. Wir müssen noch eine weitere Operation durchführen, nämlich das Spreizen, bei dem wir den übergeordneten Knoten des gelöschten Knotens zum Wurzelknoten machen müssen. Vor dem Löschen war der übergeordnete Knoten von Knoten 14 der Wurzelknoten, also 10, daher müssen wir in diesem Fall eine Spreizung durchführen.

Spreizung von oben nach unten

Beim Top-Down-Spreizen führen wir zunächst das Spreizen durch, auf dem die Löschung durchgeführt werden soll, und löschen dann den Knoten aus dem Baum. Sobald das Element gelöscht ist, führen wir den Join-Vorgang durch.

Lassen Sie uns die Top-Down-Spreizung anhand eines Beispiels verstehen.

Angenommen, wir möchten 16 aus dem unten gezeigten Baum löschen:

Schritt 1: Beim Top-Down-Spreizen führen wir zunächst das Spreizen auf dem Knoten 16 durch. Der Knoten 16 hat sowohl einen Eltern- als auch einen Großelternknoten. Der Knoten 16 befindet sich rechts von seinem übergeordneten Knoten und der übergeordnete Knoten befindet sich ebenfalls rechts von seinem übergeordneten Knoten. Es handelt sich also um eine Zick-Zack-Situation. In diesem Fall führen wir zunächst die Linksdrehung an Knoten 13 und dann 14 durch, wie unten gezeigt:

Der Knoten 16 ist immer noch kein Wurzelknoten und ein rechtes Kind des Wurzelknotens. Daher müssen wir eine Linksdrehung am Knoten 12 durchführen, um Knoten 16 zu einem Wurzelknoten zu machen.

Sobald der Knoten 16 ein Wurzelknoten wird, löschen wir den Knoten 16 und erhalten zwei verschiedene Bäume, nämlich den linken Teilbaum und den rechten Teilbaum, wie unten gezeigt:

Wie wir wissen, sind die Werte des linken Teilbaums immer kleiner als die Werte des rechten Teilbaums. Die Wurzel des linken Teilbaums ist 12 und die Wurzel des rechten Teilbaums ist 17. Der erste Schritt besteht darin, das maximale Element im linken Teilbaum zu finden. Im linken Teilbaum beträgt das maximale Element 15, und dann müssen wir eine Spreizungsoperation für 15 durchführen.

Wie wir im obigen Baum sehen können, hat das Element 15 sowohl ein Elternteil als auch ein Großelternteil. Ein Knoten befindet sich rechts von seinem übergeordneten Knoten, und der übergeordnete Knoten befindet sich ebenfalls rechts von seinem übergeordneten Knoten. Daher müssen wir zwei Drehungen nach links durchführen, um Knoten 15 wie unten gezeigt zu einem Wurzelknoten zu machen:

Nach zwei Drehungen am Baum wird Knoten 15 zum Wurzelknoten. Wie wir sehen können, ist das rechte Kind der 15 NULL, also fügen wir Knoten 17 am rechten Teil der 15 hinzu, wie unten gezeigt, und diese Operation wird als a bezeichnet verbinden Betrieb.

Hinweis: Wenn das zu löschende Element nicht im Splay-Baum vorhanden ist, wird das Splaying durchgeführt. Das Spreizen würde für das Element durchgeführt, auf das zuletzt zugegriffen wurde, bevor NULL erreicht wurde.

Algorithmus des Löschvorgangs

 If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root 

Im obigen Algorithmus prüfen wir zunächst, ob die Wurzel Null ist oder nicht; Wenn die Wurzel NULL ist, bedeutet dies, dass der Baum leer ist. Wenn der Baum nicht leer ist, führen wir die Spreizungsoperation für das zu löschende Element durch. Sobald der Spreizvorgang abgeschlossen ist, vergleichen wir die Stammdaten mit dem zu löschenden Element; Wenn beide nicht gleich sind, bedeutet dies, dass das Element nicht im Baum vorhanden ist. Bei Gleichheit können folgende Fälle auftreten:

Fall 1 : Die linke Seite der Wurzel ist NULL, die rechte Seite der Wurzel wird zum Wurzelknoten.

Fall 2 : Wenn sowohl links als auch rechts vorhanden sind, spreizen wir das maximale Element im linken Teilbaum. Wenn das Spreizen abgeschlossen ist, wird das maximale Element zur Wurzel des linken Teilbaums. Der rechte Teilbaum würde zum rechten Kind der Wurzel des linken Teilbaums werden.