HASHING Table

Hashing adalah proses menyimpan data sesuai dengan key nya.

Dalam hasing terdapat key dan data, sehingga disebut dengan Hash Table.

Untuk menentukan key, dapat menggunakan hash function.

Hash Function

Hash function dapat digunakan apabila suatu data tidak memiliki key, sehingga kita harus mencari key dari data tersebut.

• Proses Data dalam Hash Function

menggunakan hashing sesuai dengan fungsi dari datanya masing2.

Hash Function dapat berupa:

1. Mid Square

2. Division

mengubah/mengconvert data ke dalam ASCII lalu dimodulo.

3. Folding

Membagi data sesuai jumlah data angka. Setelah dibagi, lalu hasil dari pembagian tersebut akan dijumlahkan. Tahap terakhir adalah mengambil 2 digit terakhir dari hasil tersebut.

4. Rotating

membalik angka data nya. 

Misal: 1234 menjadi 4321.

5. Collision

Collision dipakai apabila ada data yang sama atau sama-sama bentrok.

Collision dapat di solusikan dengan 2 cara:

1. Linear Probling

Linear Probling dapat digunakan dengan menggunakan nomor array selanjutnya (kekurangan: data mjd berantakan, ketika di search tidak sesuai) jadi tidak disarankan untuk menggunakan operasi ini.

2. Chaining

Chaining mempunyai satu key, lalu masing-masing key menggunakan linked list yang tersambung satu sama lain sesuai dengan jumlah key. Dengan linked list pada chaining, maka data akan pushTail dan popMid. Karena kita harus tau data apa yang mau dihapus.

Binary Search Tree

Binary Search Tree adalah struktur data yang dibuat dengan tujuan untuk mempermudah dan mempercepat pencarian pada data.

• Tree

Di dalam tree terdapat sebuah node, edge, root, dan leaf. 

1. Node berupa bulatan yg berisi data.

2. Edge berupa garis yg menyambungkan masing2 node.

3. Root adalah akar yang hanya boleh satu dan menjadi titik tumpu dalam tree tersebut. Root selalu ada di paling atas.

4. Leaf: adalah node yg tidak memiliki cabang lagi dibawahnya.

Bentuk dalam tree:

1. Parent: orang tua yaitu node yang berada dari atas tree tersebut.

2. Children: anak yang berada di bawah node yang ditunjuk sebagai parents.

3. Grandparent: tingkat ketiga dari root atau node yang ditunjuk.

4. Decendants: keturunan.

5. Ancestor: leluhur.

6. Height: tingkat dari hitungan root. Root dimulai dari 1.

7. Level: sama seperti height tetapi root dihitung mulai dari 0.

• Binary Search Tree Concept

tree yg hanya boleh menampung dua children dari setiap node (max 2). 

kalau children nya lebih dari 2 maka itu bukan binary tree.

-Tree sebelah kiri lebih kecil dari root

-Tree sebelah kanan lebih besar dari root

Dengan tujuan untuk mempermudah pencarian. Jika node nya sama, maka tidak akan meminta inputan lagi sehingga bentrokan terhadap suatu node tidak akan terjadi.

1. PERFECT Binary Tree

adalah Binary Tree yang setiap nodenya benar-benar memiliki 2 children tanpa putus atau hilang 1 node pun.

Perfect Binary Tree pasti Complete.

2. COMPLETE Binary Tree

adalah Binary Tree yang setiap level harus penuh/perfect/lengkap dulu baru boleh turun ke level selanjutnya.

Setiap binary tree yang Complete belum tentu Perfect.

3. SKEWED Binary Tree

adalah Binary Tree yang setiap node hanya memiliki 1 children dan turun ke level selanjutnya.

Cara Menghitung Height maupun Level dari setiap Node

1. jumlah node maximum dari tiap level nya dapat dihitung dari 2^levelnya

2. jumlah node maximum dari tiap height nya dapat dihitung dari (2^height)-1

misal height dari 7= (2^7)-1

• Operation dalam BST

1. Operation: search

Operasi untuk mencari data.

Semua data dimulai dari root yang berada di paling atas.

2. Operation: insert

Operasi untuk menginput data.

Kalau inputannya lebih kecil, maka datanya akan masuk ke kiri. Kalau lebih besar, maka akan masuk ke kanan.

Cara Insert: node di kiri root pasti lebih kecil dari root, dan node yg disebelah kanan root pasti lebih besar dari root. Data selanjutnya akan mengecek terus bergantung dengan data yang berada di root.

Untuk BST, tidak boleh terdapat angka yg sama.

3. Operation: delete

Operasi untuk menghapus data.

Cara delete BST terdapat 3 kondisi:

