Summary of B-Tree and AVL Tree

May 17, 2020

Summary of B-Tree and AVL Tree

B-Tree dan AVL Tree merupakan konsep data struktur yang keduanya berasal dari konsep data struktur Binary Search Tree yang dimodifikasi agar lebih optimal dalam proses pencarian data-datanya.

1. B-Tree

Dalam Binary Search Tree, setiap node memiliki 1 data, dan maksimal 2 anak. Konsep data struktur B-Tree memungkinkan bagi satu node untuk memiliki lebih dari 1 data dan anak. Oleh karena itu, B-Tree memiliki ordo. Jumlah maksimum anak dalam satu node di B-Tree akan ditentukan dari ordo B-Tree tersebut, dan jumlah maksimum data dalam satu node ditentukan dari ordo-1.

B-Tree memiliki beberapa operasi, seperti : search, insert, dan delete. Contohnya adalah B-Tree dengan ordo 3 (biasa disebut 2-3 Tree) yang dapat memiliki maksimal 2 data dalam satu node, dan 3 anak. Contohnya adalah sebagai berikut :

(Insert : 5, 6, 7, 0, 4, 3, 8)

Apabila menggunakan Binary Search Tree:

Apabila menggunakan B-Tree:

Dapat dilihat bahwa 1 node memiliki data maksimal sebanyak 2 data, dan tree tersebut dapat memiliki anak maksimal sebanyak 3. Sekarang kita akan mencoba melakukan delete.

(Delete : 3, 4, 8)

B-Tree akan lebih optimal dibandingkan Binary Search Tree dalam proses searching. Hal tersebut dikarenakan level / height dari B-Tree akan lebih sedikit dibanding Binary Search Tree, dan data-datanya pun sudah di sort.

2. AVL Tree

AVL Tree bisa juga disebut self-balancing binary search tree. Dikarenakan dalam AVL Tree level subtree kiri dan subtree kanannya memiliki maksimal 1 perbedaan level. Apabila ditemukan perbedaan level antara subtree kiri dan kanan lebih dari 1 level, maka tree akan menyeimbangkan kembali setiap node nya agar perbedaan levelnya tidak lebih dari 1. Proses re-balancing ini ada di saat insert menggunakan single rotation maupun double rotation. Berikut adalah contoh penggunaan AVL Tree:

(Insert : 5, 6, 7, 0, 4, 3, 8)

Apabila menggunakan Binary Search Tree: