AVL Tree
Halo dulur - dulur sekalian. udah lama nih gak bikin ginian lagi. dari 006 ke 010 karna ada uts hehe.
jadi kali ini kita akan ngebahas AVL Tree. AVL tree sendiri lebih rumit dari BST. jujur aj ane sendiri gak bisa hehe. tpi kali ini kita bakal ngebahas teorinya dulu biar kalo simulasiin ngerti dan gk bengong doank.
langsung aja deh.
AVL Tree ditemukan oleh Adelson-Velskii dan Landis. AVL Tree merupakan salah satu jenis BST (binary Search Tree). BST digunakan dengan tujuan untuk mempercepat pencarian data. Apabila BST yg terbentuk cukup seimbang (mendekati complete binary tree) maka waktu pencarian data tidak lebih dari log2n langkah.
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.
Insertion
rule di AVL tree adalah, ketika melakukan insert maka :
1. jika nilai lebih besar maka, nilai berada disebelah kanan
2. jika nilai lebih kecil maka, nilai berada disebelah kiri
jika kedalaman tree tidak balance (perbandingan > 1) maka kita harus melakukan menyeimbangkan tree tersebut.
kita bisa menyeimbangkan tree ini menggunakan single rotation
apabila single rotation masih belum menyeimbangkan tree maka kita akan menggunakan metode double rotation.
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.
Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :
– Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
atau klo mau video bisa cek link ini https://www.youtube.com/watch?v=jDM6_TnYIqE
jadi segini aja dulu, jujur aja klo disuruh bikin codingannya sih blom ngerti wkwkwk
tapi setidaknya secara teori memang harus dimantepin dulu sih.
Tidak ada komentar:
Posting Komentar