Hashing dan Hash Tables, Trees dan Binary Tree

HASH TABLE DAN BINARY

HASH TABLE

Sebuah tabel(array) dimana untuk menyimpan dan memetakan nilai kunci yang unik untuk setiap record(baris) menjadi angka(hash) lokasi record tersebut dalam sebuah tabel.

Banyak cara untuk hash sebuah string ke sebuah kunci. Beberapa metode penting untuk membentuk fungsi hash :

1. Mid-square

2. Division (most common)

3. Folding

4. Digit Extraction

5. Rotating Hash

•  Mid Square :

Teknik hashing dimana kunci unik dihasilkan. alam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. 

Rumusnya  : h(k) = s

k = key

s =  hash key yang diperoleh dengan memilih  r bits dari k2

•  Division  :

 Jumlah lokasi memori yang tersedia dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa(modulus). Sisa tersebut adalah nilai hashnya.

Rumusnya: h(z) = z mod M

z  = key

M = nilai untuk membagi kunci. biasanya menggunakan bilangan prima, ukuran tabel atau ukuran memori yang digunakan

•  Folding : 

Membagi-bagi string / identifier menjadi beberapa bagian, lalu menambahkan bagian tersebut dan mengambil beberapa angka terakhir sebagai nilai hashnya. 

• Digit Extraction  :

Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.
Metode ini mengubah urutan digit dengan pola tertentu. Contohnya mengambil digit ke tiga sampai ke enam dari nilai aslinya, kemudian membalikan urutannya dan menggunakan digit yang terurut terbalik itu sebagai nilai hash. 

•   Rotating Hash : 

 metode ini menggunakan berbagai macam metode seperti metode division atau mid-square. lalu terjadi rotasi setelah mendapatkan kode atau alamat hash melalui metode hash.

Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.contoh :

diberikan alamat hash 20021 maka hasil rotasi adalah 12002.

TREE & Binary Tree

Tree 

Struktur data non-linear yang mewakili hubungan hierarkis di antara objek data.

Tree adalah kumpulan dari satu atau lebih node.

Simpul yang berisi informasi yang nilainya lebih besar dari simpul atas atau yang disebut root akan ditempatkan sebagai cabang kanan, jika lebih kecil dari simpul atas akan ditempatkan seagai cabang kiri.

Tree terdiri dari akar atau root atau induk, yang berisi himpunan node dan garis berarah yang disebut branch yang menghubungkan dua node.

• Root

Jika suatu tree tidak kosong maka node yang pertama dan merupakan sebuah node unik disebut root.

• Leave atau daun

Merupakan node yang nilai outdegreenya 0, yaitu node yang tidak memiliki successor (sebuah node yang terjadi pada beberapa node).

Node terdiri dari dua yaitu:

-Node internal merupakan node yang bukan root atau leave

-Node eksternal.

• Parent / induk

Tree  disebut parent jika outdegreenya lebih dari 0.

• Child / anak 

Child merupakan bagian akhir dari tree.

• Ada 3 urutan dasar yang dapat digunakan untuk mengunjungi tiap tree(pohon), yaitu :

1. Pre-order : cetak isi node yang dikunjungi, kunjungi LEFT Child, kunjungi RIGHT Child.

2. In-order : kunjungi LEFT Child, cetak isi node yang dikunjungi, kunjungi RIGHT Child.

3. Post-order : kunjungi LEFT child, kunjungi RIGHT child, cetak isi node yang dikunjungi

Binary Tree

Pohon yang setiap simpul/nodenya paling banyak mempunyai dua buah sub-pohon. Binary tree dapat diimplementasikan dalam c/c++ dengan menggunakan double linkedlist.

Jenis- jenis Binary tree :

1. Perfect Binary Tree

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

 2.Complete Binary Tree

Jenis ini mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda dan setiap node kecuali leaf hanya boleh memiliki 2 child.

 

3. Skewed Binary Tree

Skewed Binary Tree adalah Binary Tree yang semua nodenya (kecuali leaf) hanya

memiliki satu child.

4. Balance Binary Tree

dimana memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).

 Expression Tree Concept

• Prefix 

Metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung. Contoh pemakaian prefix adalah  +AB, – +ABC, * + AB – CD.

• Infix 

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

• Postfix 

Metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung. Salah satu contoh proses pengubahan infix menjadi postfix dari karakter:

( A + B ) / (( C – D ) * E ^ F).

 

Referensi : 
https://www.academia.edu/25537608/TABEL_HASH_HASH_TABLE
http://chandra-mahardika.blogspot.com/2015/10/materi-prefix-infix-dan-postfix.html
http://t-edukasi.blogspot.com/2018/01/materi-dan-pengertian-jenis-jenis.html
https://herlinnairine.wordpress.com/2015/05/05/tree-dalam-pengantar-struktur-data/
http://syazdiayhodian.blogspot.com/2011/06/hashing.html