Summary Akhir

Stefanus Likardi
2301882306

Kelas: CB01

Lecturer:  Ferdinand  Ariandy Luwinda (D4522 ) dan Henry Chong ( D4460 )

LINKED LIST

Jadi pada pertemuan kelas besar Data Structure hari ini membahas tentang "Linked List II(bagian 2)" yang dimana dibagi atas:

1.  Doubly Linked List.
2. Circular Single Linked List.
3. Circular Doubly Linked List.

Doubly Linked List

Double Linked List adalah linked list dengan node yang memiliki data dan dua buah arah pointer biasanya disebut next dan prev yang menunjuk ke node sebelum dan node sesudahnya. Sehingga bisa dikakses di next atau prev sebuah node.

Pada dasarnya Doubly Linked List hampir mirip dengan single linked list hanya saja, penghubung antar node terdapat 2 penghubung yaitu next dan juga prev. Dalam Doubly Linked List, prev dari head akan bernilai NULL dan juga nilai next dari tail juga bernilai NULL.

Operasinya pun sama dengan Single Linked List , yaitu:

1. Push

Operasi ini digunakan untuk memasukkan node baru pada sebuah linked list. Pada fungsi push terbagi 2 yaitu,

• Push Depan(Head)

Pada push depan nilai node akan dimasukkan di bagian depan setiap kali fungsi ini dijalankan. Contoh: Push Depan 1,2,3,4 akan menghasilkan 4,3,2,1.

• Push Belakang(Tail)

Pada push belakang nilai node akan dimasukkan di bagian belakang setiap kali fungsi dijalankan.

Contoh: Push Belakang 1,2,3,4 akan menghasilkan 1,2,3,4.

2. Pop
Operasi ini digunakan untuk menghilangkan(menghapus) node pada sebuah linked list. Fungsi Pop juga terbagi 2, yaitu PopDepan dan PopBelakang yang membedakan hanya darimana node itu dihapus dari depan/belakang.

Circular Single Linked List

Berbeda dengan yang sebelumnya Circular Single Linked List adalah Linked List yang Node terakhirnya tersambung dengan node pertamanya, sehingga seperti membentuk sebuah siklus searah.

Contoh seperti berikut:

Dimana setelah node Z akan terhubung ke node P.

Circular Doubly Linked List

Pada Circular Doubly, hampir sama dengan Single namun pada setiap node terdapat pointer next dan prev. Pada akhir node akan terhubung dengan node awal, begitu juga dengan node awal yang akan terhubung dengan node terakhir. Sehingga membentuk siklus bolak-balik.

Contoh seperti berikut:

Hashing and Hash Table

Jadi pada materi hari ini dibahas tentang hashing dan juga hash table.

Jadi apa itu hashing? Hashing menurut yang saya pelajari adalah sebuah function yang dimana untuk meng-sort suatu data sehingga untuk mempermudah pencarian data pada index tertentu. Hashing dan juga hash table berkaitan erat dengan array dan juga linked list.

Contoh coding hashing:

#define size 95

int hash(char nama[]){

int jmlASCII = 0;

int len = strlen(nama);

for(int i = 0; i < len; i++){

jmlASCII = jmlASCII + nama[i];

}

int key = jmlASCII % size;

return index;

}

Jadi pada coding ini, kita akan meng-input sebuah nama dan function ini akan dijalankan.

Misal hash("stefanus"), maka akan mengreturn index sebesar 18 karena jmlASCII "stefanus" % size(sudah di define sebesar 95) = 873 % 95 = 18.

Index inilah yang akan dipakai untuk mempermudah pencarian sebuah data atau menyimpan sebuah data.

Lalu untuk hashTable menurut pengertian saya adalah hasil simpanan data dari function hash kita tadi, setelah kita hash hasil index nama-nama tadi akan kita sort dengan penerapan linked list. Jadi ketika datanya ingin dicari akan lebih cepat dan efisien.

Binary Search Tree

Dimulai dari binary tree, apa itu binary tree? Binary tree adalah sekumpulan data diilustrasikan berbentuk akar pohon. Contohnya seperti berikut,

Binary tree selalu dimulai dari root/ bisa dibilang kepala dari binary tree yaitu dari ilustrasi angka 1.

Setiap angka memiliki 2 cabang, 1 cabang, bahkan tidak memiliki cabang (tergantung angka yang diinput). Angka yang lebih kecil selalu berada di bagian kiri dan yang besar berada di bagian kanan.

Dalam BST terdapat beberapa function yang dapat digunakan seperti insertion, deletion, dan print sama seperti linked list dan lain-lain.

