NIM: 2301894331
Nama: Irvan Djanitra
Dosen : Henry Chong (D4460) - Ferdinand Ariandy Luwinda (D4522)
Kelas : CB01
LINKED LIST
Linked list berarti :
- Koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer.
- 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 :
- Single Linked List
- 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
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
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.
Linear Probing (saat menggunakan array)
Mencari indeks lain yang kosong setelah indeks tersebut, sehingga data dapat dimasukkan.
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:
- 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.
- Jika leftchildren > data dan rightchildren < data maka swap data dengan LC.
- Jika leftchildren < data dan rightchildren > data maka swap data dengan RC.
Lakukan ke bawah berulang kali sampai leftchildren dan rightchildren < data.
Untuk min heap:
- 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.
- Jika leftchildren < data dan rightchildren > data maka swap data dengan LC.
- Jika leftchildren > data dan rightchildren < data maka swap data dengan RC.
Lakukan ke bawah berulang kali sampai leftchildren dan rightchildren > data.
Contoh:
