Hashing Table & Binary Tree

Kemarin kita sudah membahas mengenai Stack & Queue. Hari ini saya akan membahas mengenai hashing table dan binary tree.

Binary Tree
adalah data struktur berpohon di mana setiap simpul memiliki paling banyak 2 anak, yang disebut kiri dan kanan. Binary tree diimplementasikan terutama menggunakan link. Sebuah Tree diwakili oleh pointer ke simpul paling atas di Tree. Jika Tree tersebut kosong, maka nilai sebuah Root kosong. Binary Tree terdapat beberapa node seperti :

1. Data
2. Pointer ke anak kiri
3. Pointer ke anak kanan

Binary Tree dapat dilalui dengan 2 cara. Yang pertama adalah Depth First Traversal dan yang kedua adalah Breadth First Traversal. Depth First Traversal terdiri dari :

• Inorder (Kiri-Root-Kanan)
• Preorder (Root-Kiri-Kanan) 
• Postorder (Kiri-Kanan-Root).

Breadth First Traversal terdiri dari : Level order Traversal.

Properti dari Binary Tree :

• Angka maksimum node ada di level '1' = 2^1-1.
• Angka maksimum node adalah = 2^{h + 1} - 1. h adalah tinggi sebuah Tree.
• Ketinggian minimum adalah = Ceil(Log₂(n+1)) – 1.
• Di dalam binary tree, jumlah node leaf selalu lebih banyak 1 dari node 2 anak.
• Kompleksitas Waktu Traversal Tree : 0(n).

Salah satu alasan menggunakan Binary Tree atau Tree adalah untuk hal-hal yang membentuk hierarki. Mereka sangat berguna dalam struktur File dimana setiap file terletak di direktori tertentu dan ada hierarki spesifik yang terkait dengan file dan direktori.

Binary Heap

adalah Binary Tree dengan :

1. Isi pohon lengkap (semua level terisi penuh kecuali mungkin level terakhir dan level terakhir memiliki semua kunci yang tersisa) Properti Binary Heap ini membuatnya cocok untuk disimpan dalam array.
2. Binary Heap adalah Min Heap atau Max Heap. dalam Min Binary Heap, kunci pada root harus minimum di antara semua kunci yang ada di Binary Heap.Properti yang sama harus benar secara rekursif untuk semua node di Binary Tree. Max Binary Heap mirip dengan Min Heap. Max Binary Heap diimplementasikan menggunakan array.

• Dapatkan Minimum di Min Heap: O (1) [Atau Dapatkan Max di Max Heap]
• Ekstrak Minimum Min Heap: O (Log n) [Atau Ekstrak Max di Max Heap]
• Kurangi Kunci di Tumpukan Min: O (Log n) [Atau Kurangi Kunci di Tumpukan Max]
• Sisipkan: O (Log n)
• Hapus: O (Log n)

Struktur data Heap dapat digunakan untuk secara efisien menemukan elemen k terkecil (atau terbesar) dalam sebuah array, menggabungkan array yang diurutkan k, median aliran, dll.

Heap adalah struktur data khusus dan tidak dapat digunakan untuk mencari elemen tertentu.

Hashing Hash Function

Suatu fungsi yang mengubah kunci input besar yang diberikan ke nilai integer praktis kecil. Nilai integer yang dipetakan digunakan sebagai indeks dalam hash table. Fungsi hash yang baik harus memiliki properti berikut :

1. Dihitung secara efisien.
2. Sebaiknya mendistribusikan kunci secara seragam (Setiap posisi meja memiliki kemungkinan yang sama untuk setiap kunci)

Hash Table: Array yang menyimpan pointer ke catatan yang sesuai dengan nomor telepon tertentu. Entri dalam hash table adalah NIL jika tidak ada nomor telepon yang memiliki nilai fungsi hash sama dengan indeks untuk entri.

Collision Handling: Karena fungsi hash memberi kita sejumlah kecil untuk kunci yang merupakan bilangan bulat besar atau string, ada kemungkinan bahwa dua kunci menghasilkan nilai yang sama. Situasi di mana peta kunci yang baru dimasukkan ke slot yang sudah ditempati di hash table disebut tabrakan dan harus ditangani menggunakan beberapa teknik penanganan tabrakan. Berikut ini adalah cara untuk menangani tabrakan:

1. Chaining --> Idenya adalah untuk membuat setiap sel tabel hash menunjuk ke daftar catatan terkait yang memiliki nilai fungsi hash yang sama. Rantai itu sederhana, tetapi membutuhkan memori tambahan di luar meja.
2. Open Addressing --> Dalam pengalamatan terbuka, semua elemen disimpan dalam hash table itu sendiri. Setiap entri tabel berisi catatan atau NIL. Saat mencari elemen, kita satu per satu memeriksa slot tabel hingga elemen yang diinginkan ditemukan atau jelas bahwa elemen tersebut tidak ada dalam tabel.

Hashing Data Structure

Hashing adalah Struktur Data penting yang dirancang untuk menggunakan fungsi khusus yang disebut fungsi Hash yang digunakan untuk memetakan nilai yang diberikan dengan kunci tertentu untuk akses elemen yang lebih cepat. Efisiensi pemetaan tergantung pada efisiensi fungsi hash yang digunakan.

Biarkan fungsi hash H (x) memetakan nilai x pada indeks x% 10 dalam sebuah array. Sebagai contoh jika daftar nilai adalah [11,12,13,14,15] itu akan disimpan di posisi {1,2,3,4,5} masing-masing dalam array atau tabel hash.

Sumber :

1. https://www.geeksforgeeks.org/overview-of-data-structures-set-2-binary-tree-bst-heap-and-hash/

2. https://www.geeksforgeeks.org/hashing-data-structure/