Kann mir jemand diese Art von Rekursion erklären?

Question

Ich möchte Rekursion verstehen. Ich verstehe dummes Beispiel mit Mathe, aber ich bin nicht sicher, das Wesen davon zu kennen.

Ich habe ein Beispiel, dass ich don t verstehen, wie es funktioniert:

TREE-ROOT-INSERT(x, z) 

if x = NIL 
    return z 
if z.key < x.key 
    x.left = TREE-ROOT-INSERT(x.left, z) 
    return RIGHT-ROTATE(x) 
else 
    x.right = TREE-ROOT-INSERT(x.right, z) 
    return LEFT-ROTATE(x) 

Ich weiß, was dieser Code tut: Zuerst einen Knoten in einem BST einfügen und drehen dann jedes Mal, so der neue Knoten die wurde Wurzel.

Aber in meinen Gedanken den Code analysierend nehme ich an, dass es den Knoten einfügt, wohin es gehen muss und dann GERADE 1 MAL es den Baum dreht.

Wie ist es möglich, dass der Baum jedes Mal gedreht wird?

Answer 1

Sie müssen Ihren Platz im rekursiven Aufruf für jede Ebene der Struktur beibehalten. Wenn Sie zum ersten Mal (oder links) drücken, sind Sie nicht vollständig fertig. Sie nehmen den Baum, der das Ergebnis der ROTATE-Funktion ist, und platzieren Sie es in dem Code, in dem der rekursive TREE-ROOT-INSERT Aufruf eine Ebene höher in dem Stapel war. Sie rotieren dann erneut und geben den aktuellen Baum eine Ebene höher im Stapel zurück, bis Sie den ursprünglichen Stamm des Baumes getroffen haben.

Answer 2

Was für das Verständnis von Rekursion wichtig ist, ist die rekursive Funktion als abstrakte Black Box zu denken. Mit anderen Worten, beim Lesen oder Nachdenken über rekursive Funktionen sollten Sie sich auf die aktuelle Iteration konzentrieren, den Aufruf der rekursiven Funktion als atomar behandeln (etwas, in das Sie nicht hineingehen können), vorausgesetzt, er kann tun, was er tun soll, und sehen, wie sein Ergebnis kann verwendet werden, um die aktuelle Iteration zu lösen.

Sie kennen bereits den Auftrag IhrDeterm TREE-ROOT-INSERT(x, z):

Einsatz z in einen binären Suchbaum bei x verwurzelt, verwandelt den Baum, so dass z die neue Wurzel werden wird.

die an diesem Schnipsel sehen lassen:

if z.key < x.key 
     x.left = TREE-ROOT-INSERT(x.left, z) 
     return RIGHT-ROTATE(x) 

Dies sagt z kleiner als x ist, so dass es auf den linken Unterbaum geht (weil es BST ist). TREE-ROOT-INSERT wird erneut aufgerufen, aber wir werden nicht darauf eingehen. Stattdessen nehmen wir einfach an, dass es tun kann, was es tun soll: es wird z in den Baum einfügen, der auf x.left verwurzelt ist, und z zum neuen root machen. Dann werden Sie einen Baum des Balgs Struktur erhalten:

 
    x 
    /\ 
    z ... 
/\ 
... ... 

Auch Sie wissen nicht, wie genau TREE-ROOT-INSERT(x.left, z) Aufruf erhalten Sie die z-verwurzelte Unterbaum. In diesem Moment ist es dir egal, denn der wirklich wichtige Teil ist, was folgt: Wie kann man diesen ganzen Baum in z verankern? Die Antwort ist die RIGHT-ROTATE(x)

Aber in meinem Kopf den Code zu analysieren Ich nehme an, dass er den Knoten einsetzen, wo es zu gehen hat und dann nur 1 Mal ist es der Baum dreht.

Wie ist es möglich, dass der Baum jedes Mal gedreht wird?

Wenn ich Sie richtig verstehe, denken Sie immer noch darüber nach, wie Sie das Problem nicht rekursiv lösen können.Es ist richtig, dass Sie z mit der Standard-BST-Einfügeprozedur in die BST mit der Wurzel x einfügen können. Das bringt z in die richtige Position. Um jedoch z von dieser Position zur Wurzel zu bringen, benötigen Sie mehr als 1 Rotation.

In der rekursiven Version ist eine Rotation erforderlich, um z zum Stamm zu bringen, nachdem Sie einen z-Root-Subbaum erhalten haben. Um jedoch den z-rooted-Subbaum aus dem ursprünglichen x.left-Root-Subbaum zu erhalten, benötigen Sie ebenfalls eine Rotation. Die Rotation wird oft, aber auf verschiedenen Teilbäumen aufgerufen.