struc dat ses8
heap adalah sebuah binary search tree yang induknya memiliki nilai >= nilai anaknya.
heap ada 2 jenis yaitu max heap dan min heap.
-min heap memiliki anak kiri yang tidak ada hub dengan anak kanan.
-max heap hampir sama seperti min heap. Hanya saja parrent lebih besar dari child.
INSERTION
masukkan angka1. 51>1.swap 1dan 51. Begitu pula saat 1||50||2.
2
/ \
50 4
/ \ / \
51 100 10 20
/
1
2
/ \
50 4
/ \ / \
1 100 10 20
/
51
1
/ \
2 4
/ \ / \
50 100 10 20
/
51
DELETION
node 1 di hapus.
1
/ \
2 4
/ \ / \
50 100 10 20
/
51
5 1
/ \
2 4
/ \ / \
50 100 10 20
2
/ \
50 4
/ \ / \
51 100 10 20
51 sebagai data paling akhir menjadi root.
node akan di downheap ditukar dengan min(left child,right child)<node min(left child,right child).
Hash Table
hash table adalah truktur data untuk mencari data yang diperlukan dalam waktu O(1)
Hash function ada 3 : Division, Mid-Square, Folding
Division : Membagi string menggunakan modulus
Mid-Square : Melakukan akar pada string/identifier
Folding : membagi string menjadi beberapa part kemudian menyatukannya
Cara mengatasi Collision :
Linear Probing : Cari slot kosong selanjutnya untuk diisi
Chain : Bentuk semacam linked list dari index collision yang sama
No Comments »
RSS feed for comments on this post. TrackBack URL