SUMMARY #2

SUMMARY

Bryan Darmawan Kartolo

2301863566 / CB-01

Dosen: Ferdinand Ariandy Luwinda (D4522) & Henry Chong (D4460)

Linked List

Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail. 

• Head adalah elemen yang berada pada posisi pertama dalam suatu linked list.
• Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list.

Adapun kelebihan dan kekurangan linked list, yaitu:

• Kelebihan:

1. Penambahan elemen tidak terbatas
2. Memungkinkan untuk dihapus

• Kekukarangan:

1. Hanya dapat diakses secara sekuensial
2. Memerlukan memori dalam jumlah yang besar, untuk menyimpan data yang besar juga.

Berikut beberapa macam Linked List:

1. Single Linked List
2. Double Linked List
3. Circular Linked List
4. Multiple Linked List 

SINGLE LINK LIST:

Single Linked List adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer. Rangkaian single linked list tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan di akhiri dengan node yang mengarah pointer ke null. Single Linked List hanya memiliki satu arah dan tidak memiliki dua arah atau bulak balik, dua arah tersebut disebut dengan double linked list.
Contoh:

Pada Implementasinya, Single Linked List terdapat dua variasi yaitu circular dan non-circular.

Contoh Non Circular:

 Contoh Circular:

Dalam pembelajaran struktur data, kita akan lebih sering mengenal dengan istilah :

• Push untuk menambah data.
  • PushHead – Menambah data ke barisan paling awal
  • PushTail – Menambah data ke barisan paling akhir
  • PushMid – Menambah data ke barisan di tengah (sorting)
• Pop untuk menghapus data.
  • PopHead – Menghapus data paling awal
  • PopTail – Menghapus data paling akhir
  • PopMid – Menghapus data ditengah (sesuai parameter value)

DOUBLE LINK LIST:
Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL. 
Contoh:

CIRCULAR LINKED LIST:
Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Terdapat 2 jenis circular linked list,yaitu:

• CIRCULAR SINGLE LINKED LIST 

 

• CIRCULAR DOUBLE LINKED LIST

MULTIPLE LINKED LIST:
Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer. 
Contoh:

Hashing Table dan Binary Tree

Sebenarnya apa itu hashing?

Hashing adalah metode untuk menyimpang data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat serta dengan constant average time.

Hash Table adalah 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 dari hash table antara lain sebagai berikut:

- Waktu aksesnya cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya.

- Hash table relatif lebih cepat.

- Kecepatan dalam insertions, deletions, maupun searching relatif sama. 

- Cocok untuk mempresentasikan data dengan frekuensi insert, delete dan search yang tinggi.  

Kekurangan dari hash table antara lain sebagai berikut:

- Seringkali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (berantakan).

- Sulit digunakan untuk mencetak seluruh elemen pada hash table.

- Tidak efisien untuk mencari elemen minimum ataupun maksimum.

Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value tersebut didapat hash value. Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data. Yang perlu diperhatikan untuk membuat hash function adalah:

1. ukuran array/table size(m), 

2. key value/nilai yang didapat dari data(k),

3. hash value/hash index/indeks yang dituju(h).

Terdapat beberapa cara untuk mengubah string menjadi kunci, yaitu:

• Division
• Mid-Square
• Folding
• Digit Extraction
• Rotating Hash

Division:

Membagi string/identifier dengan menggunakan operator modulus. Biasanya modulo nya berupa ukuran dari table/array atau menggunakan bilangan prima terdekat diatas banyaknya data.

contoh :
string "ABCD" akan distore di dalam hash table yang memiliki size 97
QWER: (81 + 87 + 69 + 82 ) = 319
Totalnya adalah 319 kemudian dimodulus 97.

319 % 97 = 28
jadi kunci dari string "QWER" adalah 28 kemudian string tersebut distore di dalam hash table yang berindeks 28.

Mid-Square:

Mengkuadratkan string/identifier, kemudian mengambil beberapa angka dari hasil kuadrat (dari tengah) untuk dijadikan hash key.

Folding:

Membagi string/identifier menjadi beberapa bagian, kemudian jumlahkan bagian-bagian tersebut untuk mendapatkan hash key.

Digit Extraction:

Mengambil bagian dari string/identifier yang diberikan.

Contoh: x = 14567, jika kita mengambil angka ke 1 dan 3, kita akan mendapatkan hash key 15.

Rotating Hash:

Yaitu dengan menggunakan metode hash seperti division atau mid-square. Kemudian balikkan hash code.

Contoh: x= 12345 dibalik menjadi 54321.


Binary Tree adalah pohon khusus dimana disetiap node atau vertex bisa tidak memiliki cabang atau juga bisa memiliki 1 atau 2 cabang dan setiap cabang bisa bercabang lagi dan memiliki sifat yang sama. Binary tree digunakan untuk mewakili struktur data nonlinear. Pohon biner memiliki peran penting dalam software application dan salah satu hal paling penting dari Binary Tree adalah searching dalam algoritma.

Terdapat banyak operasi pada binary tree seperti:
Create, Clear, Empty, Insert, Find, Update, Retrieve, DeleteSub, Characteristic, Traverse.

Binary Search Trees

