AVL Tree
Dalam ilmu komputer, AVL
tree adalah binary tree yang dapat menyeimbangkan dirinya sendiri. AVL tree
merupakan subtree kiri dan subtree kanan yang memiliki perbedaan tinggi atau
level maksimal 1. Dengan AVL tree, akan dipersingkat dan disederhanakan dalam
waktu pencarian dan bentuk treenya. Di dalam AVL tree, path pencarian lokasi
dilakukan operasi insert dimulai dari root. Operasi pencarian elemen pada AVL
tree relatif sama dengan binary search tree. Hal ini dikarenakan AVL tree itu
sedikit dimodifikasi dengan menambah properti khusus yaitu keseimbangan pohon
dari binary search tree.
Terdapat 4 kasus yang ada
pada AVL tree :
1.
Left – Left :
simpul terdalam terletak di sub pohon kiri anak kiri T.
2.
Right – Right
: simpul terdalam terletak di sub pohon kanan anak kanan T.
3.
Right – Left
: simpul terdalam terletak di sub pohon kanan anak kiri T.
4.
Left – Right
: simpul terdalam terletak di sub pohon kiri anak kanan T.
Single Rotation
Berdasarkan kasus yang
disebutkan diatas, kasus 1 & 2 merupakan kasus single rotation.
Double Rotation
Berdasarkan kasus yang
disebutkan diatas, kasus 3 & 4 merupakan kasus double rotation.
B-Tree
Dalam ilmu komputer,
B-tree adalah struktur data pohon self-balancing yang memelihara data yang
diurutkan dan memungkinkan pencarian, akses sekuensial, penyisipan, dan
penghapusan dalam waktu logaritmik. B-tree menggeneralisasikan pohon pencarian
biner, memungkinkan untuk node dengan lebih dari dua anak. Tidak seperti pohon
pencarian biner self-balancing lainnya, B-tree sangat cocok untuk sistem
penyimpanan yang membaca dan menulis blok data yang relatif besar, seperti
disk. Ini biasanya digunakan dalam database dan sistem file.
Pencarian di B-tree mirip
dengan pencarian di Binary Search Tree. Misalnya kunci yang akan dicari adalah
k. Pertama-tama mulai dari root dan secara rekursif melintasi. Untuk setiap
node non-leaf yang dikunjungi, jika node tersebut memiliki kunci, cukup
mengembalikan node tersebut. Kalau tidak, kembali ke anak yang sesuai dari
node. Jika kami mencapai simpul daun dan tidak menemukan k di simpul daun, kami
mengembalikan NULL. Perhatikan bahwa anak yang tepat sebelum kunci pertama yang
lebih besar.
Traversal pada B-tree juga
mirip dengan Inorder traversal dari Binary Tree. Pertama-tama mulai dari child
paling kiri, mencetak secara rekursif child paling kiri, kemudian mengulangi
proses yang sama untuk child dan kunci yang tersisa. Pada akhirnya, cetak
secara rekursif child yang paling kanan.
Sumber :
Tidak ada komentar:
Posting Komentar