1. Jika data yg mau di delete tidak mempunyai children/leaf sama sekali, maka dapat langsung delete.

2. Jika hanya punya 1 anak, maka anak tersebut akan menggantikan data itu sendiri atau parentnya.

3. Jika punya 2 anak, maka terdapat dua pilihan lagi:

a. anak kiri paling kanan

b. anak kanan paling kiri

Tujuan dihapus agar menghemat penyimpanan memori.

STACK AND QUEUE 

• Stack Concept

Teori Stack dapat di implementasikan ke dalam array dan link list. Namun, jika memakai array, data yang digunakan akan terbatas. Sedangkan apabila memakai link list, dapat menampung data sampai tak terhingga atau unlimited.

• Array Representation

Kelebihan: bisa di book terlebih dahulu.

Kelemahan: jika ingin book 9 data, maka hanya dapat menampung 9 data tersebut.

• Linked List Representation

Membuat link list lebih mudah dengan menggunakan array, karna dapat lebih dulu di booking dan di deklarasikan terlebih dahulu sehingga tidak ada data yang ganda atau sama.

• Stack operations

Stack: tumpukan

Queue: antrian

Terdapat 3 macam operasi pada Stack:

1. Push: menambahkan data yang paling atas

2. Pop: mengambil data dari paling atas

3. Top: mengembalikan data yang paling atas

• Prefix, Infix, dan Postfix

Kenapa harus belajar materi ini?

Karna pada masa dulu, komputer tidak bisa mendeteksi kurung kurawal. Sehingga kita harus mengubah kurung kurawal tersebut menjadi bentuk prefix, infix, maupun postfix.

Pada prefix, infix, dan postfix, terdapat yang namanya operator dan operan. Operan merupakan variabel yang dapat dihitung. Sedangkan operator adalah bentuk pengoperasi seperti '+', '-', '*', '/', dll.

1. Infix

Cth: 4 * 10

Operator selalu berada di tengah.

Infix: operan operator operan

2. Prefix

Cth: * 4 10

Operator selalu berada di depan.

Prefix: operator operan operan

3. Postfix

Cth : 4 10 *

Operator selalu berada di belakang.

Postfix: operan operan operator

Dari ketiga contoh diatas, dapat disimpulkan bahwa:

* adalah operator.

4 dan 10 adalah operan.

• Depth First Search (DFS)

Digunakan untuk mencari jarak terdekat dan tersimple.

• Queue

Sama seperti stack, terdapat 3 macam operation yang digunakan dalam queue.

3 macam operasi pada queue:

1. Push: memasukan item ke index yang berada di paling belakang yang belum terisi data (NULL).

2. Pop: menghilangkan data yang berada di paling depan.

3. Front: mengembalikan data ke index paling awal/depan.

• Deques

Dibaca "dek", singkatan dari Double Ended Queue.

Bisa memasukan data di sebelah kiri maupun kanan dan data yang sudah selesai akan ditarik ke bagian tengah.

Kelebihan : dapat mengetahui data mana yang lebih cepat

1. Input Restricted Dequeu

Input nya dibatasi hanya boleh satu

2. Output Restricted Deque

Inputnya unlimited tapi output nya satu

3. Priority Deque

Menghapus satu data agar dapat memprioritaskan data yang akan dikerjakan terlebih dahulu.

• Breadth First Search

Print secara berurutan (print in order). Jika di push ABCD maka akan di print ABCD. Dengan konsep siapa masuk duluan, maka akan keluar duluan atau First In First Out.

(2 Maret 2020)

Linked list and Double Linked List

Node merupakan komponen yang dapat berisikan sebuah data.

Node biasanya dihubungkan dengan garis yang disebut Linked List.

Linked List terbagi menjadi dua, Single Linked List dan Double Link List.

1. Single Linked List, hanya dapat memberikan satu arahan kepada komponen/node yang berada di sebelah kanannya.

2. Double Linked List, dapat memberikan arahan kepada 2 arah kepada setiap node yang berada di sebelah kanan maupun kirinya.

Circular Single Linked List (Linked List)

Hanya terdiri dari satu arah tanpa adanya feedback dari setiap komponen.

Pokok dari sebuah data berada di head.

Doubly Single Linked List

Memiliki dua arah dan saling terhubung satu sama lain. Kalau di hubungkan, maka akan menguhubungkan kembali para komponen yang ada dan terjadi feedback.

Doubly Linked List: insert

Dilakukan apabila ingin menambahkan data baru di belakang. Cara kerja nya sama seperti doubly linked list biasa.

Doubly Linked List: delete

Caranya adalah melepaskan tail dan head terhadap node, lalu membuat node dengan jumlah yg sangat banyak sebagai perbandingan, lalu membuat pernyataan sebanyak node nya.