Summary AVL Tree & B-tree - William Yulio (2301869840)

1. AVL Tree
AVL Tree merupakan salah satu jenis BST (binary Search Tree). BST digunakan dengan tujuan untuk mempercepat pencarian data. Apabila BST yg terbentuk cukup seimbang (mendekati complete binary tree) maka waktu pencarian data tidak lebih dari log2n langkah.

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.
Berikut merupakan contoh AVL tree :

Sebelum masuk kedalam proses insertion dan juga deletion dalam AVL tree, maka kita harus mengetahui Cara menentukan Height dan Balance Factor :

Height :
- Jika node (root) tidak memiliki subtree heightnya = 0
- Jika node adalah leaf, height =  1
- Jika internal node, maka height =  height tertinggi dari anak + 1

Balance Factor (-1,0,1) :-Balance Factor = Height dari anak kiri - height dari anak kanan
-Apabila balance factor dari node tersebut bukan diantara -1, 0 , dan 1 , berarti terjadi violation/pelanggaran dimana berarti terdapat subtree yang harus dirotate

• Insertion - AVL Tree

  Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di insert.

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

anggap T adalah node yang harus diseimbangkan kembali

- Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
- Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
- Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
- Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Berikut contoh dari kasus kasusnya :

Kasus beserta cara merotatenya

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
- Kasus 1 dan 2 dengan single rotation
- Kasus 3 dan 4 dengan double rotation

Single Rotation

Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right

Gambaran Single Rotation :

pada contoh diatas, left-left karena dari 30 ke 22 ke kiri, dan dari 22 ke 15 ke kiri juga

Double Rotation

Double rotasi (rotasi 2x) dilakukan apabila searah, left-right atau right-left.

Gambaran Double Rotation :

Step 1 (Rotasi pertama)
kasus diatas adalah left-right

Step 2 (Rotasi kedua)

kasus diatas, left-left

• Deletion - AVL Tree

Proses deletion pada AVL Tree sama dengan BST namun terdapat tambahan dimana setiap terjadi penghapusan/deletion pada sebuah node maka path yang dilalui untuk dapat menghapus node tersebut harus di cek balance factornya apakah terdapat violation atau tidak, dimana terdapat beberapa kondisi :

-Apabila node yang ingin dihapus merupakan leaf, maka node bisa langsung dihapus.

-Kalau node tersebut memiliki 1 child, maka node tersebut akan digantikan oleh anaknya

-Kalau node tersebut memiliki 2 child, maka anak kiri yang paling kanan lah yang akan menggantikan node tersebut.

Contohnya sebagai berikut :

Delete node 60

node 55 tidak balance, karena anak kiri 0 dan anak kanan 2, selisih 2.
diseimbangkan dengan single rotation (left-left) karena 55 ke 65 kiri dan 65 ke 70 kiri
akan tetapi, node 50 menjadi tidak balance, di subtree kiri 4 dan subtree  kanan 2

diseimbangkan dengan double rotation (left-right) karena dari 50 ke 25 kiri dan 25 ke 40 kanan

AVL Tree yang sudah balance

2. 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 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 terbawa

B-tree berordo 4

• Operasi : 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.

Contoh :

Gambar dibawah ini adalah operasi insertion pada b-tree berordo 5

• Operasi : 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.
• Jika ukuran P > m/2 maka langsung delete saja data yang ingin dihapus
• Jika ukuran P = m/2 maka : perhatikan siblingnya (anggap sibling adalah Q)
• Q > m/2, maka rotasi pada P
• Q = m/2, satukan P dan Q

Contoh :

Delete pada b-tree berordo 5