Deklarasi awal masih sama dengan linked list:
#include<stdio.h>
#include<stdlib.h>
struct Data{
int nilai;
Data *left , *right; (bedanya disini left dan right, mirip dengan next dan prev)
}*root = NULL; ( kita declare root awal NULL karena belum ada data yang masuk)

Insertion:
struct Data* insertNilai(struct Data *curr,int nilai) ,(menggunakan struct karena akan mengreturn struct)
{
if(curr == NULL)
{
struct Data *temp = (struct Data*)malloc(sizeof(struct Data));
temp->nilai = nilai;
temp->left = temp->right = NULL;
curr = temp;
}
else
{
if(curr->nilai > nilai)
{
curr->left = insertNilai(curr->left,nilai);
}
else
{
curr->right = insertNilai(curr->right,nilai);
}
}
return curr;
}

AVL Tree

Pada materi kali ini kita akan membahas AVL Tree, pada dasarnya Avl Tree ini mirip dengan BST(Binary Search Tree) hanya saja pada AVL Tree kita perlu menyeimbangkan cabang setiap nodenya.

Pada AVL, perbedaan kedalaman cabang kiri dan kanannya tidak boleh lebih dari 1. Selama dibawah 2 masih diperbolehkan.

Contoh:

Tree diatas bukan merupakan AVL Tree, dikarenakan node 12 kiri dan kanan perbedaannya lebih dari 1. Pada cabang kiri 12 kedalamannya adalah 4, sedangkan yang kanan hanya 2. Perbedaannya yaitu 4-2 = 2 (lebih dari 1).

Contoh pada AVL Tree kali ini, node yang menjadi masalah adalah node 10. Karena setelah dimasukkan angka 3 otomatis cabang kiri dari node 10 akan menjadi lebih berat. Oleh karena itulah dilakukan rotation ke kanan agar cabang kiri dan kanannya seimbang kembali.

Pada gambar ini node 30 lah yang menjadi permasalahan karena cabang kanannya lebih berat, sehingga dilakukan rotation ke kiri seperti digambar.

Heap & Tries

Heap adalah sebuah tree yang dimana inputannya berurut sesuai array. Pada dasarnya konsep heap memakai konsep tree, namun dalam heap memiliki beberapa jenis yaitu:

1. Min Heap
2. Max Heap
3. Min-Max Heap

Min Heap

Mengapa disebut min heap? Dikarenakan parent pada heap memiliki nilai yang lebih kecil daripada childrennya. Kita lihat contohnya sebagai berikut:

Array : 1,2,3,17,19,36,7,25,100

Bentuk tree seperti ini karena insert dalam heap diurutkan dari kiri ke kanan, dan pada heap tidak ada array[0] hal itu dilakukan untuk mempermudah proses insert node.

Untuk mencari parent/children dari sebuah node bisa digunakan rumus berikut:

Mencari Parent : idxNode/2

Mencari children left : idxNode*2

Mencari children right : (idxNode*2)+1

Sebagai contoh kita ambil node '2' yang memiliki index 2

Parent Node 2 : 2/2 = 1 (index ke -1, yaitu node 1)

Children Left : 2*2 = 4 (index ke - 4 , yaitu node 17)

Children Right : 2*2 + 1 = 5 (index ke - 5 , yaitu node 19)

Ketika insertion, node baru yang dimasukkan ternyata lebih kecil dari parentnya maka akan dibandingkan antara node baru dengan parent jika node baru lebih kecil akan ditukar.

Contoh jika kita input angka baru yaitu angka 4. Node ini akan tersambung sebagai children left dari angka 19, dan karena angka 4 ini lebih kecil dari parentnya yaitu 19, maka angka 4 ditukar dengan angka 19. Lalu dilihat lagi apakah angka 4 lebih kecil dari angka 2, ternyata tidak jadi tidak perlu ditukar. 

Lalu untuk delete, misalkan kita ingin delete node 2. Selalu diambil array terakhir sebagai pengganti, yang disini adalah node 100.

Kita bandingkan dengan tiap children dari node 100 yaitu 17 dan 19 manakah yang lebih kecil. 17 lebih kecil jadi kita tukar 100 dengan 17. 

Kita bandingkan lagi dengan childrennya yaitu 25. 25 lebih kecil dari 100 sehingga ditukar lagi.

Max Heap

Sama dengan min heap kali ini node parent harus memiliki nilai yang lebih besar daripada childrennya.

Contoh :

Array : 90,89,70,36,75,63,65,21,18,15

Konsep Insert dan deletenya pun sama dengan Min Heap. Yang berbeda pada insert dilihat apakah children lebih besar dari parentnya, jika iya aka di swap. 

Min Max Heap

