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

Heaps & Tries

Heaps adalah Binary Tree yang terdiri dari 2 anak seperti layaknya BST namun memiliki 2 konsep yaitu :
- Max Heap
- Min Heap

Max Heap artinya nilai parent lebih besar dibandingkan dengan anaknya

Min Heap artinya nilai parent lebih kecil dibandingkan dengan anaknya

Heaps biasanya diimplementasikan di Array

seperti pada gambar dibawah ini:


Seperti pada gambar, heaps index dimulai dari 1 karena untuk mempermudah melakukan perhitungan sebuah lokasi nodenya

ini adalah rumus indexnya
Parent = x/2
L-Child = 2*x
R-Child = 2*x+1

untuk pencarian data terkecil di Min Heap sudah pasti terletak pada root
untuk pencarian data terbesar di Max Heap sudah pasti terletak pada root

Insertion
Min Heap : apabila pada tree di insert nilai yang kecil dibandingkan dengan parentnya, otomatis akan melakukan penukaran nilai child dengan parentnya, hal ini dilakukan secara terus menerus sampai bertemu parent yang nilainya lebih kecil dibandingkan yang di insert.

Max Heap : apabila pada tree di insert nilai yang besar dibandingkan dengan parentnya, otomatis akan melakukan penukaran nilai child dengan parentnya, hal ini dilakukan secara terus menerus sampai bertemu parent yang nilainya lebih besar dibandingkan yang di insert.

Mix Max Heap : Karena setiap level berbeda beda jenis heap, misalkan pada level 0 itu Min Heap, maka level 1 itu Max Heap, selanjutnya akan ditentukan dengan ganjil genap levelnya. bagaimana insertionnya ? sama seperti Min Heap dan Max Heap hanya saja terdapat perbedaan saat melakukan proses koding atau algorithmnya yaitu setiap mau mengecek antara nilai child dan parentnya, harus memperhatikan levelnya setiap bertemu level genap maka akan melakukan pengecekan insert Min Heap, dan jika bertemu level ganjil akan melakukan pengecekan insert Max Heap.

Deletion
Min Heap : saat mendelete akan mengambil element terakhir pada tree untuk menggantikan posisinya, lalu melakukan downheapmin yang berarti melakukan pengecekan ke anaknya apakah ada nilai yang lebih kecil dari nilai anaknya.

Max Heap : saat mendelete akan mengambil element terakhir pada tree untuk menggantikan posisinya, lalu melakukan downheapmax yang berarti melakukan pengecekan ke anaknya apakah ada nilai yang lebih besar dari nilai anaknya.

Min Max Heap :  saat mendelete akan mengambil element terakhir pada tree untuk menggantikan posisinya, lalu melakukan downheapmax/downheap min tergantung pada level berapa yang di delete.

Heap Complexity :
- Searching : O(1)
- Insert : O(log(n))
- Delete : O(log(n))

Applications of Heaps :
- Heap Sort
- Selection Algorithms
- Graph Algoriths

Tries, adalah tree yang setiap nodenya terdapat sebuah huruf, rootnya berisikan empty character


Gambar diatas adalah contoh dari Tries

Sekian penjelasan singkat tentang Heaps dan Tries.

Binary Search 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 pembahasan teori mengenai BST, jika ada yang mau ditanyakan seputar BST, silahkan comment.
Thank you~

AVL Tree

Balanced Binary Tree

Balanced Binary Tree adalah Tree yang memiliki minimal ketinggian root ke leaf-nya pada BST agar mencegah terjadinya kegagalan tree yaitu, skewed BST (yang datanya kekanan semua atau kekiri semua)

AVL Tree

Dinamakan berdasarkan 2 penemunya yaitu Adelson-Veleskii dan E.M. Landis

1. Menentukan Height:
- Height dari tree yang kosong adalah 0.
- Height dari sebuah node tanpa anak adalah 1.
- Height ditentukan dari height anaknya tertinggi (antara anak kiri dan anak kanan) lalu +1.

2. Menentukan Balanced factor:
- Dengan mencari perbandingan height anak kiri dan kanan (height anak kiri - height anak kanan atau sebaliknya).
- Dan disebut balance apabila nilainya tidak lebih dari 1 dan tidak kurang dari -1.

3. Insertion
- Insertnya seperti BST pada umumnya yaitu insert jika ada head dia akan mengecek apakah lebih kecil atau lebih besar dari head ? bila lebih kecil ke kiri dan apa bila lebih besar ke kanan.
- Namun ada yang membedakan yaitu harus disertakan rebalance

berikut beberapa case rebalance :
Misal A adalah node yang harus di rebalance.
Case 1 : node yang akan dimasukkan terletak di subtree kiri dari anak kiri si A.
Case 2 : node yang akan dimasukkan terletak di subtree kanan dari anak kanan si A.
Case 3 : node yang akan dimasukkan terletak di subtree kanan dari anak kiri si A.
Case 4 : node yang akan dimasukkan terletak di subtree kiri dari anak kanan si A.

Rotasi yang dilakukan saat rebalance :
- Single Rotation:
LL rotation: bentuk ke kiri dari root dan salahnya pada anak kirinya.
RR rotation: bentuk ke kanan dari root dan salahnya pada anak kanannya.
-Double Rotation:
LR rotation: bentuk ke kanan dari root dan salahnya pada anak kirinya.
RL rotation: bentuk ke kiri dari root dan salahnya pada anak kanannya.

4. Deletion
- Deletion di AVL tree seperti deletion BST yang mengambil antara successornya atau predecessornya
- Namun ada tambahan lagi bagi AVL karena setelah melakukan deletion ada kemungkinan bahwa treenya menjadi tidak balance lagi, maka dari itu kita haru melakukan rebalance kembali setelah melakukan deletion.

Sekian dari saya tentang materi AVL tree, jika ada yang mau ditanyakan silahkan comment.