Rangkuman Struktur Data 8

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 string yang berupa karakter menjadi sebuah versi yang lebih pendek sambil tetap mewakili karakter awalnya.

Fungsi dalam hashing:

• Mid-square: String dikuadratkan, lalu ambil nilai tengah untuk menjadi hash key.
• Division : Bagi string dengan menggunakan operator modulus.
• Folding : Bagi string menjadi beberapa bagian, kemudian tambahkan bagian-bagian tersebut untuk mendapatkan hash key.