AVL & B-TREE

AVL TREE DAN B-TREE

Pada pertemuan kali ini saya akan membahas tentang apa yang telah dipelajari selama mengikuti proses vicon di kelas Data Structure tentang AVL Tree dan B-Tree.

AVL TREE

AVL Tree adalah suatu Binary Search Tree yang memiliki perbedaan level maksimal 1 antara subtree kiri dan kanan. AVL Tree digunakan untuk menyeimbangkan Binary Search Tree agar lebih mudah dan cepat dalam melakukan pencarian.

Contoh AVL Tree

Insertion

Untuk menambahkan sebuah node, dilakukan pengecekan agar tree nya balance. Jika pada saat pengecekan ada yang balance factornya lebih dari 1, maka akan dilakukan rotation. Ada 2 jenis rotation yaitu Single Rotation dan Double Rotation.

• Single Rotation

• Double Rotation

Node 8 memiliki balance factor lebih dari 1 sehingga dilakukan rotation. Saat di cek ternyata merupakan right left rotation sehingga termasuk ke dalam double rotation. Solusinya adalah dengan cara menaikkan node 11 keatas agar tree menjadi balance.

Delete

Penghapusan node pada AVL Tree mirip dengan Binary Search Tree. Pada saat penghapusan, dilakukan pengecekan terhadap node yang akan dihapus karena dapat menyebabkan tree menjadi tidak balance. Lakukan rotation agar tree menjadi balance kembali.

B-TREE

B-tree adalah suatu struktur data yang memungkinkan kita untuk mengakses data dengan lebih cepat. B-tree paling berguna pada saat data yang kita gunakan dalam jumlah besar.
Dalam B-tree dikenal istilah order yang berguna untuk menentukan jumlah minimum dan maksimum anak yang dimiliki setiap node. Contoh 2-3 Tree, yang berarti maksimum order adalah 3. Setiap node memiliki batasan minimum anak adalah 2 dan maksimum adalah 3. Order juga dikenal dengan simbol "m".

• Searching : Data dalam B-tree disimpan dalam urutan sehingga untuk mencari data menjadi lebih mudah. Untuk operasi searching, kita harus membandingkan root nya apakah lebih besar atau lebih kecil.

• Insertion : Jika kita ingin memasukkan data baru, kita harus mencari dimana data tersebut harus ditempatkan. Jika leaf adalah 2-node maka langsung masukkan data disana (lalu menjadi 3-node).Jika leaf nya sudah 3-node maka dorong data tengah keatas, lalu bagi data yang tersisa menjadi 2. Lakukan secara rekursif.

• Delete : 

Untuk bagian ini yang menjadi root boleh node terbesar dari subtree kiri atau node terkecil dari subtree kanan. Dalam contoh ini digunakan node terbesar dari subtree kiri.