Binary Tree dan Hashing Table

Hashing Table

Hash atau Hashing berarti memenggal dan kemudian menggabungkan. Hash menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Hash merupakan suatu metode yang secara langsung mengakses record-record dalam suatu tabel dengan melakukan transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan  data dan penghapusan data dapat dilakukan dengan cepat.
Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Fungsi Hash adalah suatu fungsi yang mengubah key menjadi alamat dalam tabel. Fungsi Hash memetakan sebuah key ke suatu alamat dalam tabel. Idealnya, key-key yang berbeda seharusnya dipetakan ke alamat-alamat yang berbeda juga.

Hash table

Ada beberapa fungsi hash untuk mengubah string menjadi key:

•Mid-square

•Division (most common)

•Folding

•Digit Extraction

•Rotating Hash

Pada kenyataannya, tidak ada fungsi Hash yang sempurna. Kemungkinan besar yang terjadi adalah dua atau lebih key yang berbeda dipetakan ke alamat yang sama dalam tabel. Peristiwa ini disebut dengan collision (tabrakan). Karena itulah diperlukan langkah berikutnya, yaitu collision resolution (pemecahan tabrakan).

ada dua tipe Collision:

• Linear Probing: mencari spot/tempat kosong yang masih satu baris, lalu menaruh string di tempat kosong tersebut
• Chaining: menaruh string di slot yang telah disediakan di chained list (linked list)

IMPLEMENTASI HASHING TABLE PADA BLOCKCHAIN

Blockchain juga merupakan struktur data terdistribusi tetapi tujuannya sangat berbeda.

Anggap saja sebagai sejarah, atau buku besar. Tujuannya adalah untuk menyimpan daftar catatan yang terus tumbuh tanpa kemungkinan gangguan dan revisi.

Ini digunakan dalam sistem mata uang bitcoin untuk melacak transaksi. Properti ini menjadi bukti perusakan agar semua orang tahu saldo akun dengan mengetahui riwayat transaksinya.

Dalam blockchain, setiap node jaringan menyimpan data lengkap. Jadi sama sekali bukan ide yang sama dengan DHT (Distributed Hashing Table) di mana data dibagi di antara node. Setiap entri baru dalam blockchain harus divalidasi oleh proses yang disebut penambangan yang rinciannya di luar cakupan jawaban ini tetapi proses ini memastikan konsensus data.

Kedua struktur adalah struktur data terdistribusi tetapi melayani tujuan yang berbeda. DHT bertujuan untuk menyediakan struktur (dalam hal waktu pencarian dan penyimpanan jejak) yang efisien untuk membagi data pada jaringan dan blockchain bertujuan untuk menyediakan struktur data yang tahan-rusak.

Binary Tree

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). 

Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul).

Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap.

Konsep dalam tree:

- Binary tree adalah rooted tree yang yang setiap nodenya hanya memiliki maksimal 2 anak

- 2 anak tersebut disebut anak kiri dan anak kanan

- node yang tidak mempunyai anak disebut daun (leaf)

Tipe - tipe binary tree:

• Perfect Binary Tree : binary tree  yang setiap level (kedalaman) nya berada di kondisi  yang sama
• Complete Binary Tree : suatu pohon biner yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja).
• Skewed binary Tree : Suatu pohon biner yang setiap nodenya hanya memiliki 1 anak
• Balanced Binary Tree :   suatu pohon biner yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu.

Cara menghitung jumlah Node maksimal pada level yang sama = 2k  (k = jumlah level yang mau dicari)

Cara menghitung jumlah Node maksimal pada satu Binary tree = 2h+1 - 1 (h merupakan jumlah level yang ada)

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order.


Berikut rangkuman hashing table dan binary tree dan binary search yang saya cari melalui slide Binus dan internet. Sekian dan terimakasih.