Rotationen implementieren

Ein unausgeglichener Baum wird durch die Durchführung einer entsprechenden Rotationsoperation ausgeglichen. Im Abschnitt „Bäume neu ausbalancieren“ wurde erläutert, wie Rotationen an einem Knoten durchgeführt werden. Der folgende Code gibt den Algorithmus für die LL-Rotation an, wie in der Abbildung unten dargestellt.

1 balanceLL(TreeNode A, TreeNode parentOfA) {
2 Sei B das linke Kind von A.
3
4 wenn (A ist die Wurzel)
5 Sei B die neue Wurzel
6 sonst {
7 if (A ist ein linkes Kind von parentOfA)
8 Sei B ein linkes Kind von parentOfA;
9 andere
10 Sei B ein rechtes Kind von parentOfA;
11 }
12
13 Machen Sie T2 zum linken Teilbaum von A, indem Sie B.right zu A.left;
zuweisen 14 Machen Sie A zum rechten Kind von B, indem Sie A B.right;
zuweisen 15 Aktualisieren Sie die Höhe von Knoten A und Knoten B;
16 } // Ende der Methode

Beachten Sie, dass die Höhe der Knoten A und B geändert werden kann, die Höhen anderer Knoten im Baum jedoch nicht geändert werden. Sie können die RR-, LR- und RL-Rotationen auf ähnliche Weise implementieren.

Das obige ist der detaillierte Inhalt vonRotationen implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!