HEAP and TRIES

HEAP

Heap adalah sebuah complete binary tree.

Sebuah tree disebut heap maksimum saat semua node nilainya lebih besar dari childnya. (Semakin kebawah semakin kecil)

Sebuah tree disebut heap minimum saat semua node nilainya lebih kecil dari childnya. (Semakin kebawah semakin besar)

Contoh max heap:

Contoh min heap:

Insertion

I. Max heap

Saat node baru diinsert, lakukan pengecekan terhadap parentnya. Jika node baru bernilai lebih besar dibandingkan parent, tukar posisinya dengan parent. Lakukan pengecekan tersebut sampai syarat tidak terpenuhi lagi.

II. Min heap

Saat node baru diinsert, lakukan pengecekan terhadap parentnya. Jika node baru bernilai lebih kecil dibandingkan parent, tukar posisinya dengan parent. Lakukan pengecekan tersebut sampai syarat tidak terpenuhi lagi.

Deletion

Deletion pada heap pasti dilakukan di root, lalu ditukar posisi dengan node pada posisi terakhir. Lalu cek node tersebut dengan childnya sesuai dengan heapnya (jika max heap, tukar node dengan childnya jika node tersebut lebih kecil dari childnya, sebaliknya untuk min heap).

MIN-MAX HEAP

Min-max heap adalah kombinasi dari min heap dan max heap.

Tiap levelnya akan berganti antara min heap dan max heap.

Kegunaan min-max heap adalah untuk menemukan nilai max dan min dalam 1 heap saja.

Insertion

Jika node baru berada di level min, bandingkan dengan parentnya. Jika parent lebih kecil dari node baru, maka tukar node dengan parentnya, lalu upheapmax. Jika tidak, upheapmin.

Jika node baru berada di level max, bandingkan dengan parentnya. Jika parent lebih besar dari node baru, maka tukar node dengan parentnya, lalu upheapmin. Jika tidak, upheapmax.

Deletion

I. Delete min

Tuker root dengan node terakhir dari heap lalu hapus root yang sudah berada di node terakhir tersebut. Downheapmin dari root.

II. Delete max

Tukar anak kiri atau kanan dari root dengan node terakhir dari heap lalu hapus. Downheapmax dari node tersebut.

TRIES

Tries adalah suatu tree sruktur data yang digunakan untuk menyimpan array asosiatif.

Trie berasal dari kata RETRIEVAL, karena tries dapat menemukan satu kata dalam kamus dengan hanya awalan kata.

Contoh tries:

Hashing

• Hashing adalah transformasi dari sebuah string menjadi sebuah string baru yang merepresentasikan string originalnya
• Hashing dilakukan untuk memberi index dan mengambil/mencari data di database 
• Salah satu cara untuk Hashing adalah dengan menggunakan hash table
• Hash Table
• Properties pada hash table:
• Array yang menyimpan value dari original string
• Index dari hash table adalah hasil dari hashing

• Pada hashtable dapat terjadi Collision. Collision adalah ketika beberapa string memiliki index yang sama 
• Collision dapat diatasi dengan Linear Probing dan Chaining
• Linear Probing
• Linear probing dilakukan dengan cara menulis banyak step 
• Banyaknya step dilakukan sesuai dengan urutan insert dengan string lain dengan index yang sama contoh:

• Chaining
• Chaining adalah hash table yang di implementasikan dengan linked list
• Tiap index di simpan pada chain(linked list). 
• Jika terdapat string baru dengan index sama, maka tinggal di lakukan iterasi(disambung dengan next node) pada chain tersebut