Data Structure Semester 2 Final Summary

NIM: 2301894331
Nama: Irvan Djanitra
Dosen : Henry Chong (D4460) - Ferdinand Ariandy Luwinda (D4522)
Kelas : CB01




LINKED LIST

Linked list berarti : 

1. Koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer.
2. Kumpulan nodes yang merepresentasikan sebuah sequence.

Linked list memungkinkan melakukan insertion(pushDepan,pushBelakang) dan deletion(popDepan,popBelakang) kepada semua element di lokasi manapun. Linked list ini digunakan saat jumlah element tidak dapat diprediksi.
Terdiri dari 2 jenis :

1. Single Linked List
2. Double Linked List

Single Linked List

Sebuah linked list yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan metode linked list, suatu daftar isi yang saling berhubungan.

Double Linked List

Linked list dengan dua buah link, satu yang berisi reference ke data berikutnya dan satu yang berisi reference ke data sebelumnya.

*Note

Circular linked list : linked list yang node terakhirnya mengandung pointer ke node pertama. Untuk double linked list selain node terakhirnya memiliki pointer ke node pertama, node pertama juga memiliki pointer ke node terakhir.

Intinya dalam membuat linked list head harus berada di paling depan, tail harus berada dipaling belakang dan harus selalu terhubung dan tidak boleh putus. 

*next = menyimpan alamat dari struct berikutnya(sehingga saling terhubung)

Fungsi insert untuk memasukkan data baru

Pushdepan = data terbaru dihubungkan pada tail dan tail digeser ke data terbaru

 

Pushmiddle = data terbaru diletakan ditengah-tengah data yang sudah ada

 

Pushbelakang = data terbaru dihubungkan pada head dan head digeser ke data terbaru

 

Fungsi delete untuk menghapus data sehingga memory dapat dipakai kembali(saat penghapusan isi alamat dari struct yang telah dihapus masih ada dan akan hilang jika ada data baru yang menggunakan memory tersebut)

Sebelum menghapus kita perlu menyelamatkan head dan tail terlebih dahulu agar masih tetap terhubung

Popdepan = data yang dihapus data terakhir(posisi tail)


Popmid = menghapus suatu data tertentu ditengah


Popbelakang = data yang dihapus data pertama(posisi head)

Berbeda dengan single link list, double link list selain mempunyai *next juga mempunyai *prev yang menyimpan alamat dari struct sebelumnya sehingga dalam double link list memungkinkan untuk kembali pada struct sebelumnya secara langsung tanpa perlu mencarinya dari head 

Circular link list = link list yang tail→next=head

Source Code

Membuat struct dan node

Contoh push tail

Contoh pop head

HASHING & HASH TABLE
Hashing adalah suatu cara atau fungsi untuk men-store data ke dalam sebuah array.

Hash table terdiri dari indeks & value

Hash Function


Mid-Square = Input akan dipangkatkan dengan 2, lalu diambil bagian tengahnya (middle part)



Division = Menggunakan z % M dimana z adalah input dan M adalah table size.



Folding = Memisahkan input per 2 angka, lalu menjumlahkannya.




Digit Extraction = Menentukan sendiri digit angka yang akan diambil.

Misalkan digit pertama dari belakang




Rotating Hash = Me-reverse input untuk dijadikan key.

Collision = kondisi dimana key atau indeks yang dihasilkan oleh hash function sudah terisi oleh data lain sehingga akan terjadi tabrakan saat ingin memasukkan data yang tersebut.

Cara mengatasinya:

Linear Probing (saat menggunakan array)

Mencari indeks lain yang kosong setelah indeks tersebut, sehingga data dapat dimasukkan.

Chaining (menggunakan linked list)
Data sesuai hasil keynya *next nya menunjuk pada data yang baru. Dengan kata lain data yang baru dipushmid setelah data yang sesuai keynya.

TREE & BINARY TREE

Pada sebuah tree :

• Node paling atas disebut root (Node A).
• Ada parent dan children.
• Node yang tidak memiliki children disebut leaf.
• Node yang parentnya sama disebut sibling.

Binary tree = tree yang hanya memiliki 2 children, disebut left children dan right children.

Binary tree memiliki beberapa type antara lain :

-Perfect

-Complete 

-Skewed

