Summary: AVL tree and B tree

AVL tree

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.

agar tree tetap seimbang, setelah meletakkan sebuah node,kita harus melakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan 2 cara yaitu Single rotation dan Double rotation

Single rotation

Single rotation dilakukan apabila searah, left-left atau right-right

contoh:

Double rotation

Double rotation dilakukan apabila searah, left-right atau right-left.

AVL Tree Deletion

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.

B Tree

Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree. 2-3 Tree pada postingan sebelumnya yaitu Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree merupakan salah satu B-Tree berorder 3. Itu sebabnya setiap nodenya memiliki batasan anak, dengan minimal 2 anak dan maksimal 3 anak.

Aturan pada B-Tree : m = order

Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
Root memiliki anak minimal 2, selama root bukan leaf
Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
Data yang tersimpan pada node harus terurut secara inorder
Semua leaf berada pada level yang sama, level terbawah

Insertion

Aturan Insertion :

Anggap data yang mau di insert adalah key
Posisikan key pada node yang sesuai, seperti pada BST dan 2-3 Tree, anggap node tersebut A
Jika A adalah node dengan jumlah data kurang dari m-1, maka langsung masukan saja
Jika A adalah node dengan jumlah data m-1, maka masukan nilai tengah kemudian masukan ke parentnya. Kemudian anggaplah parent tersebut A. Kemudian periksa kembali sesuai aturan point ke 3 dan 4.

Deletion
Aturan Deletion :

Anggap node yang mau di delete adalah key

Delete dilakukan pada leaf. Meskipun pada saat menghapus node parent, kita tetap menganggapnya menghapus leaf, karena ketika parent dihapus lalu digantikan oleh anak terbesar subtree kiri atau anak terkecil subtree kanan sama saja kita seolah-olah menghapus anak yang menggantikannya. dimana anak tersebut selalu berada pada posisi leaf. maka leaf tersebut dianggap P.