25/05/2016 – Data Structure

Heap, Tries and Hashing

Heap adalah sebuah Complete Binary Tree yang memenuhi persyaratan heap. Heap terdiri dari dua jenis, yaitu max heap, min heap dan ada pula min-max heap.

heapfig2

Tries adalah struktur datayang tersusun yang digunakan untuk menyimpan array yang bersifat asosiatif. Root nya dibuat 0 untuk memudahkan proses pencarian menggunakan formula search nantinya.

Hashing adalah transformasi dari string karakter menjadi nilai panjang biasanya lebih pendek atau kunci yang mewakili string asli. Fungsi dari Hash adalah sebagai berikut:

  1. Divison : dengan modulus ( h(x) = x Mod M)
  2. Mid-square : dengan mengkuadratkan setelah itu ambil digit tengah hasil kuadrat (h(k) = s)
  3. Folding : dengan cara mememisahkan angka menjadi dua bagian, lalu jumlahkan angka tersebut. Ambil beberpa digit dari halsilnya.

 

Leave a Reply

Your email address will not be published. Required fields are marked *