Data Structure 7

Video Confrence 1

AVL Tree (Adelson-Velskii and Landis Tree)

Hari ini gw belajar dari video confrence Binus tentang AVL Tree. Simpelnya, AVL tree itu cuman lanjutan dari Binary Search Tree (BST) ato bisa juga kita bilang sebagai "uprade"an dari BST.

Kenapa sih kita harus belajar AVL Tree? Kan kita udah bisa bikin coding BST..

Jawabannya karena di kasus-kasus tertentu, BST bisa aja ga seimbang. Misalnya kalau kita insert angka dari 1 sampe 10, BST-nya bakalan berat di kanan. Akibatnya yang menjadi salah satu dari tujuan kita bikin BST (yaitu buat mempercepat pencarian menjadi 2 log n) itu ga tercapai. Kalo misalnya BST kita jadinya cuman garis lurus doang, berarti kalo kita mau cari satu data, tetep aja harus travel sebanyak n data. Nah, si AVL ini membuat pencarian tree kita jadinya lebih efektif. Meskipun memang kecepatan carinya belum persis selalu = 2 log n, tapi jauh lebih mendekati 2 log n dibanding sebanyak n.

Nah, jadi dalam AVL, cara kita masukin data sama persis kayak di BST. Yaitu, kalo data baru yang kita masukin lebih kecil, maka bakal ke kiri, kalo lebih besar, maka bakal ke kanan. Yang ngebedain adalah dalam AVL, perbedaan tinggi dalam tree kita itu HARUS lebih kecil dari 2 (jadi perbedaan yang masih boleh itu cuman 0 atau 1).

Gimana sih caranya kita bikin tree ini bedanya ga sampe 2? Caranya ada 2, yaitu single rotate dan double rotate. Pertama kita bakal bahas single rotate dulu karna lebih simpel.



Nah kita pake gambar aja biar lebih jelas. Hal pertama yang harus kita cari tau itu, di mana sih ga seimbangnya tree ini. Kalo kita liat gambar di atas, yang ga seimbang itu di '3' karena masuknya data '5'. Trus tahap kedua adalah, cari tau ini pake single rotate atau double rotate. Cara nentuinnya gimana sih? Kalo garisnya lurus (dari angka 3, 4, dan 5 itu kan lurus ke kanan), maka kita cuman perlu single rotate.

Bayangin aja pas kita ngerotate itu kayak katrol, kalo kita tarik tali katrolnya, otomatis angka 3 bakal turun dan angka 4 bakal naik kan kayak gambar di atas. Nah single rotate itu cuman kyk gitu aja. Tapi setelah kita ngerotate kita selalu harus cek penempatan datanya udah bener belom. Di gambar di atas, 3 jadi anak kirinya 4 dan 5 jadi anak kanannya 4 which is udah sesuai dengan aturan BST.

Sekarang kita bahas double rotation..


 

Nah, kita juga pake gambar biar lebih jelas. Double rotate itu dipake kalo kita nemuin tree yang ga stabil itu bengkok. Jadi pertama kan kita harus cari tau tree mana yang ga stabil. Dalam gambar ini, itu tree 6 (karena anak kirinya 1 dan anak kanannya 3, maka perbedaan levelnya 2 which is ga boleh). Tapi kalo kita lihat 6, 15, dan 7 itu juga ga membentuk 1 garis lurus (alias bengkok). Makanya kita harus pake double rotate. Pertama kita tarik dulu 15 dan 7 biar 7-nya di atas dan 15 di bawah. Nah sekarang kan (6, 7, dan 15) udah jadi dalam 1 garis nih. Kita tinggal pake single rotate deh. Tarik 7 agar naik ke atas, dengan begitu 6-nya otomatis turun ke bawah. Trus terakhir kita juga cek lagi apakah tree yang barusan kita rotate itu udah sesuai dengan aturan BST. Dalam gambar di atas, treenya udah sesuai dengan aturan BST. Maka double rotation kita udah selsai.