Implementasi AVL Tree sebagai BST Plus Rebalancing
Proses awal penyisipan atau penghapusan dilakukan sesuai aturan BST,
tapi dilanjutkan dengan proses rebalance berdasarkan kasus-kasus yang terjadi.
Dengan adanya toleransi perbedaan tinggi max 1 tersebut maka rebalancing
dapat dilokalisir hingga tingkat subtree tertentu.
Untuk mengetahui subtree mana rebalance akan dilakukan suatu
penelusuran berdasarkan harga BF tersebut mulai dari yang paling lokal
yaitu subtree dari ayah node yang baru masuk/dihapus ke setiap ancestor tepat
di atasnya (lebih global) hingga diketahui saat BF ancestor tidak
mengalami perubahan BF. Perhatikan contoh berikut ini yang menunjukkan
perubahan BF sejumlah node akibat adanya penyisipan.
Setelah penyisipan key 53.
Dengan haya melakukan rebalancing pada subtree dengan BF +2 atu -2 terendah
maka segera tree kembali menjadi AVL.
Berikut akan dijelaskan selengkapnya operasi-operasi rebalancing pada semua
kemungkinan struktur subtree saat terjadi penyisipan.
Rebalancing dengan Rotasi
Pada dasarnya rebalancing dilakukan dengan merotasikan node-node tertentu
dalam subtree tsb berdasarkan harga-harga BF node-node level atas dalam
subtree. Ada empat jenis rotasi:
- Single Right Rotation (SRR)
Kondisi: Bila N adalah subtree di mana terjadi penyisipan (atau N adalah node baru
disisipan itu sendiri), dan R adalah ancestor paling bawah yang mendapatkan
BF-nya menjadi -2, sementara P anak kiri dari R yang mana N adalah anak kiri
dari P (dpl. BF(P) = -1, mengapa?). Rotasi dilakukan sehingga P menjadi ayah dari N dan R yang masing-masing
adalah anak kiri dan kanan dari P sementara jika ada subtree kanan dari P dengan
x sebagai root maka akan menjadi subtree kiri dari R.
BF(R) dan BF(P) keduanya menjadi 0.
- Single Left Rotation (SLR)
Kondisi: merupakan simetri dari kondisi untuk SRR;
bila N adalah subtree di mana terjadi penyisipan (atau N adalah node baru
disisipan itu sendiri), dan R adalah ancestor paling bawah yang mendapatkan
BF-nya menjadi +2, sementara P anak kanan dari R yang mana N adalah anak kanan
dari P (dpl. BF(P) = +1). Rotasi dilakukan sehingga P menjadi ayah dari R
dan N yang masing-masing adalah anak kiri dan kanan dari P sementara jika ada
subtree kiri dari P dengan x sebagai root maka akan menjadi subtree kanan dari
R.
BF(R) dan BF(P) keduanya menjadi 0.
- Double Right Rotation (DRR)
Kondisi: bila N adalah subtree di mana terjadi penyisipan (atau N adalah node baru
disisipan itu sendiri), dan R adalah ancestor paling bawah yang mendapatkan
BF-nya menjadi -2, sementara P anak kiri dari R yang mana N adalah anak kanan
dari P (dpl. BF(P) = +1). Rotasi dilakukan dua kali, pertama dalam subtree P yang
menghasilkan P sebagai anak kiri dari N, kemudian dalam subtree R yang menghasilkan
R sebagai anak kanan dari N. Jika N memiliki subtree kiri maka subtree ini menjadi
subtree kanan dari P dan juga jika N memiliki subtree kanan maka subtreee ini mejadi
subtree kiri dari R.
BF(N) menjadi 0, BF(P) dan BF(R) tergantung pada BF(N) semula:
jika BF(N) = 0 maka BF(P) dan BF(R) keduanya menjadi 0;
jika BF(N) = +1 maka BF(P) menjadi 0 dan BF(R) menjadi +1;
jika BF(N) = -1 maka BF(P) menjadi -1 dan BF(R) menjadi 0;
- Double Left Rotation(DLR)
Kondisi: merupakan simetri dari DRR; bila N adalah subtree di mana terjadi
penyisipan (atau N adalah node baru
disisipan itu sendiri), dan R adalah ancestor paling bawah yang mendapatkan
BF-nya menjadi +2, sementara P anak kanan dari R yang mana N adalah anak kiri
dari P (dpl. BF(P) = -1). Rotasi dilakukan dua kali, pertama dalam subtree P yang
menghasilkan P sebagai anak kanan dari N, kemudian dalam subtree R yang menghasilkan
R sebagai anak kiri dari N. Jika N memiliki subtree kiri maka subtree ini menjadi
subtree kanan dari R dan juga jika N memiliki subtree kanan maka subtreee ini mejadi
subtree kiri dari P.
BF(N) menjadi 0, BF(P) dan BF(R) tergantung pada BF(N) semula:
jika BF(N) = 0 maka BF(P) dan BF(R) keduanya menjadi 0;
jika BF(N) = -1 maka BF(P) menjadi 0 dan BF(R) menjadi +1;
jika BF(N) = +1 maka BF(P) menjadi -1 dan BF(R) menjadi 0;
Algoritma Rebalance Pada Penyisipan
Penyisipan key dengan BST menghasilkan node baru sebagai leaf yang kita
sebut N yang menjadi anak dari P.
Jika N adalah turunan kiri dari P, maka BF(P) -= 1, jika turunan kanan
maka BF(P) += 1. Kemudian periksa :
-
Jika BF(P) semula adalah -1 (atau +1) dan sekarang menjadi 0 maka proses
selesai.
-
Jika BF(P) semula adalah 0 dan sekarang menjadi +1 (atau -1) maka
-
BF(ayah dari P) -= 1 jika P anak kiri dari R, atau
- BF(ayah dari P) += 1 jika P anak kanan dari R;
- Bila BF(R) menjadi = 0 maka selesai.
- (Berarti BF(R) menjadi -1 atau +1) Periksa secara rekursif
ayah dari R (jika ada) sebagai R sekarang, R semula menjadi P, P
semula menjadi N s.d. R=root atau selesai akibat kasus-kasus point sebelumnya.
- (Berarti BF(R) semula adalah +1 menjadi +2 atau semula -1 menjadi -2) Periksa BF(R) dan BF(P):
-
Kasus BF(P) = -1 atau 0 dan BF(R) = -2: lakukan SRR dan selesai.
-
Kasus BF(P) = +1 dan BF(R) = -2: lakukan DRR dan selesai.
-
Kasus BF(P) = +1 atau 0 dan BF(R) = +2: lakukan SLR dan selesai.
-
Kasus BF(P) = -1 dan BF(R) = +2: lakukan DLR dan selesai.
Contoh
Perhatikan contoh terakhir berikut ini yang mengalami
penyisipan key 26. Setelah penyisipan 26 secara BST maka tree menjadi sbb.
Setelah DLR pada subtree 23 menghasilkan sbb.
Setelah penyisipan 53 secara BST menghasilkan tree sbb.
Setelah dilakukan SLR pada subtree 51 menghasilkan tree sbb.
Latihan
Penyusunan AVL tree dari keadaan kosong dengan bilangan-bilangan:
745, 555, 878, 785, 750, 751, 756, 769,
449, 711, 712, 713.
Hint: penyisipan empat data pertama akan berlangsung sebagaimana dilakukan
BST tanpa terjadi proses rebalance karena masing-masing sudah membentuk
AVL tree dan terakhir akan menghasilkan AVL tree sbb.
Berapa kali rotasi perlu dilakukan pada penyisipan?
Jika suatu subtree mengalami rotasi berarti struktur di dalamnya
belum jenuh (mencapai perfect binary tree) ie. masih mampu menerima
node baru tanpa terjadi penambahan tinggi. Jadi setiap penyisipan
hanya akan berakibat satu kali rotasi atau tidak sama sekali.
Algoritma Rebalance Pada Penghapusan
Dalam proses penghapusan, jika ayah/ancestor dari node yang dihapus
mengalami perubahan BF dari 0 menjadi -1 (atau +1),
maka subtree P tidak mengalami perubahan
tinggi dan berarti selesai.
Jika perubahan BF terjadi dari +1 (atau -1) menjadi 0 maka berarti
terjadi pemendekan subtree yang dapat mengakibatkan perubahan
di ancestor yang lebih tinggi.
Selain itu adalah BF berubah menjadi +2 atau -2 yang mengakibatkan
rotasi sesuai kondisi yang terjadi.
Perlu ditekankan disini bahwa pada penghapusan, BF dari node P dalam
diagram dapat berharga 0 (dalam penyisipan tidak akan terjadi,
mengapa?). Untuk kondisi maka kombinasi BF(R)=+2 dan BF(P)=0
menghasilkan SLR dan BF(R) = -2 dan BF(P) = 0 menghasilkan SRR.
-
Tahap pertama penghapusan suatu node pada AVL tree adalah melakukan
penghapusan sebagai yang dilakukan BST dan dilanjutkan dengan
rebalancing.
-
Misalnya node yang dihapus adalah D, setiap ancestor R mulai dari
ayah D ke atas dilakukan pemeriksaan apakah terjadi perubahan BF.
-
Jika D adalah anak (atau keturunan) kanan dari R dan BF(R) semula
adalah 0 (yang menjadi -1 maka subtree R tetap balance serta tidak
terjadi pemendekan R sehingga proses selesai.
-
Jika D adalah anak (atau keturunan) kiri dari R dan BF(R) semula
adalah 0 (yang menjadi +1 maka subtree R tetap balance serta tidak
terjadi pemendekan R sehingga proses selesai.
-
Jika BF(R) semula adalah +1 atau -1 dan menjadi 0 maka terjadi pemendekan
subtree R, dan proses pemeriksaan dilanjutkan ke ayah dari R sebagai
R sekarang.
-
BF(R) semula adalah -1 dan menjadi -2 (note: D adalah keturunan/anak kanan dari R)
maka dengan anak kiri R disebut P dan anak kanan R disebut N:
-
jika BF(P) = 0 maka dilakukan SRR dan selesai
karena tidak terjadi pemendekan subtree R.
-
jika BF(P) = -1 maka dilakukan SRR namun
karena terjadi pemendekan subtree R pemeriksaan untuk rebalance
dilanjutkan pada ayah R sebagai R sekarang.
-
(Berarti BF(P) =+1) dilakukan DRR dan
karena terjadi pemendekan R proses rebalance dilakukan pada ayah R sebagai
R sekarang.
-
BF(R) semula adalah +1 dan menjadi +2 (note: D adalah keturunan/anak kiri
dari R) maka dengan anak kanan R disebut P dan anak kiri R disebut N:
-
jika BF(P) = 0 maka dilakukan SLR dan selesai
karena tidak terjadi pemendekan subtree R.
-
jika BF(P)= +1 maka dilakukan SLR namun
karena terjadi pemendekan subtree R pemeriksaan untuk rebalance
dilanjutkan pada ayah R sebagai R sekarang.
-
(Berarti BF(P) = -1) dilakukan DRR dan
karena terjadi pemendekan R proses rebalance dilakukan pada ayah R sebagai
R sekarang.
Berapa kali rotasi perlu dilakukan pada penghapusan?
Jika suatu subtree mengalami rotasi berarti subtree tersebut mengalami
pemendekan dan ini dapat berakibat perubahan di level lebih tinggi dari
subtree tinggi. Jadi pada setiap penghapusan
bisa mengakibatkan beberapa kali rotasi.
Contoh
Dari tree berikut ini hendak dilakukan penghapusan 81
Penghapusan secara BST menyebabkan 79 menggantikan 81 dan penghapusan node ex-79.
Karena subtree 79 tidak balance maka terjadilah SLR
Rotasi tsb. mengakibatkan perubahan BF node 77 yang
selanjutnya terjadi lagi rotasi SRR.
Rotasi kedua ini mengaibatkan perubahan BF node 45. Namun karena perubahannya
adalah menjadi 0 maka proses selesai.
Latihan
Dari tree latihan untuk penyisipan, lakukan berturut-turut penghapusan
key-key berharga 750, 745, 878, 785, dan 555.
Untuk lebih memahami operasi-operasi AVL Tree ini lihatlah page demo AVL Tree.
Pertanyaan
-
Berapakah tinggi maksimum dan tinggi minimum suatu AVL tree yang memiliki
jumlah node n = 1, 2, 4, 8, 12, N ?
-
Berapakah jumlah path rata-rata dari root ke setiap node dalam kondisi
terburuk pada suatu AVL tree dengan jumlah node n = 1, 2, 4, 8, 12, N?
-
Berapakah jumlah node minimum dan jumlah node maksimum pada suatu AVL tree
dengan tinggi h = 1, 2, 4, H?
-
Berapa banyak operasi untuk melakukan rotasi:
Implementasi Algoritma
Walaupun mekanisme-mekanisme rotasi AVL Tree nampaknya rumit tetapi dalam
implementasinya amat sederhana. Untuk operasi SRR hanya diperlukan metoda
TreeNode SRR(TreeNode R) {
TreeNode P = R.left;
R.left = P.right;
P.right = R;
return P;
}
Sementara pada DRR diperlukan metoda
TreeNode DRR(TreeNode R) {
TreeNode P = R.left;
TreeNode N = P.right;
R.left = N.right;
P.right = N.left;
N.right = R;
N.left = P;
return N;
}
Demikian halnya SLR dan DLR.
Analisis Algoritma
Dari algoritma implementasi di atas dapat disimpulkan bahwa kompleksitas
algoritma operasi penyisipan/penghapusan bergantung pada algoritma
penyisipan dan penghapusan pada BST yang berisikan komponen utamanya
adalah algoritma pencarian (i.e. pencarian posisi penyisipan atau node
yang akan dihapus) yang diketahui O(lg n). Operasi
rotasi sendiri hanya beberapa baris perintah yang berarti O(1).
Dari segi struktur tree itu sendiri maka berdasarkan analisis Fibonacci
Tree (lihat penjalasan dalam buku teks edisi sebelumnya: Standish, T.A.
Data Structures, Algorithms, and Software Principles in C,
Addison-Wesley, 1995, pp.384-387) diperoleh tinggi untuk AVL Tree
dengan N key adalah tidak akan lebih dari 1.44 lg(N+2) - 1.328.
Sementara minimal adalah membentuk AVL Tree semampat-mampatnya mendekati
bentuk perfect binary tree dengan tinggi lg(N).