Hash Table & Binary Tree

Hashing

Hashing adalah sebuah teknik yang digunakan untuk mengidentifikasikan sebuah objek spesifik dari sebuah kelompok dari objek yang serupa. Contoh penggunaan hashing dalam kehidupan nyata :

• Di perpustakaan, setiap buku diberikan sebuah nomor unik yang bisa digunakan untuk menentukan informasi tentang buku tersebut, seperti posisi pastinya di perpustakaan atau orang yang sedang meminjamkannya etc.

Hash Function

Sebuah hash function adalah sebuah fungsi yang bisa digunakan untuk memetakan sebuah data set dari ukuran yang berubah-ubah ke sebuah data set dari ukuran yang pasti, yang jatuh ke hash table. Nilai yang dikembalikan oleh sebuah hash function disebut hash values, hash codes, hash sums, atau hanya hashes.

Ciri-ciri hash function yang baik:

1. Mudah untuk memetakan data, harus mudah untuk dipetakan dan harus tidak menjadi algoritme sendiri.
2. Distribusi yang seragam, harus memberikan distribusi yang seragam terhadap hash table dan tidak menghasilkan pengelompokan.
3. Sedikit tabrakan, tabrakan terjadi ketika sepasang elemen dipetakan ke hash value yang sama

Hash Table

Hash Table adalah sebuah data structure yang digunakan untuk menyimpan informasi. Informasi tersebut memiliki dua komponen utama, yaitu Key dan Value. Hash table menggunakan hash function untuk mengcompute sebuah index ke dalam sebuah array di mana sebuah elemen akan dimasukkan atau dicarikan.

https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/

Blockchain

Blockchain adalah sebuah linked list yang mengandung data dan sebuah hash pointer yang menunjuk ke blok sebelumnya, sehingga menciptakan sebuah chain.  Hash pointer mirip dengan sebuah pointer, tetapi daripada hanya mengandung alamat dari blok sebelumnya, ia juga mengandung hash dari sebuah data dalam blok sebelumnya.

https://blockgeeks.com/guides/what-is-hashing/

Binary Tree

Sebuah binary tree adalah sebuah data structre yang hierarkis di mana setiap node memiliki paling banyak dua anak yang umumnya disebut dengan anak kiri dan anak kanan.’Setiap node mangandung tiga komponen:

1. Pointer ke subtree kiri
2. Pointer ke subtree kanan
3. Data elemen

Node yang terletak di paling atas tree disebut dengan root.

https://www.studytonight.com/data-structures/introduction-to-binary-trees

Terminologi Umum

• Root: Node  yang terletak di ujung atas tree
• Parent: Setiap node (kecuali sebuah root) dalam sebuah tree terhubung dengan sebuah directed edge tepat dari satu node lainnya. Node ini disebut sebagai parent.
• Child: Sebuah node yang terhubung langsung ke node lainnya ketika bergerak menjauhi root.
• Leaf/External node: Node tanpa anak.
• Internal node: Node dengan setidaknya satu children.
• Depth of a node: Banyaknya edges dari root ke node.
• Height of a node: Banyaknya edges dari node ke leaf paling dalam. Height dari tree adalah height dari root.

Tipe Binary Tree

• Rooted Binary Tree: Memiliki root node dan memiliki paling banyak dua child anak
• Full Binary Tree: Sebuah tree di mana setiap node memiliki antara 0 atau 2 anak
• Perfect Binary Tree: Sebuah binary tree di mana interior node memiliki dua anak dan leaves memiliki depth dan level yang sama
• Complete binary tree: Sebuah binary tree di mana setiap level, kecuali mungkin yang terakhir, diisi penuh, dan semua node berada di posisi paling kiri sebisa mungkin
• Balanced binary tree: Sebuah binary tree disebut height balanced apabila ia memenuhi batasan berikut:

1. Heights dari subtree kiri dan kanan berbeda paling banyak satu node
2. Subtree kiri seimbang
3. Subtree kanan seimbang

• Degenarate tree: Sebuah tree di mana setiap parent node hanya memiliki satu child node. Bekerja seperti sebuah linked list.