Hashing Table & Binary Tree

Muhamad Rafif Hadi Kusmawan
2301913154
CD - 01

Hashing Table

Hashing Table adalah struktur data yang digunakan untuk menyimpan pasangan kunci / nilai. Ini menggunakan fungsi hash untuk menghitung indeks ke dalam array di mana elemen akan dimasukkan atau dicari. Dengan menggunakan fungsi hash yang baik, hashing dapat bekerja dengan baik. Di bawah asumsi yang masuk akal, waktu rata-rata yang diperlukan untuk mencari elemen dalam hash table.

dibawah ini ada beberapa fungsi hash untuk mengubah string menjadi key

1. Mid - Square

2. Division (most common)

3. Folding

4. Digit Extraction

5. Roating Hash

Fungsi hash adalah fungsi apa pun yang dapat digunakan untuk memetakan kumpulan data dari ukuran arbitrer ke kumpulan data dengan ukuran tetap, yang termasuk dalam tabel hash. Nilai yang dikembalikan oleh fungsi hash disebut hash value, hash codes, hash sums, or simple hahses.

Binary Tree

Binary Tree adalah structrur data tree di mana setiap node setiap node paling banyak memiliki 2 anak, yang disebut sebagai anak kiri dan anak kanan. Definisi rekursif hanya menggunakan teori himpunan gagasan adalah bahwa (non-kosong) pohon biner adalah tiga (L, S, R), di mana L dan R adalah pohon biner atau himpunan kosong dan S adalah satu set tunggal. Beberapa penulis memungkinkan pohon biner menjadi himpunan kosong juga.

dibawah ini ada beberapa jenis binary tree

1. Perfect Binary Tree: pohon biner yang setiap level (kedalaman) nya berada di kondisi yang sama.

2. Binary Tree Lengkap: satu pohon biner yang kedalamannya berjumlah n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama sekali, boleh saja tanpa atau tidak.

3. Pohon biner miring: Setiap pohon biner yang setiap nodenya hanya memiliki 1 anak.

4. Pohon Biner Seimbang: satu pohon biner yang tinggi di antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu.