Hash Table and Binary Tree

Hash Table

Hashing

Hashing adalah transformasi aritmatik sebuah string atau karakter menjadi nilai yang merepresentasikan string aslinya.           

Hashing digunakan sebagai metode untuk menyimpan data di dalam sebuah array agar penyimpanan, penambahan, dan pencarian data dapat dilakukan dengan benar.     

Hash Table

Hash table adalah table (array) dimana kita menyimpan suatu string asli, dimana index dari array adalah suatu kunci yang dienkripsi (hashed key ), namun nilainya adalah string yang asli.

Ukuran dari hash table biasanya terdiri dari berbagai macam urutan, namun biasanya lebih sedikit dari berbagai kemungkinan string. Jadi, beberapa string kemungkinan mempunyai hashed key yang sama.

Hash Function

Hashing adalah salah satu bagian penting dari data structure dimana didesain oleh suatu fungsi yang dinamakan hash function yang digunakan untuk memetakan suatu nilai dengan suatu ciri yang spesifik untuk akses elemen yang lebih cepat.

Misalkan untuk fungsi H(x) akan memetakan nilai x yang disimpan di

index x%10, maka data {11,13,15,17,19 } akan disimpan secara berturut-turut akan disimpan di index { 1,3,5,7,9 } di dalam array.

Beberapa metode untuk membuat Hash Function :

Ø Mid – Square

Ø Division

Ø Folding

Ø Digit Extraction

Ø Rotating Hash

Mid-Square

Function: h(k) = s

k  = key

s  = hash key yang diperoleh dari nilai tengah kuadrat k

·        kuadratkan string/identifier (k), lalu kita ambil angka tengah dari kuadrat string/identifier untuk dijadikan hash key (s)

Division

Function: h(z) = z mod M

z  = key

M = angka yang digunakan untuk membagi key

·        ketika ingin memunculkan index dan meletakkan key di index hasil function division

Folding

·       bagi key menjadi beberapa bagian

·       jumlahkan bagian individualnya

Digit Extraction

·       beberapa bagian digit dari key akan dijadikan hash address

·        contoh :

x = 12350. Jika kita mengambil angka ke 1, 2, dan 4, maka kita akan mendapatkan hashcode : 125.

Rotating Hash

·       gunakan metode apa saja, lalu urutan angka akan dibalik ( misalkan division atau mid-square )

·       setelah mendapatkan hash code dari hash method, lakukan rotation

·       rotation adalah dijalankan dengan menggeser digit untuk mendapatkan hash address yang baru.

·       contoh :

hash address awal = 27201

hasil rotation = 10272

Collision

·       ketika kita ingin menyimpan string menggunakan hash function sebelumnya ( menggunakan karakter pertama dari setiap string )

·       misalkan kita ingin mendeklarasikan tipe data float, exp, char, atan, ceil, acos, floor

·       maka kita akan menemukan kesamaan di tipe data float dan floor, serta tipe data char dan ceil. Ini terjadi karena kedua pasang tipe data memiliki awalan karakter yang sama, sehingga mempunyai hash key yang sama.

·       disinilah terjadi collision

Ada dua solusi umum untuk mengatasi collision :

1.   Linear Probing

mencari tempat selanjutnya yang kosong dan meletakkan string di tempat tersebut

2.   Chaining

meletakkan string sebagai linked list

Trees and Binary Tree

Tree Introduction

·        Tree adalah non-linear data structure yang merepresentasikan relasi antara objek atau data

·        Beberapa tree bisa dilihat di dalam directory structure ataupun organizational hierarchies

·        Node dari tree harus disimpan terus menerus dan bisa disimpan dimana saja, serta dihubungkan oleh pointer

 

DEGREE of TREE = 3

DEGREE of C = 2

HEIGHT = 3

PARENT of C = A

CHILDREN of  A = B, C, D

SIBILING of F = G

ANCESTOR of F = A, C

DESCENDANT of C = F, G

Tree Concept

·        node di posisi paling atas disebut root

·        garis yang menghubungkan parent dan child disebut edge

·        node yang tidak mempunyai children disebut leaf

·        node yang mempunyai parent yang sama disebut sibling

·        degree adalah total sub tree dari sebuah node ( jumlah descendant )

·        height / depth adalah degree maksimum dari sebuah node di dalam tree

·        jika ada garis yang menghubungkan p dengan q, maka p disebut ancestor dari q, serta q disebut descendant dari p

Binary Tree Concept

·       binary tree adalah tree di dalam data structure yang mempunyai paling banyak dua children

·       kedua children tersebut biasa disebut left child dan right child

·       node yang tidak mempunyai children disebut leaf

Types of Binary Tree

·        Perfect Binary Tree adalah binary tree dengan level yang berjumlah sama dengan height/depth

·        Complete Binary Tree adalah binary tree dengan level yang berjumlah sama dengan height/depth, namun hampir terisi sempurna

·        Skewed Binary Tree adalah binary tree yang setiap nodenya mempunyai paling banyak satu child

·        Balanced Binary Tree adalah binary tree dimana tidak ada leaf yang garisnya lebih Panjang dari leaf lainnya

Property of Binary Tree

·     maksimum jumlah node dari level k adalah

·        beberapa sumber menyebutkan bahwa level dari binary tree dimulai dari 1 (root)

·       height dari sebuah tree adalah total dari level diluar dari root

·       gambar di atas memiliki height sebanyak 3 ( dimana level 0 tidak dihitung karena mengandung root )

·     height minimum dari binary tree dengan n node adalah

·       height maksimum dari binary tree dengan n node adalah n-1

·        Skewed Binary Tree memiliki height yang maksimum

(dengan node minimum, bisa membuat height yang maksimum)

Representation of Binary Tree

o   Implementasi dengan array

-      Index di array menunjukkan nomor node

-      Index 0 adalah node root

-      Index left child adalah 2p + 1, dimana p adalah parent index

-      Index right child adalah 2p + 2

-      Index parent adalah ( p – 1 ) / 2

o   Implementasi dengan linked list

Expression Tree Concept

Threaded Binary Tree

Threaded Binary Tree adalah binary tree yang memiliki cara menunjuk pointer NULL yang berbeda dengan binary tree