Hashing and Hash Tables, Trees & Binary Tree (L)

Session 05

Hasing 

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

Hash Table

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. Kelebihan menggunakan hash table adalah hash table relatif lebih cepat, kecepatan dalam insertsion,deletions relatif sama.

Pada saat kita ingin membuat hash table function ada beberapa hal yang perlu kita perhatikan yaitu  ukuran array / table size, key value/nilai yang di dapat dari data(k) , hash value/hash index/indeks yang dituju(h).

Contoh - contoh hash function :

1.Mid-square

2.Division (most common)

3.Folding

4.Digit Extraction

5.Hashing Rotation

1.Mid square

mencari sebuah value dengan cara mengkuadratkan dan kemudian menggunakan jumlah bit yang sesuai dari kotak tengah untuk mendapatkan kunci hash

step :

1.Kuadratkan nilai dari kuncinya (k^2)

2.Meng-extract r bit yang berada di tengah dari hasil yang diperoleh pada langkah pertama

function : h(k) = s

k = key

s = hash key yang diperoleh dengan memilih r bit dari k^2

Contoh mid square

2.Division

Mencari sebuah value menggunakan operator modulus(%). Cara ini adalah cara tersimple untuk menemukan sebuah value dalam hash table.

function : h(z) = z mod M

z = key

m = nilai yang digunakan untuk membagi kunci, biasanya menggunakan bilangan prime, besar dari tabel / besar dari memori yang digunakan.

Contoh division

3.Folding

 Metode ini membagi nilai asli ke dalam beberapa bagian, kemudian menambahkan nilai-nilai tersebut, dan mengambil beberapa angka terakhir sebagai nilai hashnya.

step :

1.membagi nilai kunci menjadi beberapa bagian

2.tambahkan bagian-bagiannya

4.Digit Extraction

Metode ini menggunakan cara digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.

contoh : Misal x = 15,980

jika kita mengekstrak digit 1,2,5 maka kita dapat mendapatkan hash code : 150.

5.Rotation hash

Metode ini menggunakan cara merotasi digit 

contoh : alamat hash = 25291

hasil rotasi = 19252

Collision 

Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.

Collision(tabrakan pada hash function) bisa saja terjadi, ada dua cara untuk permasalah tersebut yaitu,  Linear Probing dan Chaining

1. Linear Probing

Dengan menambahkan suatu interval pada hasil yang diperoleh dari fungsi hash sampai ditemukan lokasi yang belum terisi. Interval yang biasa digunakan adalah 

2.Chaining

Metode rantai bisa juga digunakan untuk menyelesaikan tabrakan pada hash function, setiap data yang di dalam array sebenarnya terhubung secara single linked list yang berpasangan.

Tree

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lain

Konsep tree

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

istilah-istilah dalam tree :

a.)Root = node yang berada paling atas

b.)Edge = garis yang menghubungkan node

c.)Leaf = node-node yang tidak memilik daun

d.)Degree of node = degree suatu node adalah total subtree

e.)Sibling = node yang mempunyai parent sama

f.)Ancestor = Seluruh node yang terletak sebelum node tertentu dan

terletak pada jalur yang sama. 

g.)Descendant = Seluruh node yang terletak sesudah node tertentu

dan terletak pada jalur yang sama. 

Binary Tree

Binary tree adalah suatu tree yang selalu mempunyai 2 anak, biasanya ada di kiri dan kanan.Binary tree mempunyai beberapa tipe yaitu, perfect binary tree, balance binary tree, skewed binary tree, dan balance binary tree.

A. Perfect binary tree

Binary tree yang mempunyai kedalaman sama di bagian kiri dan kanan

B.Complete binary tree

Complete binary tree adalah 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). Dan dalam penempatan simpulnya diutamakan yang sebelah kiri yang terpenuhi.

C.Skewed binary tree

Skewed binary tree adalah binary tree yang mempunyai node paling banyak satu, sehingga membuatnya tidak seimbang

D.Balanced Binary Tree

Balanced binary tree adalah suatu pohon biner yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu

Data Structures Session 4

Stack & Queue

