CA01-011 Heap & Tries

Max Heap : pohon yang parentnya selalu lebih besar dari anaknya

Min Heap : pohon yang parentnya selalu lebih kecil dari anaknya
Min-Max Heap : Pohon yang selang-seling parentnya


Heap biasanya menggunakan array, tapi bisa menggunakan linked list juga.
Dimulai dari 1 untuk memudahkan mencari node.

Insert dalam heap dilakukan dengan seperti berikut:
1.       Insert node seperti dalam Binary Tree
2.       cek apakah angka tersebut memenuhi syarat (lebih besar dari parentnya untuk min heap, lebih kecil dari parentnya untuk max heap)
3.       Jika salah, maka angka tersebut ditukar dengan parentnya
4.       lakukan step 2 dan 3 sampai node tersebut memenuhi syaratnya, atau node tersebut berada di posisi root
aksi yang dilakukan tersebut disebut Heapify Up
untuk delete dilakukan sebagai berikut:
1.       hapus root dari pohon tersebut
2.       insert elemen paling terakhir yang di-insert
3.       cek apakah angka tersebut memenuhi syarat (lebih kecil dari childnya untuk min heap, lebih besar dari childnya untuk max heap)
4.       Jika salah, maka angka tersebut ditukar dengan parentnya
5.       lakukan step 3 dan 4 sampai node tersebut memenuhi syaratnya, atau node tersebut berada leaf/tidak punya child lagi

aksi yang dilakukan tersebut adalah Heapify Down
Insert dan delete min-max heap dilakukan dengan cara berikut:
Insert
1.       Insert node seperti dalam Binary Tree
2.       cek apakah angka tersebut memenuhi syarat (lebih besar dari parentnya untuk level min, lebih kecil dari parentnya untuk level max)
3.       Jika salah, maka angka tersebut ditukar dengan parentnya
4.       lakukan step 2 dan 3 sampai node tersebut memenuhi syaratnya,
5.       kemudian, cek apakah angka tersebut memenuhi syarat terhadap grandparent/2 depth di atasnya. Jika tidak memiliki grandparent, berhenti.
6.       Jika salah, maka angka tersebut ditukar dengan grandparentnya
7.       lakukan step 5 dan 6 sampai node tersebut memenuhi syaratnya, atau node tersebut berada di posisi root.
Delete (min)
Dimisalkan x adalah elemen terkecil dari children dan grandchildren dari node yang ingin dihapus
1.       jika x adalah grandchildren dari node tersebut
1. 1 jika x lebih kecil dari node tersebut, tukar node tersebut dengan x.
1. 2 jika x lebih besar dari parent, maka tukar x dengan parentnya
1. 3 lakukan 1.1 dan 1.2 hingga sesuai dengan syaratnya

2.        jika x adalah children dari node tersebut
1. 1 jika x lebih kecil dari node tersebut, tukar node tersebut dengan x.

Id parent (x) = x/2
Id left-child (x) = 2*x
Id Right-child(x) = 2 * x + 1

Tries digunakan di autocomplete, searching, buble words, list/set/collection
Tries : sebuah tree yg vertex/nodenya mewakili satu kata


-character
-Map (Character,Trie)
-Bool IsEnd

Komentar

Posting Komentar

Postingan populer dari blog ini

CA01-006

Linked List Butuh malloc untuk alokasi value ke memory yang berbeda Pointer next dibuat untuk menyimpan data setelahnya, struct data untuk recursive Indikator posisi awal dengan if head==NULL Pergeseran dilakukan dengan next->curr Tail->Next==NULL Sebagai penanda akhir list Next adalah alamat curr setelah bergeser Menghapus/pop dengan menggeser curr/tail ke alamat sebelumnya Double Linked List Double linked list adalah single linked list yang memiliki 2 arah. Tidak seperti single linked list yang hanya bergeser dari head ke tail, double linked list bisa begeser ke arah sebaliknya Keuntungan Double linked List 1.         Implementasinya tidak jauh berbeda dari Single linksed list 2.         Mampu bergeser dua arah 3.         Deletion lebih mudah dilakukan, karena tidak perlu menggunakan pointer node dan pointer node sebelum yang akan...
Baca selengkapnya

CA01-004

BST/ Binary Search Tree BST adalah sebuah cara untuk mengurutkan data berdasarkan Hieerarki. Karena Binary, masing-masing node hanya punya boleh keturunan maksimum dua. Dalam penyusunannya, data yang lebih besar ada di kanan dan data yang lebih kecil ada di kiri, bisa juga sebaliknya. Insert: insert dalam BST setelah insert pertama adalah ·          Jika node yang dimasukkan lebih besar dari node atasnya, maka keturunannya akan ada di bawah dan diletakkan di sisi kanan node tersebut. ·          Jika node yang dimasukkan lebih kecil dari node atasnya, maka keturunannya aka nada di bawah dan diletakkan di sisi kiri node tersebut Pop : Pop dalam BST memiliki aturan sebagai berikut: ·          Jika pop dilakukan pada leaf/ node yang tidak memiliki keturunan maka node tersebut akan langsung di pop ·          Jika pop...
Baca selengkapnya