HEAP, TRIES, HASHING

Heap

adalah sebuah objek array yang dapat dengan mudah divisualisasikan sebagai complete tree. Ada korespondensi satu ke satu diantara elemen array dan node dari tree. Tree itu benar2 penuh pada semua tingkatan kecuali mungkin yang terendah, yang diisi dari kiri sampai titik tertentu. Semua node dari heap juga memenuhi hubungan bahwa nilai kunci pada setiap node pada kurangnya sama besar dengan nilai pada anak2nya.

Bentuk : complete binary tree.

Sifat : Setiap node lebih besar dari atau sama dengan masing2 anak sesuai dengan perbandingan predikat yang ditetapkan.

Jenis :

• Min heap : setiap elemen node adalah lebih kecil daripada childrennya. Elemen terkecil akan terletak pada root tree.
• Max heap : setiap elemen node adalah lebih besar daripada childrennya.
• Min Max heap : gabungan dari min heap dan max heap.

Insert : Untuk menambahkan sebuah elemen ke heap harus melakukan operasi up-heap.

Max heap

Min heap

Insertion in min-heap

Delete-Min in Min heap

Min-Max heap

Elemen terkecil ada di root. Elemen terbesar ada di salah satu anak root.

Upheap :

• Jika node baru min-level
  • Jika node baru parent lebih kecil, maka tukar valuenya dan upheapmax dari parent.
  • Atau upheapmin dari node baru.
• Jika node baru max-level
  • Jika node baru parent lebih besar maka tukar valuenya dan upheapmin dari parent.
  • Atau upheapmax dari node baru.

Deletion

• Elemen terkecil
  • Tukar root dengan elemen terakhir di heap
  • Kurangi angka elemen di heap
  • Downheapmin dari root
• Element terbesar
  • Tukar anak kiri/kanan dari root dengan elemen terakhir di heap
  • Kurangi angka dari elemen di heap
  • Downheapmax dari node

Tries

adalah ordered tree struktur data yang digunakan untuk menyimpan asosiatif array, biasanya strings. Sebuah tree dimana setiap vertex memiliki satu huruf/prefix.

Hashing

adalah transformasi dari string karakter menjadi nilai panjang biasanya lebih pendek atau kunci yang mewakili string asli. Digunakan untuk indeks dan mengambil item dalam database karena lebih cepat untuk menemukan item menggunakan kunci hash lebih pendek daripada untuk menemukannya menggunakan nilai asli.