Lalu yang terakhir ada min max heap. Heap ini merupaka campuran dari min dan juga max heap karena pada heap ini memiliki level-level seperti berikut.

Pada level genap terdapat nilai minimum dan pada level ganjil terdapat nilai maximum. Setiap insert dilakukan kita harus cek parentnya terdapat pada level apa jika parentnya min, makan node baru kita harus lebih besar dari parent dan sebaliknya.

Tries

Tries bentuknya juga memakai konsep tree, namun pada tries hanya menyimpan sebuah karakter dan biasanya digunakan untuk auto-complete kata-kata.

Contoh bentuk Tries:

                       root
                    /   \    \
                    t   a     b
                    |   |     |
                    h   n     y
                    |   |  \  |
                    e   s  y  e
                 /  |   |
                 i  r   w
                 |  |   |
                 r  e   e
                        |
                        r

Dimulai dari root bisa membentuk berbagai kata sesuai alur tree yang ada.

Seperti "answer","any","bye","there","their".

RBT

Red Black Tree (RBT) konsepnya sama dengan binary search tree, namun ada beberapa kondisi yang harus diperhatikan  ketika menginsert/mendelete nodenya.

Setiap insertion baru, node selalu diwarnai merah kecuali root.

Ketika parent bewarna hitam tidak terjadi violation, namun jika parent bewarna merah terjadi violation.

Sebagai contoh node baru yaitu X(Kiri) dan Z(Kanan) kita ubah parent dan uncle menjadi warna hitam dan grandparent diubah menjadi merah.

Dalam case ini terjadi violation, dan dilakukan single rotation (bisa juga double rotation). Yang menjadi pivot diubah warnanya menjadi hitam dan childrennya warna merah.

Ketika mendelete, kita harus memperhatikan beberapa ketentuan seperti berikut:

•Perform similar DELETION process in BST

•Either choose RIGHT-MOST of LEFT CHILD or LEFT-MOST of RIGHT CHILD ( Successor / Predeccessor)

1) NODE-TO-DELETE : RED - NO VIOLATION

2) NODE-TO-DELETE : BLACK

  - DELETE the NODE

  - Mark the location as DOUBLEBLACK

  1) SIBLING : RED

  - Change PARENT to RED

  - Change SIBLING to BLACK

  - Rotate at X  -> RECHECK DOUBLEBLACK

  2) SIBLING : BLACK

  1) BOTH CHILD : BLACK

  - Change SIBLING to RED

  - Move DOUBLEBLACK to PARENT  -> RECHECK DOUBLEBLACK

  2) One of the CHILD : RED

  - SINGLE/DOUBLE ROTATION

  - Change CHILD to BLACK  -> REMOVE DOUBLEBLACK

B-TREE

Yang saya pelajari kali ini yaitu 2-3 Tree atau biasa disebut B-Tree orde 3. Disebut Orde 3 karena maksimal dari nodenya hanya bisa menampung maksimal 2 key. Begitu mencapai 3 key dia akan memecah.

Contoh kita akan insert 75 pada tree ini.

Nodenya akan terpecah karena ketika kita input 75 akan terjadi violation dimana key sudah mencapai maximum dari ordenya yaitu 3.

Sehingga nilai tengahnya kita naikan ke parent yaitu 80

75 dan 90 Di-split.

Intinya selama masih memenuhi batas minimal  dan maksimal node, lakukan insert biasa seperti BST.

GRAPH

Graph yang telah saya pelajari ada 3, Minimum spanning tree ada 2 cara sedangkan shortest path 1 cara.

MST

Cara Prim dan Kruskal

Dimulai dari Prim, kita ambil contoh graph diatas mencari MST dari graph tersebut. Cara prim yaitu kita mengurutkan Adjacency List nya sesuai abjad/nomor. Jadi kita mulai A, kita cari semua degree yang berhubungan dengan A.

Di bagian PQ kita sort sesuai value, dan ketika kita mengambil MSTnya tidak boleh membentuk graph tertutup. Sehingga kita dapatkan MST seperti diatas.

Kruskal

Karena sama-sama MST hasilnya akan sama hanya saja cara pengerjaannya sedikit berbeda.

Bedanya pada kruskal kita langsung sort di bagian Adjacency Listnya, dan langsung dimasukkan ke T. Sehingga didapatkan hasil sama seperti Prim.

Dikjstra

Lalu pada Dikjstra, kita diharuskan mencari jarak terpendek untuk mencapai tujuan tertentu

pada graph ini kita diharuskan mencari shortest path dari A-F. Tidak harus menyentuh semua nodenya.

Didapatkan 3 cara shortest path dengan nilai minimum yang sama yaitu 4.