1. Stack 
Stack atau tumpukan adalah suatu kumpulan elemen dimana elemen yang baru dimasukkan yang dapat diakses. Sebuah stack biasa di implementasikan menggunakan array atau bisa juga dengan linked list. Sebuah stack biasa menggunakan prinsip Last In First Out (LIFO), yang artinya masuk terakhir pertama. Contoh penerapan prinsip LIFO adalah sebuah kumpulan tumpukan buku yang baru saja dimasukkan ke dalam toko dengan jenis buku yang sama, pasti buku yang paling atas yang terjual terlebih dahulu.

Adapun pemanfaatan stack adalah untuk perhitungan ekspresi aritmetika(postfix),algoritma Backtracking(runut balik) dan algoritma rekursif.

Operasi-Operasi dalam Stack
1.Push : Menambahkan sebuah data baru
2.Pop : Menghapus sebuah data
3.Top : Mengambil data yang paling atas

2.Queue

Queue atau antrian merupakan struktur data linear dimana penambahan komponen dilakukan disatu ujung, sementara pengurangan dilakukan diujung lain. Queue sendiri menggunakan prinsip First In First Out (FIFO), yang artinya masuk pertama keluar pertama. Contoh penerapan FIFO di dalam kehidupan sehari-hari adalah antrian di dalam sebuah bank, yang setiap datang nasabah diwajibkan mengambil nomor antrian, dan yang datang lebih dahulu pastilah akan di panggil duluan  oleh teller bank

Operasi-Operasi dalam Queue

1.Fungsi insert atau Enqueue digunakan untuk memasukkan sebuah data atau sebuah nilai ke dalam queue

2.Fungsi delete atau Dequeue digunakan untuk mengapus sebuah data di dalam queue.

Circular Queue

Jika kita menggunakan array untuk queue seperti di atas, maka ketika ada proses pengambilan (dequeue) ada proses pergeseran data. Proses pergeseran data ini pasti memerlukan waktu apalagi jika elemen queue-nya banyak. Oleh karena itu solusi agar proses pergeseran dihilangkan adalah dengan metode circular array

Perbedaan antara Stack dan Queue

sumber : http://www.differencebetween.net/technology/difference-between-stack-and-queue/

Infix, Postfix, and Prefix Notation

Terdapat 2 istilah dalam notasi Infix, Postfix, Prefix

1.Operator : Tanda operasi ('+', '-', '/', '*', '%')

2.Operand : Nilai asal yang digunakan dalam operasi contohnya angka 1-10 dst.

Hal yang penting saat menggunakan notasi ini adalah komputer akan lebih cepat mengeksekusi program, dan lebih mengehemat penggunaan memori komputer.

Infix, Postfix, Prefix 

Keterangan : Opd --> Operand 

                      Opr --> Operator

1.Infiix  : operator ditulis diantara operand --> (opd opr opd)

Contoh :  10  + 3 * 4

2.Postfix : operator ditulis setelah operand --> (opr opr opd)

Contoh :  10 3 4 * +

3.Prefix : operand ditulis sebelum operator-->(opd opr opr)

Contoh : + 10 * 3 4

Contoh lain 

Infix : ((1 + 3) / (100 * 5) ^ 30)

Prefix : / + 1 3 ^ * 100 5 30

Postfix : 1 3 + 100 5 * 30 ^ / 

Breadth First Search and Depth First Search 

1. Breadth First Search 

Metode pencari BFS adalah salah satu metode pencarian yang sederhana, dimana pencarian dimulai dari titik awal, kemudian dilanjutkan ke semua cabang titik tersebut secara berurutan. Jika titik yang dituju belum ditemukan, maka akan ada perulangan ke masing-masing titik cabang dari masing-masing titik, sampai titik tujuan ditemukan.

Source : binusmaya.binus.ac.id

 Visit order : A, B, C, D, E

Untuk kelanjutannya, ada di link dibawah ini : 

http://michaeljulius11.blogspot.com/2017/10/pengertian-metode-pencarian-bfs-dan-dfs.html

2.Depth First Search 