Implementasi binary tree:

⇒Menggunakan array

-0 adalah indeks root.

-Misal p adalah indeks yang diketahui maka indeks parent = (p-1)/2, indeks anak kiri = 2p+1, dan indeks anak kanan = 2p+2.

⇒Menggunakan linked list

Expression tree

Cara membacanya:

• Infix = left children – parent – right children
• Postfix = left children – right children – parent
• Prefix = parent – left children – right children

BINARY SEARCH TREE

Binary Search Tree (BST) adalah Sistem yang mendukung pencarian (searching) dan pengurutan (sorting) secara cepat.

Push

Pada saat push pada BST newnode akan dibandingkan dengan suatu node x yang sudah ada. Jika newnode < x, maka nownode diletakkan disebelah kiri. Jika newnode > x, maka nownode diletakkan disebelah kanan.

Deletion

Saat deletion terdapat beberapa kasus:

➤Node yang dihapus adalah leaf

Hapus curr.

➤Node yang dihapus memiliki 1 anak

Hubungkan parent dengan children lalu hapus curr.

➤Node memiliki 2 anak, ada 2 pilihan, cari anak paling kanan dari left subtree atau anak paling kiri dari right subtree untuk menggantikan posisi yang didelete.

AVL

AVL Tree adalah binary tree yang memenuhi syarat minimal height atau ketinggian dari jumlah node yang ada. AVL Tree merupakan salah satu dari Balanced Search Tree.

Balanced Search Tree digunakan agar binary tree memiliki height terkecil sehingga bisa mempertahankan complexity-nya O(log n) dimana n adalah jumlah node.

Dalam AVL Tree terdapat yang namanya balance factor yang nantinya akan digunakan untuk menentukan perlu atau tidaknya rebalancing dilakukan. Balance factor (bf) dihitung dengan mengurangkan tinggi dari anak kiri dengan tinggi dari anak kanan.

Rebalancing dilakukan ketika pada suatu node terjadi violated, dimana bf (balance factor) bernilai lebih dari 1 atau kurang dari -1. 

Dapat dilihat dari contoh diatas, dengan adanya AVL Tree maka tinggi dari sebuah tree dapat diminimalisir. Pada awalnya tinggi tree tersebut 4 lalu berubah menjadi 3 jika dijadikan AVL tree, sehingga jika melakukan pencarian pada suatu node hanya perlu maksimal 3 step yang sebelumnya maksimal 4 step. 

HEAP
Heap adalah salah satu bentuk binary tree.
Heap terdiri dari 2 jenis yaitu:

 1. Max Heap
  Heap yang rootnya adalah data yang paling maksimum.
          

2. Min Heap

Heap yang rootnya adalah data yang paling minimum.

Insert pada heap dilakukan dengan meletakkan data tempat terakhir sesuai complete binary tree. Lalu selanjutnya akan dibandingkan dengan parentnya. 

Untuk max heap, swap dilakukan saat newdata>parent. Ini akan dilakukan terus menerus keatas sampai newdata<parent. 

Untuk min heap, swap dilakukan saat newdata<parent. Ini akan dilakukan terus menerus keatas sampai newdata>parent.

Contoh:

Delete pada heap hanya dapat dilakukan pada root. Setelah dihapus kemudian root akan digantikan dengan data terakhir sesuai complete binary tree. 

Untuk max heap:

1. Jika leftchildren dan rightchildren > data maka bandingkan LC dengan RC, jika LC > RC maka swap data dengan LC, jika LC < RC maka swap data dengan RC.
2. Jika leftchildren > data dan rightchildren < data maka swap data dengan LC.
3. Jika leftchildren < data dan rightchildren > data maka swap data dengan RC.

Lakukan ke bawah berulang kali sampai leftchildren dan rightchildren < data.

Untuk min heap:

1. Jika leftchildren dan rightchildren < data maka bandingkan LC dengan RC, jika LC < RC maka swap data dengan LC, jika LC > RC maka swap data dengan RC.
2. Jika leftchildren < data dan rightchildren > data maka swap data dengan LC.
3. Jika leftchildren > data dan rightchildren < data maka swap data dengan RC.

Lakukan ke bawah berulang kali sampai leftchildren dan rightchildren > data.

Contoh: