Selasa,10 maret 2020
hi saya jason ,jadi hari ini saya belajar tetng hash table ,tree,dan binary tree
so lets begin
untuk pertama ialah Hash Table
Pengertian dari Hash Table
Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.
Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).
Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.
Operasi Pada Hash Tabel
Ø insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
Ø find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
Ø remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
Ø getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu
contohnya ;
jika ingin menyimapan nama kata, maka kita dapat menyimpan karakter pertama dari setiap string menjadi angka sehingga
Mid Sqaure
Collision
Collision adalah 2 atau lebih kunci memiliki hash code yang sama , yang membuatnya tabrakan atau rebutan.
cara mengatasi Collision:
-Linear Probing
-Chaining
2.Binary Tree
Tree (pohon) adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many). Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai percabangan atas dirinya.
Lalu, ada lagi yang namanya Binary Tree. Apa bedanya? Sebenarnya sama sama konsepnya dengan
Tree. Hanya saja, kita akan mengambil sifat bilangan biner yang selalu bernilai 1 atau 0 (2 pilihan).
Berarti, binary tree adalah tree yang hanya dapat mempunyai maksimal 2 percabangan saja. Untuk
lebih jelasnya, lihat gambar di bawah ini.
Jenis-jenis Binary Tree :
a) Full Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
b) Complete Binary Tree
Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
c) Skewed Binary Tree
Comments
Post a Comment