Verketten / Zusammenführen / Verbinden zwei AVL-Bäume

Question

Nehmen wir an, ich zwei AVL-Bäume haben und dass jedes Element aus dem ersten Baum kleiner ist dann jedes Element aus der zweiten Baum. Was ist der effizienteste Weg, um sie zu einem einzigen AVL-Baum zu verketten? Ich habe überall gesucht, aber nichts gefunden nützlich.

Answer 1

Angenommen, Sie den Eingang Bäume zerstören können:

1. entfernen, das äußerste rechte Element für den linken Baum, und es verwenden, einen neuen Wurzelknoten zu konstruieren, dessen linkes Kind ist linken Baum und dessen rechtes Kind die richtige Baum: O (log n)
2. bestimmen und festgelegt, dass Knotens Ausgleichsfaktor: O (log n). In (temporärer) Verletzung der Invarianten, die Balance außerhalb des Bereichs liegen kann {-1, 0, 1}
3. drehen, um den Ausgleichsfaktor wieder in Reichweite zu bekommen: O (log n) Umdrehungen: O (log n)

Somit kann die gesamte Operation in O (log n) durchgeführt werden.

Edit: Am zweiten Gedanken, ist es einfacher, Grund, über die Drehungen in dem folgenden Algorithmus. Es ist auch sehr wahrscheinlich schneller:

1. Bestimmen Sie die Höhe der beiden Bäume. O (log n)
   Unter der Annahme, dass der richtige Baum ist höher (der andere Fall ist symmetrisch):
2. entfernen, das äußerste rechte Element aus dem left Baum (Drehen und seine berechnete Höhenverstellung, falls erforderlich). Lassen Sie n dass Element sein. O (log n)
3. Im rechten Baum, navigate links, bis erreichen Sie einen Knoten, dessen Unterbaum ist höchstens ein 1 größer als left. Lassen Sie r, dass der Knoten sein. O (log n)

4. ersetzen, dass der Knoten mit einem neuen Knoten mit dem Wert n, und Teilbäumen left und r. O (1)
   Durch die Konstruktion wird der neue Knoten AVL-ausgewogen, und der Baum 1 größer als r.

5. erhöht seine Eltern Balance entsprechend. O (1)

6. und Neuverteilung wie Sie sich nach dem Einlegen. O (log n)

Answer 2

Eine extrem einfache Lösung (das Arbeiten ohne Annahmen in den Beziehungen zwischen den Bäumen), ist dies:

1. Führen Sie eine Mergesort beiden Bäume in ein Array zusammengefasst (gleichzeitig Iterierte beiden Bäume).
2. Erstellen Sie eine AVL-Baum aus dem Array -. Das mittlere Element nehmen die Wurzel zu sein und gelten rekursiv auf linke und rechte Hälften

Beide Schritte sind O (n). Das Hauptproblem dabei ist, dass es O (n) zusätzlichen Platz in Anspruch nimmt.

Answer 3

Die beste Lösung, die ich für dieses Problem zu lesen hier . Ist sehr nah an meriton 's Antwort, wenn Sie dieses Problem zu beheben:

Im dritten Schritt des Algorithmus navigiert links, bis Sie den Knoten, dessen Unterbaum hat die gleiche Höhe wie der linke Baum erreichen. Dies ist nicht immer möglich, (Gegenbeispiel siehe Bild). Der richtige Weg, um diesen Schritt zu tun ist, zwei Fund für einen Teilbaum mit einer Höhe h oder h+1 wo h die Höhe des linken Baumes ist

Answer 4

Ich nehme an, dass Sie nur einen Baum zu gehen haben (hoffentlich die kleinere) und jeweils einzeln an die anderen Baumelementen der hinzufügen. Die AVL insert / Löschvorgänge nicht zu einem Zeitpunkt, das Hinzufügen eines ganzen Unterbaumes zu behandeln entworfen.