Archive for Mei 2020
Heaps
Pengenalan
Heap adalah sebuah struktur data berbasis tree yang memenuhi kondisi heap. Berikut merupakan kondisi-kondisi heap:
- Min Heap: Setiap node lebih kecil dari anaknya
- Max Heap: Setiap node lebih besar dari anaknya
Dari kondisi itu, kita dapat simpulkan bahwa node terkecil ada pada root (root dimulai dari index 1 u/ mempermudah dalam membuat relasi antar node), sementara node terbesar ada pada leaf. Heap bisa diimplementasikan dengan ArrayList, namun akan jauh lebih mudah jika menggunakan array.
Pengaplikasian heap pada priority queue:
- Selection Algorithm (mencari min/max, median, elemen terbesar, dll)
- Algoritma Dijkstra (mencari jalan terpendek dalam grafik)
- Algoritma Prim (mencari spanning tree yang minimum)
Sort pada heap memiliki efisiensi O(n.log(n)).
Dalam pengaplikasian heap pada priority queue, terdapat beberapa operasi seperti:
- find-min: mencari elemen terkecil dalam heap
- insert: memasukkan elemen baru dalam heap
- delete-min: menghapus elemen terkecil dalam heap
Relasi antar node pada heap dengan implemetasi array dapat dibuat dengan mudah, seperti berikut:
*misalkan index dari suatu node adalah n
- Index parent = x / 2
- Index left-child = x * 2
- Index right-child = (x * 2) + 1
Operasi
Find-min
Find-min dalam heap dapat dilakukan dengan mudah, karena node terkecil sudah pasti berada di root. Fungsi nya dapat dituliskan seperti:
int findMin(){
return data[1];
}
Insert
Min-Heap
Child dari node selalu lebih kecil dari pada parent.
Berikut adalah step by step dalam melakukan insert pada min-heap:
- Masukkan elemen baru ke bagian akhir heap (pada leaf)
- Jika node baru tersebut lebih besar daripada parentnya, lakukan upheap
- Upheap: bandingkan node dengan parentnya. Jika node > parent, tukarkan posisi antara node dengan parent. Kemudian loop terus hingga parent > node
Berikut adalah step by step dalam melakukan delete pada min-heap:
- Dalam operasi delete pada min-heap, kita hanya harus menghapus node terkecil yaitu root
- Gantikan root dengan node paling akhir dalam heap
- Kurangkan jumlah elemen dalam heap
- Lakukan downheap pada root agar sesuai dengan peraturan heap
- Downheap: bandingkan node dengan kedua childnya (kiri-kanan). Jika node > child, tukarkan posisi
antara node dengan child terkecil. Kemudian loop terus hingga node < child atau node telah menjadi leaf
Max-heap
Child selalu lebih besar dari parent. Cara insertnya sama saja dengan min-heap, hanya saja dengan kondisi yang berkebalikan.
Min-Max Heap
Untuk min-max heap, perhatikan gambar berikut:
Dari contoh diatas kita bisa melihat bagaimana child bisa lebih kecil/besar dari parent tergantung posisi levelnya. Jika node lebih kecil dari parent pada level genap, maka node akan lebih besar dari parent pada level ganjil. Root selalu merupakan elemen terkecil, elemen terbesar sudah pasti merupakan salah satu dari root child.
Insert pada min-max heap sama saja dengan min-heap atau max-heap, namun upheap nya sedikit berbeda. Berikut penjelasan terhadap upheap untuk min-max heap:
- Upheapmin: bandingkan nilai dari node dengan nilai dari grand parentnya. Jika nilai node lebih kecil dari parentnya, tukar nilai antara node dengan parent. Lalu, lanjutkan dengan upheapmin grand parentnya.
- Upheapmax: bandingkan nilai dari node dengan nilai dari grand parentnya. Jika nilai node lebih besar dari parentnya, tukar nilai antara node dengan parent. Lalu, lanjutkan dengan upheapmin grand parentnya.
Delete
Min-Heap
Berikut adalah step by step dalam melakukan delete pada min-heap:
Downheap: bandingkan node dengan kedua childnya (kiri-kanan). Jika node > child, tukarkan posisi
antara node dengan child terkecil. Kemudian loop terus hingga node < child atau node telah menjadi leaf- Dalam operasi delete pada min-heap, kita hanya harus menghapus node terkecil yaitu root
- Gantikan root dengan node paling akhir dalam heap
- Kurangkan jumlah elemen dalam heap
- Lakukan downheap pada root agar sesuai dengan peraturan heap
- Downheap: bandingkan node dengan kedua childnya (kiri-kanan). Jika node > child, tukarkan posisi antara node dengan child terkecil. Kemudian loop terus hingga node < child atau node telah menjadi leaf
Max-heap
Child selalu lebih besar dari parent. Cara deletionnya sama
saja dengan min-heap, hanya saja dengan kondisi yang berkebalikan.
Min-Max Heap
Untuk deletionnya, kita bisa menghapus node terkecil atau node terbesar. Berikut step nya:
- Deletion untuk node terkecil:
- Gantikan root dengan elemen paling akhir dalam heap
- Kurangkan jumlah elemen dalam heap
- Downheapmin dari root
- Deletrion untuk node terbesar:
- Gantikan antara child terbesar (kiri / kanan) dengan elemen paling akhir dari heap
- Kurangkan jumlah elemen dalam heap
- Downheapmax dari node
Downheapmin / Downheapmax:
Misalkan n adalah elemen terkecil dari child atau grand-child dari suatu node
- Jika m adalah cucu dari node:
- Jika m < node: Tukar nilai mereka
- Jika m > node: Tukar nilai mereka dan lanjutkan downheapmin dari m
- Jika m adalah anak dari node:
- Jika m < node: Tukar nilai mereka
Downheapmax sama saja dengan downheapmin, hanya saja operator relasinya dibalik.
Heaps & Tries
Pengenalan
Red-Black Tree diciptakan pada tahun 1972, oleh Rudolf Bayer. Saat pertama kali diciptakan, tree ini disebut "Symmetric Binary B-Tree". Meskipun Red-Black Tree terbilang kompleks, tree ini memiliki running time yang cepat untuk setiap operasinya serta sangat efisien.
Sebuah Binary Tree bisa disebut Red-Black Tree jika memenuhi kondisi berikut:
- Setiap node memiliki warna, antara hitam atau merah
- Root dari tree selalu berwarna hitam
- Semua external node berwarna hitam
- Jika suatu node berwarna merah, maka kedua anaknya pasti hitam
Operasi
Insertion
Red-Black tree merupakan binary tree, karena itu peraturan-peraturan pada binary tree berlaku juga pada red-black tree. Bedanya, saat melakukan insertion pada red-black tree, kita harus memperhatikan kondisi berikut:
- Jika tree masih kosong. Buat node baru sebagai root dengan warna hitam
- Jika node tidak kosong. Buat node baru sebagai leaf node dengan warna merah
- Jika parent dari node baru berwarna hitam, kita tidak perlu lakukan penyesuaian tambahan
- Jika parent dari node baru berwarna merah, cek warna sibling dari parent. Lalu perhatikan kondisi berikut:
- Jika sibling berwarna hitam, lakukan rotation sesuai dengan kondisi tree. Kemudian lakukan recolor
- Jika sibling berwarna merah, lakukan recolor. Kemudian cek apakah parent dari parent node baru adalah root atau bukan. Jika bukan, lakukan recolor kemudian recek dan sesuaikan dengan kondisi yang ada
Contoh insertion:
Deletion
Sama seperti insertion, deletion pada red-black tree juga harus memperhatikan peraturan yang ada pada binary tree. Namun pada red-black tree, deletion memiliki tambahan kondisi yang membuatnya menjadi lebih kompleks.
Penghapusan / deletion hanya bisa dilakukan pada leaf. Node lain selain leaf node hanya mengosongkan value dari node, tanpa menghapus node tersebut.
Ketika suatu node dihapus, dia akan digantikan oleh child nodenya. Warna dari child node akan menimpa warna dari parent. Sehingga saat kita menghapus suatu black node (dan dia mempunyai 2 black child), dia akan menjadi double black (DB). Hal itu juga berlaku pada leaf node, karena setiap leaf node sebenarnya memiliki 2 anak black node yang NULL (secara default).
Berikut kondisi yang perlu diperhatikan:
- Jika node yang ingin dihapus (harus leaf) adalah red node, maka node boleh langsung dihapus tanpa perlu melakukan cek kondisi atau penyesuaian tertentu
- Jika sibling dari DB adalah hitam dan kedua childnya (child dari sibling) adalah black node, ikuti step berikut:
- Hilangkan DB
- Pindahkan hitam ke parent (warna parent berubah jadi hitam jika warna awalnya merah, dan DB jika warna awalnya hitam)
- Buat sibling menjadi merah
- Jika DB masih ada, cek dan sesuaikan dengan kondisi lain
- Jika sibling DB adalah merah, tukar warna antara parent dengan sibling. Lalu rotate parent ke arah DB
- Jika sibling DB adalah hitam, dan childnya (dengan posisi paling jauh dari node DB) adalah hitam dan child lainnya (dengan posisi paling dekat dengan DB) adalah merah:
- Tukarkan warna sibling dari DB dengan warna anaknya (yang paling dekat dengan DB)
- rotate sibling ke arah menjauhi DB
- Lakukan kondisi 5
- Jika sibling DB adalah hitam, dan child dari sibling (yang jauh) adalah merah:
- Tukarkan warna parent dengan sibling
- rotate parent ke arah DB
- Hilangkan DB
- Ganti warna anak sibling yg merah, menjadi hitam
Contoh deletion: