Binary Search Tree Avl Tree [PDF]

Citation preview

Binary Search Tree (BST) Binary Tree Sebagai Struktur File



Binary Search Tree 











Struktur Binary Tree banyak digunakan untuk membantu memecahkan persoalan suatu algoritma, contohnya untuk memecahkan masalah organisasi file direct. Penggunaan Binary Tree sebagai suatu struktur file yang disebut Binary Search Tree (BST). Aturan Insert ke dalam File BST : < Node  Masuk Ke Kiri > Node  Masuk Ke Kanan



Contoh Insert ke File Binary Search Tree Key : 30, 62, 69, 41, 25, 39, 14, 93 30



25 14



62 41



39



69



93



Ketidakefisienan Binary Search Tree Key : 14, 25, 30, 39, 41, 62, 69, 93 14



25



30



39



41



62



69



93



AVL TREE (Adelson, Velskii, Landis) BST Yang “Seimbang”



Balance Factor B A C







 



---> level 1 D ---> level 2 F ---> level 3 E ---> level 4



Subtree : Tree yang terbentuk disebelah kanan atau kiri dari suatu node. (Catatan : Node tsb disebut root subtree) Tinggi subtree : Level node terbawah dari subtree dikurang level root subtree tsb Balance Factor : Tinggi subtree kanan dikurang tinggi dari subtree kiri dari suatu node



AVL Tree  











Binary Search Tree yang memiliki aturan setiap node selalu memiliki balance factor 0, +1 atau -1 Maka : setiap kali key baru diinsert ke dalam file, setiap node dilihat balance factornya Apabila ada node yang balance factornya tidak 0, +1 atau -1 (tidak imbang) maka struktur file dilakukan transformasi : pemutaran dan atau penggeseran Kemungkinan tidak imbang hanya 2 dan diselesaikan dengan solusi : Rotasi Tunggal dan Rotasi Ganda



Kemungkinan Transformasi 1 (Rotasi Tunggal) +1 +2



Y



X Y



A B



X



Rotasi kiri



+1 0



0



0



C



C B



A



h h



h h+1



h



Node Baru



h



h+1



Kemungkinan Transformasi 1 (Rotasi Tunggal) X



0



-2 Rotasi kanan



Y A



-1



C



Y X 0



C B



B



A



h h+1 h+1



Node Baru



h



h



h



Kemungkinan Transformasi 2 (Rotasi Ganda) 0



X



+1 +2



-1 0



A



+1 0



Y



-1



Z



+2



B



A



h-1



+2



Z



C h-1 h



B



h Node Baru



0



A



h



X



0



Y



X



D h



Z



C



h



h



h-1



C



h



D h



h-1



Y



B



3 Geser kiri (X)



1 2



Geser kanan (Y)



D



Kemungkinan Transformasi 2 (Rotasi Ganda) Z



-2



X



Y



Y +1 -1



A B



X



D



Z



Z C



Y



h h h



h-1



-2



A



D



B



+1



C



D



h-1



h



h



C



B



h h



Node Baru



X



0



-2



0



A



0



h-1 h



3 Geser kanan (X)



1 2



Geser kiri (Y)



Transformasi Mana ? 







Bila 2 node teratas tandanya sama maka gunakan Transformasi 1 (rotasi tunggal) Bila 2 node teratas tandanya beda maka gunakan Transformasi 2 (rotasi ganda)



CONTOH SOAL AVL-TREE Masukkan key berikut ke dalam AVL Tree : 51, 88, 92, 72, 41, 55, 35, 10