Sunday, May 25, 2014

Heap , Deap !

HEAP
Heap merupakan salah satu proses yang ada dalam Binary Search Tree.
Heap sendiri dibedakan menjadi 3 macam:
       -Min Heap.
       -Max Heap.
       -Min-Max Heap.
Dalam Heap dibedakan menjadi 2 macam Proses : Insertion, dan Deletion.

Min Heap : Memiliki ciri-ciri sebagai berikut;
       -Setiap elemen Node yang ada harus lebih kecil dari elemen Children(anaknya).
       -Elemen Node yang terkecil terletak pada ROOT.
       -Elemen Node yang terbesar terletak pada salah satu node yang ada di LEAVES.

http://bcu.copsewood.net/dsalg/heap/Diagram2.jpg



Berikut adalah konsep Insertion dalam Heap
 
 kita akan memasukkan angka dengan value 2
Pertama-tama yang angka 2 akan dimasukkan ke dalam index angkat terakhir yang ada dalam tree tersebut. Angka 2 akan dimasukkan ke sebelah 8. (selalu diinsert dari node dengan index terakhir).



Disini, pengecekan dilakukan karena ciri-ciri dari heap adalah setiap Node yang ada selalu lebih kecil dari Node anaknya (children). value angka 2 lebih kecil dari parentnya yaitu 6. Maka karena 6 > 2 , angka 2 akan naik dan mereplace kedudukan 6 dan berlaku sebaliknya.




Disini pengecekan pun berhenti karena angka 2 lebih besar dari parent Nodenya yaitu 1. maka insertion dalam Min heap pun telah selesai.

Deletion


Deletion pada root.
Pertama , Root akan dihapus, lalu penggantian akan dilakukan terhadap INDEX terakhir dalam tree. Maka angka 8 akan meng-replace angka 1(yang akan di delete).

Namun, karena ciri2 dalam heap tidak di penuhi dari tree tsb, karena nilai ROOT nya lebih besar dari children yang ada maka pengecekan dilakukan


Karena nilai 8 lebih besar dari nilai 3, maka di swap. dan proses ini dilakukan terus menerus sampai tree tersebut memenuhi syaratnya



















Max Heap
Proses yang ada dalam Max Heap hampir sama dengan Min Heap, hanya pembalikan saja. Dimana ROOT memiliki value yang paling besar, sedangkan leave memiliki value kecil.


http://www.algolist.net/img/max-heap.png

Konsep Insertion dan deletion juga berlaku sama dengan Min heap , namun value yang besar lebih di prioritaskan dari pada yang kecil.

Min - Max Heap

http://upload.wikimedia.org/wikipedia/commons/5/50/Min-max_heap.jpg
Min Max Heap, memiliki konsep dimana, setiap level ganjil dimulai dengan MIN, dan level genap dimulai dengan MAX heap.  Maka, value terkecil terletak dalam ROOT.

Deap

Deap memiliki konsep yang sama heap, lebih tepatnya min-max heap yang lebih sederhana.
Berikut adalah aturan aturan yang ada dalam Deap:
1. root selalu NULL
2. left subtree dari root adalah min-heap
3. right subtree dari root adalah max-heap

Sesuatu yang unik dari deap adalah sesuatu yang bernama "partner". Partner adalah pasangan dari sebuah node dari deap.  Di bawah akan dijelaskan dengan lebih detail mengenai partner. 

http://squadrive.blog.binusian.org/files/2011/06/Picture10.png

Yang dimaksud adalah, lihat bagian tree sebelah kiri, jika diperhatikan bagian kiri memiliki MIN HEAP sedangkan bagian sebelah kanan memiliki MAX HEAP.
Partner adalah Node yang berdampingan dari MIN heap ke Max Heap, contohnya pada gambar sebelah kanan bisa dilihat, bahwa PARTNER dari angka 10 adalah 50, angka 12 dengan 40 dan angka 25 dengan Node yang kosong.
Bila lokasi partner ternyata kosong, maka partnernya menjadi parent dari posisi partner yang seharusnya.


Nama : Dickson
NIM : 1701291283
Binus University









Saturday, May 17, 2014

Red Black Tree

Atau disingkat sebagai RBT, adalah jenis tree yang di seimbangkan dengan pengelompokan warna yang di bedakan menjadi 2 warna yaitu hitam dan merah.

Syarat-Syarat yang berlaku dalam RBT:
  • Setiap Node memiliki warna, antara hitam atau pun Merah.
  • Root yang ada dalam Tree tersebut harus berwarna Hitam.
  • Setiap External Node yang ada berwarna Hitam.
  • Jika sebuah Node berwarna Merah, maka kedua anaknya pasti berwarna Hitam.
Setiap Operasi yang ada dalam Red Black Tree dibagi menjadi 2 Proses, Insertion dan Deletion.

Insertion:
Dalam Insertion, proses yang dilakukan sama dengan Binary Search Tree. Namun memiliki syarat setiap Node yang dimasukan memiliki warna Merah.
Apabila saat Node dimasukkan, memiliki Parent yang berwarna Merah, maka ada pelanggaran yang terjadi dari aturan yang telah ditetapkan.
Untuk memperbaikinya, kita bisa melakukan LL, LR, RR, RL rotation. agar Tree tersebut kembali seimbang dan memenuhi syarat pewarnaan yang ada.

http://www.cosc.canterbury.ac.nz/research/RG/alg/rbtree.gif


 Berikut adalah contoh dari double rotation
http://cs.lmu.edu/~ray/images/rbrestructuring.png

Perhatikan bahwa setiap Node leave terakhir memiliki external node dengan default color black.

Deletion
Berikut adalah catatan yang diberikan dari dosen saya.

Delete
M = target delete
C = pengganti

jika M = red   , C = Black langsung ganti
jika M = black , C = red langsung ganti dan recolor C = black
jika M = black , C = black akan menciptakan token double black di posisi C

C = N
S = sibling
Sl = sibling left
Sr = sibling right
P = parent

kondisi 1 jika S = red , SL & SR = black
maka reverse color P dan S dan rotate di P , token black tetap ada di N
kondisi 2 jika s = black , SL & SR = black
maka recolor S = red , token black pindah ke P
jika warna P = red recolor jadi black jika P = black maka terjadi double black lg
kondisi 3 jika S = black , SL / SR = RED
maka rotate di parent (single/double), parent baru mengikuti warna parent lama dan kedua anaknya jadi hitam , lalu token black hilang

nb : jika token double black berada pada node merah, maka node tsb menjadi hitam dan
token double black hilang.