NIM : 2301863811
Kelas : CB01
Nama Dosen :
- Ferdinand Ariandy Luwinda (D4522)
- Henry Chong (D4460)
Kelas : LB08
Nama Dosen :
- Diana (D4458)
AVL TREE
Pengertian 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.
Contoh AVL Tree
Tree diatas adalah AVL karena perbedaan tinggi kanan dan kiri subtrees untuk setiap nodes sama dengan satu atau dibawah satu.
Contoh bukan AVL Tree
Mengapa AVL Tree?
Sebagian besar operasi Binary Search Tree (search,insertion,deletion,dll) membutuhkan O(h) waktu dimana h adalah ketinggian BST, bahkan bisa O(n) untuk Binary Tree yang miring. Jika ketinggian pohon disesuaikan menjadi O(log n) setelah semua operasi insertion dan deletion, maka bisa dipastikan batas atas O(Log n) untuk semua operasi. Ketinggian AVL Tree selalu O(Log n) dimana n adalah jumlah node di pohom.
Insertion
Untuk memastikan Tree tetap AVL Tree setelah semua insertion, kita harus menggunakan operasi insertion standar BST untuk penyeimbangan. Berikut adalah 4 operasi dasar yang bisa dilakukan untuk menyeimbangkan Tree tanpa melanggar properti Tree (keys(left) < key(root) < keys(right))
Single Rotation
1. Left-left rotation
Jika Tree tidak seimbang, ketika sebuah node di insert ke subtree kanan nya subtree kanan, maka kita lakukan Single Left Rotation.
Di contoh, node A menjadi tidak seimbang karena sebuah node di insert ke subtree kanan nya subtree kanan A. Rotation dilakukan dengan membuat A subtree kiri dari B.
2. Right-right rotation
AVL Tree akan menjadi tidak seimbang apabila sebuah node di insert ke subtree kiri nya subtree kiri. Tree akan membutuhkan Single right rotation.
Double Rotation
3. Left-right rotation
Double rotation agak sedikit lebih kompleks dibandingkan single rotation. Agar lebih mengerti, kita harus membahas setiap langkah satu persatu. Left-right rotation adalah kombinasi left rotation diikuti right rotation.
Sebuah node di insert ke subtree kanan nya subtree kiri. Itu menyebabkan C menjadi node tidak seimbang. Skenario ini membuat AVL melakukan Left-right rotation.
Pertama kita lakukan left rotation di subtree kiri dari C. Ini membuat A menjadi subtree kiri dari B.
Node C masih belum seimbang, tetapi sekarang karena subtree kiri dari subtree kiri.
Sekarang kita lakukan right rotation ke Tree, membuat B menjadi root baru di subtree ini. C sekarang menjadi subtree kanan dari subtree kirinya.
Tree sudah seimbang.
4. Right-left rotation
Double rotation kedua, adalah kombinasi dari right rotation dilanjutkan dengan left rotation.
Sebuah node telah di insert ke subtree kiri dari subtree kanan. Ini menyebabkan A menjadi tidak seimbang.
Pertama kita lakukan right rotation di node C, membuat C menjadi subtree kanan dari subtree kiri nya sendiri (B). Sekarang B menjadi subtree kanan nya A.
Node A masih belum seimbang karena subtree kanan dari subtree kanan, sehingga membutuhkan left rotation.
Left rotation dilakukan dengan membuat B menjadi root node yang baru dari subtree. A menjadi subtree kiri dari subtree kanan B.
Tree sudah seimbang.
Deletion
Menghapus sebuah node di AVL Tree mirip dengan BST. Deletion bisa mengganggu keseimbangan AVL Tree, maka Tree harus diseimbangkan setelahnya dengan melakukan rotation.
Terdapat 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :
- Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.- Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Tree dengan AVL.
Rotation yang digunakan sama dengan insertion, yaitu :
1. Left Rotation
2. Right Rotation
3. Left-right Rotation
4. Right-left Rotation
Contoh Deletion:
Kita mau delete node 30 di tree diatas
Disini, node B mempunyai faktor keseimbangan 0, maka Tree di rotate dengan right rotation. Node B menjadi root, sedangkan A dipindahkan ke kanan. Anak kanan dari node B menjadi anak kiri node A.
2-3 Tree (B-Tree)
2-3 Tree adalah salah satu tipe struktur
data yang setiap node internal memiliki satu elemen data dan dua anak atau dua
elemen data dan tiga anak. Jika sebuah node berisi satu elemen data value kiri, ia memiliki dua subtree yaitu
kiri dan tengah. Sedangkan jika sebuah node berisi dua elemen data value kiri dan value kanan, ia memiliki tiga subtree yaitu kiri, tengah dan kanan.
Keuntungan dari 2-3 Tree adalah lebih seimbang bila dibandingkan dengan Binary
Search Tree.
INSERTION
Tahap
/ Aturan dalam melakukan insertion:
1. Pertama
kita harus mencari dimana data tersebut harus diletakkan di 2-3 Tree
menggunakan searching, maka akan ditemukan 1 leaf yang tepat untuk melakukan
insertion.
Ada 3 kemungkinan kasus dalam insertion
(1) Insert
di node yang hanya ada 1 elemen data
(2) Insert
di node yang memiliki 2 elemen data yang parent nya hanya memiliki 1 elemen
data
(3) Insert
di node yang memiliki 2 elemen data dan parent nya juga memilki 2 elemen data
2. Jika
leaf yang dituju memiliki 2 node, maka kita cukup insert data baru tersebut,
sehingga menjadi 3 node.
3. Jika
leaf yang dituju sudah memiliki 3 node. Maka simulasikan dengan memasukkan data
baru diantara data A dan B (A dan B adalah dua data yang terdapat di 3 node
tersebut). Nilai data yang berada di tengah-tengah antara nilai A, B, dan data
baru akan naik ke parent dan membagi 2 sisanya menjadi 2 node. Secara rekursif
memperbaiki pada parent nya.
DELETION
Tahap
/ Aturan dalam melakukan delete
1. Seperti
BST, pertama kita harus melakukan searching untuk leaf yang memiliki data yang
kita cari.
2. Jika
leaf nya memiliki 3 node, maka kita tinggal melakukan operasi delete dan
dijadikan 2 node.
3. Jika
leaf nya memiliki 2 node:
-
Jika parent memiliki 3 node, maka ambil 1
nilai dari 3 node tersebut. Jika sibling nya 3 node, maka dorong nilai tersebut
dari sibling ke parent untuk membuat parent menjadi 3 node lagi. Jika sibling
nya adalah 2 node, buat parent nya menjadi 2 node dan gabungkan node dengan
sibling nya.
-
Jika parent nya 2 node, jika sibling nya 3
node, maka ambil satu nilai dari parent dan dorong satu nilai dari sibling ke
parentnya sendiri. Hal lainnya yaitu mengabungkan parent dengan sibling.
Red Black Tree
Red Black Tree
adalah salah satu tipe self-balancing BST (disebut juga simetris binary B-tree)
yang kompleks dengan menggunakan warna merah dan hitam. Meskipun RBT rumit,
tetapi sangat efisien saat melakukan insert, delete, search.
Karakteristik Red Black
Tree:
1.
Setiap node berwarna merah (Red) atau
hitam (Black).
2.
Root node selalu berwarna hitam.
3.
Setiap node leaf juga berwarna hitam.
4.
Node yang berwarna merah akan memiliki 2
child berwarna hitam (node merah tidak boleh memiliki child merah).
5.
Jumlah node hitam sama dari root ke
eksternal node.
6.
Node yang berada dibawah root apabila di
level yang sama, disebut juga sibling.
7.
Tree seimbang apabila selisih level antara
subtree kanan dan kiri root hanya berselisih 2.
Insertion
pada RBT
Insertion
pada Red Black Tree memiliki beberapa aturan, yaitu:
1.
Node yang di-insert awalnya akan diberi
warna merah kecuali root. (Apabila melanggar karakteristik RBT baru diubah
warnanya).
2.
Jika parent dari node yang baru di-insert
berwarna hitam maka tidak terjadi pelanggaran.
3.
Jika parent dari node yang di-insert
berwarna merah juga maka akan dilakukan rotasi atau pewarnaan ulang, cara-nya
sebagai berikut:
-
Jika node yang di-insert memiliki
paman/uncle (sibling dari parent) yang berwarna merah. Maka ubah warna parent
dan uncle menjadi hitam dan kakek dari node tersebut menjadi merah (kecuali
jika kakek adalah root).
-
Jika node yang di-insert memiliki parent
merah tetapi paman-nya berwarna hitam (atau NULL), maka bisa dilakukan single
atau double rotation. Ganti pivot terakhir menjadi hitam dan anaknya menjadi
merah.
4.
Perlu diingat bahwa node yang tidak
memiliki leaf harus berwarna hitam.
Deletion
pada RBT
Berikut cara melakukan deletion pada Red Black Tree:
1. Delete
dilakukan seperti pada Binary Search Tree
2. Jika
node yang ingin di-delete berwarna merah, maka tinggal kita ganti node yang
ingin dihapus dengan childnya yang berwarna hitam.
3. Jika
node yang ingin di-delete berwarna hitam, maka ganti node yang ingin dihapus
dengan childnya dan ubah warna childnya menjadi warna hitam.
4. Jika
node yang ingin di-delete dan childnya sama-sama berwarna hitam, maka yang
harus kita lakukan adalah :
a. Ganti
node yang ingin dihapus dengan childnya, lalu, ganti childnya sehingga
mempunyai token double black (N).
b. Jika
siblingnya berwarna merah tukar warna N dan parentnya, lalu rotate di parentnya.
c. Jika
sibling, child kiri, dan child kanan berwarna hitam, maka ganti warna sibling
menjadi merah.
d. Jika
sibling berwarna hitam, child kiri dan child kanan nya berwarna merah, maka lakukan
single atau double rotation.
5. Jika
node yang ingin di-delete adalah root, maka token double black bisa dihapus.
Heap adalah struktur data tree yang merupakan complete binary tree (bukan binary search tree). Heap memiliki beberapa properties yaitu :
1. Min Heap
- Setiap node lebih kecil dari masing-masing childnya.
- Root memiliki nilai terkecil. Nilai terbesar terletak di leaf node.
2. Max Heap
- Setiap node lebih besar daripada childnya.
- Root memiliki nilai terbesar. Nilai terkecil terletak di leaf node.
- Heap dengan Min Heap pada level genap dan Max Heap pada level ganjil.
Heap dapat diimplementasikan dengan array juga linked list.
Aplikasi pada heap :
1. Priority Queue
- Selection Algorithm
- Dijkstra's Algorithm
- Prim Algorithm
2. Heap Sort
Implementasi Heap menggunakan array;
- Array dimulai dengan indeks ke 1
- Rumus umum aplikasi heap dengan array (x adalah current node) :
Parent(x) = x/2
Left-child(x) = 2*x
Right-Child(x) = 2*x+1
Min Heap (Ascending Order) :
- Insertion pada Min Heap
1. Insert node selalu berurutan dari level paling rendah dengan urutan kiri ke kanan.
2. New node selalu menjadi leaf node.
3. Sesuaikan sesuai properti heap secara rekursif.
- Deletion pada Min Heap
1. Node yang dihapus selalu root karena node yang paling kecil, lalu diganti dengan node yang paling terakhir di insert.
2. Sesuaikan dengan properti heap secara rekursif.
Hapus node 7
7 diganti dengan elemen terakhir
Max Heap (Descending Order) :
- Insertion pada Max Heap
1. Periksa apakah node yang akan dimasukkan sudah lebih kecil dibandingkan parentnya.
2. Apabila node yang dimasukkan lebih besar daripada parentnya, maka swap posisi node tersebut dengan parentnya.
3. Begitu seterusnya sampai root merupakan data paling besar.
- Deletion pada Max Heap
1. Jika ingin menghapus root maka yang perlu dilakukan adalah menggantikan root dengan menggunakan node paling terakhir dari tree.
2. Jika root masih lebih kecil daripada child-nya, maka swap root dengan child-nya.
3. Begitu seterusnya sampai data di root merupakan data terbesar.
Min-Max Heap
- Insertion pada Min-Max Heap
Insert node sesuai urutan, lalu cek upheap lalu sesuaikan dengan properties level. Umumnya dilakukan penyesuaian rekursif dengan urutan sebagai berikut:
1. Parent
2. Grand Parent
- Deletion pada Min-Max Heap
Deletion selalu dilakukan pada root, lalu sesuaikan dengan downheap sesuai properties. Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebagai berikut:
1. Grand child
2. Child (grand child disesuaikan dengan parentnya)
TRIES
- Tries adalah binary tree yang dilakukan untuk menyimpan array asosiatif.
- Properties pada tries :
1. Setiap node merepresentasikan satu huruf.
2. Root selalu merepresentasikan node kosong.
- Aplikasi pada trees adalah fitur auto complete yang ada pada browser.
~ Thankyou ~
