AVL & B-Tree

AVL

Kata AVL itu sendiri berasal dari nama pembuatnya yaitu Adelson-Veleskii dan Landis. Sebelum menjelaskan AVL kita perlu mengetahui apa itu BST (Binary Search Tree). Dimana Trees merupakan data non-linier menunjukkan relasi dari hirarki object - object data. Trees menggunakan teknik pointer untuk menyambungkan node dengan node di dalam tree. Dan sedangkan Binary Tree Mirip dengan konsep atau bentuk Tree pada umumnya, tetapi setiap parent (node) memiliki minimal 2 anak, dan 2 anak tersebut biasanya dianggap menjadi left child dan right child dan sama seperti konsep tree node yang tidak memiliki anak disebut leaf. Lalu BST (Binary Search Tree) sebenarnya memiliki kemiripan dengan yang diatas tadi, BST merupakan struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap anak node sebelah kiri selalu lebih kecil nilainya dari pada root node, dan juga sebaliknya dimana anak node sebelah kanan selalu lebih besar daripada root node.

Setelah memahami sedikit tentang BST maka kita dapat membahas tentang AVL dimana AVL itu merupakan salah satu jenis dari BST yang tujuannya juga untuk mempercepat pencarian data. Bedanya yaitu AVL itu sendiri merupakan balanced BST. AVL Tree adalah BST yang memiliki perbedaan height atau tinggi maksimal 1 antara sub tree atau anak kiri dan sub tree kanan. Sama seperti yang dijelaskan tadi, AVL berguna untuk menyeimbangkan BST sehingga proses pencarian pada data lebih cepat dibandingkan BST itu sendiri.

Terdapat beberapa operasi pada AVL yaitu:

• Insertion
• Deletion

Setiap proses tersebut memiliki kondisinya masing - masing dan berikut akan dijelaskan secara singkat.

Insertion

Pada Insertion terdapat 4 kondisi yang akan terjadi saat ingin memasukkan data pada struktur data AVL.

1. Case I (Single Rotation -> LL Rotation). 
2. Case II (Single Rotation -> RR Rotation).
3. Case III (Double Rotation -> LR Rotation).
4. Case IV (Double Rotation -> RL Rotation).

Deletion

Pada Deletion terdapat 3 kondisi yang harus diperhatikan agar tidak terjadi kerusakan atau error pada data.

1. Case I (Jika node yang akan dihapus tidak memiliki child kiri maupun kanan maka tinggal dihapus).
2. Case II (Jika node yang akan dihapus hanya memiliki satu child saja maka child tersebut yang akan menggantikan parentnya yang akan dihapus tersebut).
3. Case III (Jika node yang akan dihapus memiliki 2 child yaitu child kiri dann juga child kanan, jika terjadi demikin harus ada kesepakatan yang konsisten untuk memilih pengganti node yang dihapus tersebut. Pilihannya antara child sub tree kiri yang paling kanan dan child sub tree kanan yang paling kiri).

Dan setelah melakukan Deletion jangan lupa untuk mengecek lagi height pada AVL tersebut sehingga akan tetap seimbang.

Contoh soal:

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

Delete: 3,4,8

B-Tree

B-Tree memiliki konsep yang sangat mirip dengan AVL dan juga BST dimana bertujuan untuk melakukan pencarian data lebih cepat tetapi lebih spesifik kegunaannya. B-Tree digunakan pada disk. Sebuah tree menyimpan banyak kunci, dan faktor cabang pohon sangat tinggi sehingga pohon dengan ketinggian kecil dapat menyimpan kunci dalam jumalh yang sangat banyak, yang dapat diakses hanya dengan beberapa operasi atau langkah saja. Salah satu penerapan yang spesifik tersebut pada B-Tree adalah untuk database atau basis data.

Seperti yang dijelaskan tadi, B-Tree sangat mirip dengan AVL dan juga BST, tetapi bedanya adalah AVL dan BST pada setiap nodenya memegang satu buah data, sedangkan B-Tree dapat memegang 2 data pada setiap nodenya. dan anaknya dan juga degree memiliki maksimal 3.

Contoh Soal:

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

Delete: 3,4,8