AVL Tree dan Balanced Tree / 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 yaitu dari yang
seharusnya dari O(h) dimana h adalah height dari tree menjadi hanya O(log n).
Agar Tree tetap seimbang, maka diberikan batasan
sebesar -1, 0, atau 1, dimana batasan ini didapat dari selisih height child
kiri dan child kanan.
Ada beberapa operasi dalam AVL Tree, yaitu:
1. Insert, dalam insert dapat menyebabkan beberapa
masalah miringnya / tidak seimbangnya jumlah child kiri dan child kanan,
berikut beberapa masalah yang ada:
a. Left-left case dan Right-right case:
diselesaikan dengan single rotation yaitu dengan mengambil bagian tengah dari 3
node yang segaris/lurus dan meletakkanya di tengah sebagai parent, dengan 2
node sisanya menjadi cabangnya.
b. Left-right case dan Right-left case
contoh single rotation
2. Deletion, jika node yang dihapus merupakan
leaf, maka setelah dihapus harus di cek keseimbangannya, jika tidak seimbang
maka harus dilakukan rotation. Sedangkan jika yang dihapus bukan node leaf,
maka harus dilakukan deletion seperti pada BST kemudian dengan mengganti node
dengan node terkanan bagian subtree kiri atau node terkiri bagian subtree
kanan, lalu setelah itu dicek keseimbangannya.
***Tambahkan di rangkuman***
AVL dan B-Tree dengan soal:
* insert: 5,6,7,0,4,3,8
* delete: 3,4,8
B-Tree
B-Tree atau Balanced tree atau pohon seimbang
adalah tree yang tidak ada simpul daun yang lebih panjang terhadap daun yang
lain. Search tree adalah tree dimana setiap subtree dari sebuah simpul
mempunyai kunci lebih kecil dari subpohon kanan simpul tersebut. Kunci dalam
sebuah simpul secara konsep berada di antara subtree-subtree dan lebih besar
dari kunci di subtree kiri simpul dan lebih kecil dari kunci di subtree kanan
simpul.
Penyebutan panjang B-Tree dengan banyak m adalah
2, 3,...m-Tree. Misalnya B-Tree dengan m = 4, disebut 2,3,4-Tree.
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
Komentar
Posting Komentar