AVL Tree

AVL Tree
Dalam ilmu komputer, sebuah AVL tree adalah sebuah pohon biner terurut yang dapat menyeimbangkan dirinya sendiri pertama, yang ditemukan serta dinamai setelah dua penemunya, G.M. Adelson-Veleskii dan E.M. Landis. 

Contoh AVL Tree:

Cara Menentukan Height dan Balance Factor:

• Jika node (root) tidak memiliki subtree heightnya sama dengan 0.
• Jika node adalah leaf, maka height sama dengan 1.
• Jika internal node, adalah height maksimum yang dimiliki children ditambah 1.

Rebalance AVL Tree
Jika selama operasi modifikasi, perbedaan tinggi (sementara) lebih dari satu muncul antara child subtrees, parent subtree harus "rebalanced". Alat perbaikan yang diberikan adalah apa yang disebut rotasi pohon karena mereka menggerakkan kunci hanya "secara vertikal" sehingga urutan urutan ("horizontal") kunci sepenuhnya dipertahankan. 
Misalkan X adalah node yang memiliki faktor keseimbangan (sementara) −2 atau +2. Substansi kiri atau kanannya telah dimodifikasi. Biarkan Z menjadi anak yang lebih tinggi. Perhatikan bahwa Z berada dalam bentuk AVL oleh hipotesis induksi. Dalam hal penyisipan, penyisipan ini telah terjadi pada salah satu anak Z sedemikian rupa sehingga ketinggian Z meningkat. Dalam kasus penghapusan, penghapusan ini terjadi pada saudara t1 dari Z dengan cara sehingga ketinggian t1 yang sudah lebih rendah telah menurun.

Biarkan node yang harus diseimbangkan kembali oleh T.
Ada 4 kasus:
Kasus 1: node terdalam terletak di subtree kiri anak kiri T.
Kasus 2: node terdalam terletak di subtree kanan anak kanan T.
Kasus 3: node terdalam terletak di subtree kanan anak kiri T.
Kasus 4: node terdalam terletak di subtree kiri anak kanan T.

Catatan: Dalam insertion, nodeterdalam akan menjadi node yang disisipkan.

Penyisipan (insertion), dan penhapusan (deletion) semuanya memerlukan O(logn) kali dalam kasus biasa dan kasus terburuk. Penambahan (additions) dan penhapusan membutuhkan tree tersebut untuk menyeimbangkan kembali dirinya melalui rotasi tree satu kali atau lebih.
Cara perurutannya yaitu nilai sebelah kiri yang paling rendah, sedangkan nilai sebelah kanan paling besar dari nilai utamanya (root), left<root< right.

Insertion
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. dengan melacak jalur dari kunci baru menuju root. Untuk setiap node P temui, periksa apakah ketinggian kiri (P) dan kanan (P) berbeda pada paling banyak 1.

• Jika Ya, lanjutkan ke parent(P).
• Jika Tidak, perbaiki sub pohon P baik dengan rotasi tunggal atau rotasi ganda.

Insertion terdiri dari:

Rotasi LL: node baru dimasukkan dalam sub-pohon kiri dari sub-pohon kiri dari node kritis

Rotasi RR: node baru dimasukkan ke dalam sub-pohon kanan dari sub-pohon kanan dari node kritis.

Rotasi LR: node baru dimasukkan di sub-pohon kanan sub-pohon kiri dari node kritis.

Rotasi RL: node baru dimasukkan di sub-pohon kiri dari sub-pohon kanan dari node kritis.

Deletion

Node yang dihapus akan berupa daun atau nodedengan satu anak.

Lacak jalur dari (induk) daun yang dihapus ke arah root. Untuk setiap node 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 penyisipan).

Contoh:

Penghapusan node (60), membuat node (55) tidak seimbang.

Sehingga dilakukan single rotation pada node (55).

Tetapi menyebabkan node (50) menjadi tidak seimbanng, sehingga harus di lakukan double ratation.

Hasil akhir dari deletion node (60).