AVL Tree

AVL TREE

Apa itu AVL Tree?
hmmm........ AVL Tree sebenarnya mirip dengan Binary Search tree, Hanya saja lebih diperbarui.

Jadi apa yang diperbarui??

AVL Tree dikenal sebagai self balancing tree, oleh karena itu yang diperbarui adalah data-data yang telah dimasukin kedalam rantaian tree. Kenapa diperbarui? bukankah itu repot?Kan kita sudah ada Binary Search Tree yang memiliki time complexity O log n tapi kenapa kita membutuhkan AVL Tree?

Iya Pencarian data dalam Binary Search Tree sangat lah cepat dengan complexity blablabla. Tapi gimana kalau BST ketemu worst casenya? dimana treenya bakal terisi child kanan doang? contohnya:

jadi berikut adalah contoh worst case BST dimana pencarian akan menjadi linear search. Sehingga akan sulit untuk mencari data dengan time complexity yang dikatakan tadi.

Jadi Tugas AVL di sini adalah untuk merapikan dirinya sblm di search, sama seperti kamu sebelum kencan harus bercemin kan?kalau jelek di rapiin kalau udah ganteng yaudah gas kencan!. Oh yah gw lupa para programmer disini biasanya jomblo, maaf-maaf. Canda doang jangan ngambek :).

Oke kita lanjut ke Tugas apa yang akan dilakukan oleh si AVL. Karena AVL Tree adalah self balancing tree jadi kita akan main function insert dan delete seperti di Binary Search Tree.

Jadi yang pertama adalah Insert:

Bagaimana cara memasukan data kedalam tree di AVL?

sebetulnya sih sama aja kaya BST masukin datanya...., udah gitu doang kok :v nginsert pake rekursif :v.

Canda-canda :), sebetulnya AVL tree cara insertnya memang sama persis, hanya saja disini kita akan menghitung panjangnya left dan right childnya setelah insert. setelah menghitung tingginya kita akan ngecek apakah kedua child memiliki tinggi yang sama, apabila berbeda AVL Tree akan mengatur tinggi kedua child menjadi sama.

Sebelum masuk ke kodingan saya akan memberitahu logicnya.

1. insert secara rekursif, kalau bingung liat contoh insert BST.

2. jadi siap insert AVL bakal ngecek kiri kanan data yang telah diinsert, apakah tinggi kiri kanannya sama. kalau sama biarin

3. Nah kalau ga sama dia akan perform rotate.Rotate disini ada 2 yaitu Right Rotate dan Left Rotate, jadi bagaimana cara rotate menyelamatkan Tree tersebut sehingga balance?

Yang pertama dia akan ngecek dulu apakah kiri yang ketinggian atau kanan yang ketinggian kalau kanan ketinggian dia akan melakukan Left rotate, dan kalau kiri ketinggian dia akan melakukan Right Rotate.

Ok sekarang apa itu left rotate? dan apa itu right rotate? kamu liat gambar diatas itu kan berat kanan Jadi prosesnya itu kan insert 10 -11-12-13-14. Nah sekarang kalau AVL Tree pada saat insert ke 12 dia akan melihat ada yang ga balance yaitu berat kanan sehingga pertama dia akan menjadi kaya gini.

Nah sekarang kita bayangin kalau panah merah itu treenya masih tegang :"), Jadi kita lemasin dulu menjadi yang biru.

Nah di gambar ini yang lemas akan kelihatan seperti rotate kiri kan? makanya kita sebut itu sebagai rotate kiri atau putar ke kiri.

Ayo kita ingat ingat gaya gravitasi! kalau lemas dia bakal??, YAK!! DIA BAKAL TURUN KEBAWAH!! sehingga jadi begini.

dan seterusnya.

Sama seperti left rotate , right rotate akan melakukan hal yang sama apabila kirinya lebih tinggi.

Berikut adalah contoh Codingannya (Jangan di copas ya :) tau kok yang baca suka copas):

Nah berikut adalah codingannya, sengaja tidak saya buat function maxnya dan balancenya agar kalian tidak copas tanpa berpikir :").

Yang kedua adalah Delete AVL Tree:

Sebetulnya cara delete yang benar di AVL Tree sama saja kaya Delete di BST, hanya saja setelah delete tinggal kita check kiri kanan atas bawah apakah balance

apabila ga balance dia akan perform rotate kaya.

WKOWKOWKOWKO... GA ADA CODINGAN DELETE KALI INI BUAT KALIAN!!

Coba sendiri cara delete itu gimana :v

Bagi yang butuh simulator AVL Tree berikut adalah website buat simulatornya:https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

Sekian dari saya Terima kasih!.Selamat Berkoding!