Algoritma ini mirip dengan Algoritma BFS (Breadth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma BFS (Breadth First Search) melakukan perhitungan secara terurut dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama.

visit order : A, C, B, E, D.

Untuk kelanjutannya ada di link dibawah ini 

https://saungkode.wordpress.com/2014/04/16/penelusuran-pohon-biner-berdasarkan-kedalaman-dengan-algoritma-dfs-stack-dan-secara-melebar-level-order-dengan-algoritma-bfs-queue-dan-implementasinya-dalam-bahasa-c/

Pointer
Pada materi single linked list dan double linked list hal yang sangat penting adalah pointer. Definsi pointer adalah suatu variabel yang berisi suatu alamat lokasi tertentu.Fungsi pointer adalah sebagai penunjuk alamat lokasi variabel lain. Berikut adalah potongan source code untuk penggunaan pointer sederhana.

1.Single Linked List
Linked list adalah suatu koneksi linear dari data, atau yang lebih umum dikenal sebagai nodes. Dimana setiap node menunjuk node yang lainnya melalui sebuah pointer. Pada umumnya sebuah rangkaian single linked list maupun double linked list diawali dengan head dan diakhiri dengan node yang mengarah ke pointer NULL.

Representasi single linked list dapat dilihat pada gambar di bawah ini : 

Pada gambar diatas angka 10 adalah sebagai Head, sesusai dengan definisi head yaitu elemen yang berada pada posisi pertama dalam linked list. Sedangkan 30 adalah sebagai Tail yaitu elemen yang berada pada posisi terakhir.

Operasi-Operasi di Single Linked List

1.Insert 

Fungsi ini adalah menambahkan sebuah simpul yang baru ke dalam sebuah linked list

2.Konstrukor 

Fungsi ini membuat linked list yang baru dan tidak berisi apapun(kosong)

3.isEmpty

Fungsi ini adalah untuk mengecek isi dari linked list, apakah kosong atau tidak.

4.FindFirst

Fungsi ini digunakan untuk mencari elemen pertama dalam sebuah linked list

5.FindNext

Fungsi ini digunakan untuk mencari elemen yang ditunjuk oleh pointer

6.Retrive
Fungsinya digunakan untuk mengamnil elemen yang ditunjuk, dan dikembalikan ke dalam function

7.Update 

Fungsinya mengubah elemen yang ada di dalam linked list atau bisa saja kita sebut mereplace

8.Delete Now
Fungsinya adalah untuk menghapus elemen yang terdapat dalam linked list.

Circular Single Linked List

Circular single linked list adalah single linked list yang pointer nextnya menunjuk pada dirinya sendiri, jikalau di single linked list di elemen terakhir(tail) akan ada pointer next yang menunjuk NULL, tapi jika circular single linked list jikalau sudah di elemen terakhir, dia akan kembali ke dirinya sendiri sehingga berputar,oleh sebab itu disebut circular

Representasi circular single linked list dapat dilihat pada gambar di bawah ini : 

2.Double Linked List

Berbeda dengan single linked list dan circular single linked list yang hanya memiliki 1 pointer saja sedangkan double linked list adalah salah satu contoh implementasi linked list dan single linked list, berdasarkan namanya yaitu double, artinya di linked list ini mempunyai 2 penunjuk yaitu kiri dan kanan. Pada umumnya kanan adalah sebagai next dan penunjuk kiri sebagai prev. 

Representasi sebuah double linked list dapat dilihat pada gambar di bawah ini : 

Operasi-Operasi di Double Linked List

1.Insert Tail 

Fungsinya adalah  menambahkan sebuah simpul baru di belakang(bagian kanan) dalam sebuah linked list

2.Insert Head

Fungsinya adalah menambahkan sebuah simpul baru di depan(bagian kiri) dalam sebuah linked list

3.Delete Tail

Fungsinya adalah menghapus simpul dari yang paling belakang(kanan), berkebalikan dengan fungsi Insert tail

4.Delete Head

Fungsinya adalah menghapus simpul dari yang paling depan(kiri), yang berkebalikan dengan fungsi insert head

Circular Double Linked List

Circular double linked list memiliki 3 field yaitu :

1.Pointer berikutnya(next)

2.Pointer sebelumnya(prev)

3.Berisi data untuk node

Double Linked List Circular pointer next dan prev nya menunjuk ke dirinya sendiri secara circular.

Representasi sebuah circular double linked list dapat dilihat pada gambar di bawah ini :