Tinggi simpul:
- ketinggian sub-tree kosong adalah 0.
- tinggi leaf adalah 1.
- ketinggian simpul internal adalah ketinggian maksimum anak-anaknya ditambah 1.
faktor seimbang:
-perbedaan ketinggian subtree kanan dan kiri.
faktor seimbang dari semua node di AVL Tree seharusya lebih dari 1.
Node yang mengandung 17 (orange) lebih dari 1, jadi BST ini bukan AVL Tree.
AVL Tree Operations: Insertion
- Pertama, masukkan key baru sebagai leaf baru seperti dalam BST
- lalu, restore kondisi seimbangya
- Pertama, masukkan kunci baru sebagai daun baru seperti dalam strategi memasukkan Binary Search Tree biasa.
*Tetapi ini dapat menyebabkan pelanggaran pada properti AVL Tree.
- Selanjutnya, kembalikan kondisi keseimbangan.
- Rotasi LL: simpul baru dimasukkan dalam sub-pohon kiri dari sub-pohon kiri dari node kritis
- Rotasi RR: simpul baru dimasukkan di sub-pohon kanan dari sub-pohon kanan dari node kritis.
- Rotasi LR: node baru dimasukkan di sub-pohon kanan dari sub-tree kiri dari node kritis
- Rotasi RL: simpul baru dimasukkan di sub-pohon kiri dari sub-pohon kanan dari node kritis
Untuk memastikan bahwa pohon yang diberikan tetap AVL setelah setiap penyisipan, kita harus menambah operasi penyisipan BST standar untuk melakukan penyeimbangan ulang. Berikut ini adalah dua operasi dasar yang dapat dilakukan untuk menyeimbangkan kembali BST tanpa melanggar properti BST (kunci (kiri) <kunci (root) <kunci (kanan)).
1) Rotasi Kiri
2) Rotasi Kanan
Langkah-langkah yang harus diikuti untuk pemasangan
Biarkan simpul yang baru dimasukkan menjadi w
1) Lakukan insert BST standar untuk w.
2) Mulai dari w, naik dan temukan simpul tidak seimbang pertama. Biarkan z menjadi simpul tidak seimbang pertama, y menjadi anak dari z yang datang di jalan dari w ke z dan x menjadi cucu dari z yang datang di jalur dari w ke z.
3) Seimbangkan kembali pohon dengan melakukan rotasi yang sesuai pada subtree yang di-root dengan z. Ada 4 kemungkinan kasus yang perlu ditangani karena x, y dan z dapat diatur dalam 4 cara. Berikut ini adalah 4 pengaturan yang mungkin:
a) y adalah anak kiri dari z dan x adalah anak kiri dari y (Kasing Kiri Kiri)
b) y adalah anak kiri z dan x adalah anak kanan y (Left Right Case)
c) y adalah anak kanan z dan x adalah anak kanan y (Right Right Case)
d) y adalah anak kanan z dan x adalah anak kiri y (Kasus Kiri Kanan)
Berikut ini adalah operasi yang harus dilakukan dalam 4 kasus yang disebutkan di atas. Dalam semua kasus, kita hanya perlu menyeimbangkan kembali subtree yang berakar dengan z dan pohon lengkap menjadi seimbang karena ketinggian subtree (Setelah rotasi yang sesuai) yang di-root dengan z menjadi sama seperti sebelum penyisipan. (Lihat ceramah video ini untuk bukti)
AVL Tree Operations: Deletion
- Hapus simpul seperti pada Binary Search Tree biasa.
*Node yang dihapus akan berupa daun atau simpul dengan satu anak.
- Lacak jalur dari (induk) daun yang dihapus ke arah root. Untuk setiap simpul P yang ditemui, periksa apakah ketinggian kiri (P) dan kanan (P) berbeda paling banyak 1.
*Jika Ya, lanjutkan ke induk (P).
*Jika Tidak, perbaiki sub pohon P baik dengan rotasi tunggal atau rotasi ganda (seperti dalam insersion).
- Setelah kita melakukan rotasi pada P, kita mungkin harus melakukan rotasi pada beberapa leluhur P. Jadi, kita harus terus melacak jalan sampai kita mencapai root.
Langkah-langkah yang harus diikuti untuk dihapus.
Untuk memastikan bahwa pohon yang diberikan tetap AVL setelah setiap penghapusan, kita harus menambah operasi penghapusan standar BST untuk melakukan penyeimbangan ulang. Berikut ini adalah dua operasi dasar yang dapat dilakukan untuk menyeimbangkan kembali BST tanpa melanggar properti BST (kunci (kiri) <kunci (root) <kunci (kanan)).
1) Rotasi Kiri
2) Rotasi Kanan
Biarkan simpul yang akan dihapus
1) Lakukan penghapusan BST standar untuk w.
2) Mulai dari w, naik dan temukan simpul tidak seimbang pertama. Misalkan z menjadi simpul tidak seimbang pertama, y menjadi tinggi anak z yang lebih besar, dan x menjadi tinggi anak y yang lebih besar. Perhatikan bahwa definisi x dan y berbeda dari penyisipan di sini.
3) Seimbangkan kembali pohon dengan melakukan rotasi yang sesuai pada subtree yang di-root dengan z. Ada 4 kemungkinan kasus yang perlu ditangani karena x, y dan z dapat diatur dalam 4 cara. Berikut ini adalah 4 pengaturan yang mungkin:
a) y adalah anak kiri dari z dan x adalah anak kiri dari y (Kasing Kiri Kiri)
b) y adalah anak kiri z dan x adalah anak kanan y (Left Right Case)
c) y adalah anak kanan z dan x adalah anak kanan y (Right Right Case)
d) y adalah anak kanan z dan x adalah anak kiri y (Kasus Kiri Kanan)
Seperti penyisipan, berikut ini adalah operasi yang harus dilakukan dalam 4 kasus yang disebutkan di atas. Perhatikan bahwa, tidak seperti penyisipan, memperbaiki simpul z tidak akan memperbaiki pohon AVL lengkap. Setelah memperbaiki z, kita mungkin harus memperbaiki leluhur z juga (Lihat ceramah video ini untuk bukti)
No comments:
Post a Comment