Hashing table & Binary Tree

1. Hashing
2. Hash Table
3. Hash Function
4. Collision 
5. Tree Concept
6. Binary Tree Concept
7. Type of Binary Tree
8. Property of Binary Tree
9. Expression Tree Concept
10. Threaded Binary Tree Concept

1. Hashing

Hashing adalah proses menghasilkan data keluaran (output data) yang panjangnya tetap dan sama, dari data masukan (input data) yang panjangnya berbeda-beda.Hashing adalah bentuk akses data yang efisien secara komputasi dan ruang penyimpanan yang menghindari waktu akses non-linear dari daftar dan pohon terstruktur yang dipesan dan tidak tersusun, dan persyaratan penyimpanan yang sering eksponensial untuk akses langsung ruang negara dari kunci besar atau panjang variabel.

2. 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).

    

      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

3. Hash Function

Ada banyak cara untuk mengaitkan string menjadi kunci. Berikut ini adalah beberapa metode penting untk membangun fungsi hash:

1. Mid-square

Kuadratkan string/identifier dan kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key. Jika kuncinya adalah string, itu dikonversi ke angka.

2. Division

Membagi string atau pengidentifikasi dengan menggunakan operator modulus. Ini adalah metode hashing integer yang paling sederhana.

3. Folding

Partisi string atau identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash.

4. Digit Extraction

Digit yang ditentukan sebelumnya dari nonor yang diberikan dianggap sebagai alamat hash.

5. Rotating Hash

Menggunakan metode hash lalu setelah mendapatkan kode atau alamat hash dari metode tersebut, lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

4. Collision

Ada 2 cara untuk menanggani :

1. Probing Linier

Cari slot kosong berikutnya dan letakkan talinya di sana. Pemeriksaan linear memiliki yang buruk kompleksitas pencarian jika ada banyak tabrakan.

2. Rantai

Masukkan string ke dalam slot sebagai daftar rantai (daftar tertaut). Jadi apabila terjadi tabrakan, kita hanya perlu beralih pada rantai itu.

5. Tree Concept

- Node di atas disebut sebagai root atau akar.

- Garis yang menghubungkan induk ke anak adalah edge atau garis.

- Node yang tidak memiliki anak disebut daun.

- Node memiliki orang tua yang sama disebut saudara.

- Derajat simpul adalah total sub pohon simpul.

- Tinggi atau kedalamanan tingkat maksimum node dalam pohon.

- Jika ada garis yang menghubungkan p ke q, maka p leluhurnya q, dan q adalah keturunan p.

6. Binary Tree Concept

Binary tree adalah structure data rooted tree dimana setiap node memiliki paling banyak 2 anak yaitu kanan dan kiri. Node yang tidak memiliki anak disebut daun. 

7. Type of Binary Tree

Ada 4 macam tipe:

1. Perfect Binary Tree

    Pohon biner dimana setiap level berada pada kedalaman yang sama.

2. Complete Binary Tree

    Pohon biner dimana setiap level, kecuali mungkin terakhir, terisi penuh, dan semua node sejauh mungkin dibiarkan.

3. Skewed Binary Tree

    Pohon biner dimana setiap node memiliki paling banyak satu anak.

4. Balance Binary Tree

    Pohon biner dimana tidak ada daun yang lebih jauh dari akar daripada daun lainnya.

8. Property of Binary Tree

- Maximum number of nodes on level k of a binary tree is 2k
- Maximum number of nodes on a binary tree of height h is 2h+1 - 1.
- Minimum height of a binary tree of n nodes is 2log(n).
- Maximum height of a binary tree of n nodes is n - 1.

9. Expression Tree Concept

1. Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung.

Contoh pemakaian prefix adalah  +AB, – +ABC, * + AB – CD.
2. Infix adalah cara penulisan ungkapan dengan meletakkan operator di antara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi.
Contoh pemakaian infix adalah A+B, A+B-C, (A+B)*(C-D).
3. Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung.

10. Threaded Binary Tree Concept 

Pohon biner berulir sama dengan pohon biner tetapi dengan perbedaan dalam menyimpan pointer NULL. Dalam representasi tertaut, sejumlah node berisi pointer NULL baik di bidang kanan atau kiri atau keduanya. Ruang yang terbuang untuk menyimpan tunjuk NULL ini dapat digunakan secara efisien untuk menyimpan kedamaian informasi bermanfaat lainnya.

Nama : Dewi Mutiara

NIM : 2301887830

Kelas besar : CB01

Kelas kecil : LK01