Überschreiben der Einfügemethode

Das Einfügen eines Elements in einen AVL-Baum ist dasselbe wie das Einfügen in einen BST, außer dass der Baum möglicherweise neu ausbalanciert werden muss. Ein neues Element wird immer als Blattknoten eingefügt. Durch das Hinzufügen eines neuen Knotens kann die Höhe der Vorgänger des neuen Blattknotens zunehmen. Überprüfen Sie nach dem Einfügen eines neuen Knotens die Knoten entlang des Pfads vom neuen Blattknoten bis zur Wurzel. Wenn ein unausgeglichener Knoten gefunden wird, führen Sie eine entsprechende Drehung mit dem Algorithmus im folgenden Code durch.

1 balancePath(E e) {
2 Holen Sie sich den Pfad vom Knoten, der das Element e enthält, zur Wurzel,
3 wie in Abbildung 26.9 dargestellt;
4 für jeden Knoten A im Pfad, der zur Wurzel {
führt 5 Aktualisieren Sie die Höhe von A;
6 Es sei parentOfA das übergeordnete Element von A,
7, der der nächste Knoten im Pfad ist, oder null, wenn A die Wurzel ist;
8
9 Schalter (balanceFactor(A)) {
10 Fall -2: wenn balanceFactor(A.left) == -1 oder 0
11 LL-Rotation durchführen; // Siehe Abbildung 26.2
12 andere
13 LR-Rotation durchführen; // Siehe Abbildung 26.4
14 Pause;
15 Fall +2: wenn balanceFactor(A.right) == +1 oder 0
16 RR-Rotation durchführen; // Siehe Abbildung 26.3
17 andere
18 RL-Rotation durchführen; // Siehe Abbildung 26.5
19 } // Ende des Wechsels
20 } // Ende für
21 } // Ende der Methode

Der Algorithmus berücksichtigt jeden Knoten im Pfad vom neuen Blattknoten zur Wurzel. Aktualisieren Sie die Höhe des Knotens auf dem Pfad. Wenn ein Knoten ausgeglichen ist, ist keine Aktion erforderlich. Wenn ein Knoten nicht ausgeglichen ist, führen Sie eine entsprechende Rotation durch

Das obige ist der detaillierte Inhalt vonÜberschreiben der Einfügemethode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!