Review

Linked List

Linked List biasa kita gunakan untuk mempermudah insertion data pada database..Serta tidak membuang-buang memory, karena menggunakan malloc yang disebut juga memory allocation sesuai dengan memory yang dibutuhkan.
 
Jangan lupa untuk menggunakan library stdlib yaa...
karena ada penggunaan malloc..
selain stdlib bisa juga menggunakan library malloc
yaitu : #include<malloc.h>

Push adalah function untuk insertion data
Pop adalah function untuk deletion data
Printall adalah function untuk view data  

Stack & Queue

Stack artinya tumpukan, yang berarti data linked list yang dibuat harus sesuai dengan definisi stack, yaitu last in first out, layaknya tumpukan balok, kita menyusun dari bawah ke atas, namun saat menarik balok kita mulai dari bagian atas, ini lah mengapa stack di sebut LIFO (Last In First Out).

Queue artinya antrian, yang berarti data linked list yang dibuat harus sesuai dengan definisi queue, yaitu first in first out, layaknya antrian tiket bioskop, orang yang terdepan dan sudah membayar akan keluar dari antrian, ini lah mengapa queue disebut FIFO (First In First Out).

Apakah kodingan berbeda ?? jelas beda...
untuk stack, yang digunakan adalah function push tail dan pop tail.
untuk queue, yang digunakan adalah function push tail dan pop head.

Notes:
- Push = menambahkan data
- Pop = menghapus data

Hashing & Binary Tree

Hashing adalah transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau kunci yang mewakili string asli. penggunaannya seperti memberikan indeks ke dalam database.

Ada beberapa jenis teknik hashing:

- Mid Square

ini adalah teknik pengambilan indeks melalui angka tertentu pada value.
cth:

data 1 - 2132411

maka mid part yang diambil adalah 324

data 2 - 7657876

maka mid part yang diambil adalah 578

- Division

ini adalah teknik pengambilan indeks melalui value yang di modulus dengan angka yg sudah ditentukan.

sebagai contohnya, saya mengambil indeks A-Z yang bertotal ASCII sampai 90.
cth: kata yang saya gunakan "ABE"

kita hitung value menggunakan ASCII :
A = 65
B = 66
E = 69
(65+66+69) % 90 = 20

maka akan disimpan di indeks 20

- Folding

ini adalah teknik yang membagi setiap string menjadi beberapa bagian

cth: angka 3241 dalam hash table yang disediakan sebanyak 100

dibagi menjadi 32 dan 41
kemudian ditambahkan dan hasilnya adalah 73

- Digit Extraction

ini adalah teknik dengan mengambil beberapa bagian dari angkanya

cth: 12345
ambil digit 1, 3, dan 5
sehingga hash code yang didapat adalah 135

- Rotating Hash

ini adalah teknik yang dilakukan setelah memiliki hash code dengan cara-cara diatas kemudian di rotasi

cth: hash code = 12345
rotated menjadi = 54321

Binary Tree, berarti sebuah tree yang memiliki 2 anak yaitu anak kiri dan anak kanan, berbeda dengan single linked list karena menunjukkan ke 1 data berikutnya, klo binary tree menunjuk ke 2 data selanjutnya.

Binary Searh Tree

BST (Binary Search Tree) adalah Tree yang bisa mempercepat pencarian, sorting data dengan tepat, memiliki kemudahan entri data dana penghapusan data. BST adalah binary tree namun memiliki kemampuan auto sorting.

BST pada anak kiri memiliki nilai yang lebih kecil daripada parentnya dan pada anak kanan memiliki nilai yang lebih besar dari parentnya.

1. Searching
Pencarian data mudah karena hanya perlu membandingkan data dengan root terlebih dahulu, jika lebih kecil maka akan lanjut pencarian ke kiri, dan apabila lebih besar dari root, maka melakukan pencarian ke kanan.

2. Insertion
Memulai memasukkan data dari root terlebih dahulu, apabila kosong maka data pertama akan menjadi root. dan sama halnya apabila data selanjutnya lebih kecil dari root maka data baru akan dibuat di sebelah kiri root, dan apabila data selanjutnya lebih besar dari root maka data baru akan dibuat di sebelah kanan root. Lakukan terus sampai menemukan node kosong yang bisa ditimpa dengan data baru.

3. Deletion
Jika data terdapat pada ujung tree (leaf), maka langsung hapus saja. Apabila memiliki 1 anak, tinggal sambungkan ke parent si data yang akan dihapus. Jika memiliki 2 anak, carilah data yang tepat untuk menggantikan data yang akan di delete, bagaiman mendapatkannya ? yaitu dengan melakukan pencarian data dari bagian kiri root lalu ke kanan sampai ditemukan data paling ujung (predecessor) atau bisa juga dengan melakukan pencarian data dari bagian kanan root lalu ke kiri sampai ditemukan data yang paling ujung (successor) kemudian replace data yang akan dihapus dengan data tersebut.

Namun dari semua advantage yang dimiliki BST, ada bagian dimana BST bisa menjadi tree yang sama saja seperti linkedlist biasa, misalkan akan mengisi data 1,2,3,4,5. apabila data pertama yang masuk 1 maka root = 1, dan 2,3,4,5 akan berada di bagian kanan dari root. Tidak ada bedanya dengan LinkedList, padahal tujuan dari BST sendiri agar mempermudah pencarian data. Nah hal ini disebut dengan Skewed Tree (kekanan terus / kekiri terus).

Sekian review materi dari
- Linked List
- Stack & Queue
- Hashing & Binary Tree
- Binary Search Tree