Pohon cari biner adalah pohon biner yang dirancang untuk menskemakan urutan data yang akan dimasukkan ke dalam memori agar proses pencarian, penghapusan dan penambahan data dapat berjalan secara efisien dibanding dengan pemasukan data secara array maupun link.

Sifat dari skema pohon cari biner adalah : 

(1) setiap elemen yang berada di left substrees selalu lebih kecil dari elemen yang ada di right substrees.

(2) setiap elemen yang berada di right substrees selalu lebih besar atau sama dengan elemen yang berada di left substrees.

Contoh:

Ada 3 cara untuk melakukan penelusuran pada binary search trees, yaitu:

1. Pre Order: Print data, Telusur ke kiri, Telusur ke kanan.

2. In Order: Telusur ke kiri, Print Data, Telusur ke kanan.

3. Post Order: Telusur ke kiri, Telusur ke kanan, Print Data.

Balanced Binary Tree (AVL Tree)

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Gambar:

Cara menentukan height dan balance factor:

Height :
- Jika node (root) tidak memiliki subtree heightnya = 0
- Jika node adalah leaf, height =  1
- Jika internal node, maka height =  height tertinggi dari anak + 1

Balance Factor :
-selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.

AVL Tree Operations:

1. Insertion

AVL Tree mempunyai 2 proses balancing/insertion, yaitu:

- Single Rotation

Single rotation dilakukan apabila searah, left-left atau right-right

Karena sisi kiri 2 memiliki kedalaman 1, dan sisi kanan 2 memiliki kedalaman 3. maka selisih kedalamannya adalah 2, sehingga tidak balance. Dengan begitu, kita harus merotate sisi kanan seperti pada gambar diatas.

- Double Rotation

Double rotation dilakukan apabila searah, left-right atau right-left.

Karena memiliki sisi bengkok, maka proses balancing akan menggunakan double rotation seperti pada gambar diatas.

2. Deletion

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.

Jika 4 didelete, maka akan terjadi ketidakseimbangan di no 3. dengan begitu kita harus melakukan rotasi pada no 2, tetapi saat mengecek no 5 juga tidak seimbang. kita juga harus melakukan rotasi pada no 8, dan hasil akhirnya akan balance seperti pada gambar diatas.

Heap and Tries

Heap:

Adalah sebuah complete binary tree yang mempunyai heap properties.

Adapun jenis heap sebagai berikut:

1. Min Heap

Semua nilai node lebih kecil dari childnya. Sehingga dapat dikatakan root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node

• Insertion min heap dengan ketentuan insert node selalu berurutan dari level terendah dengan urutan left ke right, new node selalu menjadi leaf node, lalu kita sesuaikan dengan heap properties secara rekursif.
• Deletion min heap dengan ketentuan node yang dihapus selalu root karena merupakan node terkecil, lalu diganti dengan node terakhir yang diinsert, lalu sesuaikan lagi dengan heap properties secara rekursif.

2. Max Heap

Merupakan kebalikan dari min heap, yaitu dimana semua node nilainya lebih besar dari childnya.

• Insertion max heap hampir sama dengan min heap, tetapi hanya berbeda aturan. Aturannya yaitu nilai child< nilai parentnya.
• Deletion max heap dapat kita lakukan dengan menukar anak kiri atau kanan dari root dengan node terakhir dari heap lalu hapus. Lalu downheapmax dari node tersebut.

3. Min-Max Heap

Merupakan gabungan dari min dan max heap. Konsep Min Max Heap adalah level root akan bernilai minimum, selanjutnya akan bernilai maximum, dan seterusnya.

• Insert min-max heap dengan ketentuan insert node sesuai urutan lalu cek upheap dan sesuaikan dengan properties level. Biasanya dilakukan penyesuaian rekursif dengan urutan parent dulu lalu grand parent.
• Deletion min-max heap selalu dilakukan pada root lalu seusaikan dengan downheap sesuai properties. Biasanya dilakukan penyesuaian secara rekursif dengan urutan grand child(disesuaikan dengan parentnya) lalu child.

Tries:

Tries adalah prefix tree yaitu data tree yang terurut strukturnya untuk penyimpan suatu array. Berasal dari kata reTRIEval yang berarti untuk menyimpan asosiatif array dan jika dalam aplikasinya trie concept ini seperti auto-complete. biasanya tries dioperasikan pada pencarian browser, lalu spell checker pada digital dictionary.

Pada tries ini mengandung huruf:

bear, bell, bid, bull, buy, sell, stock, stop.

References:
http://suciantinovi.blogspot.com/2014/03/linked-list-i_14.html
https://medium.com/codelabs-unikom/struktur-data-single-linked-list-93bbd56b6ed1
https://www.academia.edu/32350910/MAKALAH_STRUKTUR_DATA_VARIASI_LINKED_LIST
https://www.academia.edu/25537608/TABEL_HASH_HASH_TABLE
https://informatika11d.wordpress.com/2012/11/22/struktur-data-hash-table/
https://www.slideshare.net/GRADhita/modul-praktikum-11-hashing-table 

https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/

https://saragusti22.wordpress.com/2015/05/04/pengantar-struktur-data-tree-dan-binary-tree/

http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html

http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html

https://www.geeksforgeeks.org/avl-tree-set-1-insertion/