Mengatasi Kaedah sisipan

Memasukkan elemen ke dalam pokok AVL adalah sama seperti memasukkannya ke BST, kecuali pokok itu mungkin perlu diseimbangkan semula. Elemen baharu sentiasa disisipkan sebagai nod daun. Hasil daripada menambah nod baharu, ketinggian nenek moyang nod daun baharu mungkin meningkat. Selepas memasukkan nod baharu, semak nod di sepanjang laluan dari nod daun baharu sehingga ke akar. Jika nod tidak seimbang ditemui, lakukan putaran yang sesuai menggunakan algoritma dalam kod di bawah.

1 balancePath(E e) {
2 Dapatkan laluan dari nod yang mengandungi elemen e ke akar,
3 seperti yang digambarkan dalam Rajah 26.9;
4 untuk setiap nod A dalam laluan menuju ke punca {
5 Kemas kini ketinggian A;
6 Biarkan parentOfA menandakan induk A,
7 yang merupakan nod seterusnya dalam laluan, atau null jika A ialah punca;
8
9 suis (balanceFactor(A)) {
10 kes -2: jika balanceFactor(A.left) == -1 atau 0
11 Lakukan putaran LL; // Lihat Rajah 26.2
12 lagi
13 Lakukan putaran LR; // Lihat Rajah 26.4
14 rehat;
15 kes +2: jika balanceFactor(A.right) == +1 atau 0
16 Lakukan putaran RR; // Lihat Rajah 26.3
17 lagi
18 Lakukan putaran RL; // Lihat Rajah 26.5
19 } // Tamat suis
20 } // Tamat untuk
21 } // Tamat kaedah

Algoritma mempertimbangkan setiap nod dalam laluan dari nod daun baharu ke akar. Kemas kini ketinggian nod pada laluan. Jika nod seimbang, tiada tindakan diperlukan. Jika nod tidak seimbang, lakukan putaran yang sesuai

Atas ialah kandungan terperinci Mengatasi Kaedah sisipan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!