Nama: Diovinsen Yeodyra
NIM: 230187781
Kelas: CB01-CL
Hari: Selasa, 9 Juni 2020
Lecturer:
Ferdinand Ariandy Luwinda (D4522) , Henry Chong (D4460)
Linked list
Linked list adalah salah satu bentuk struktur data yang berisi kumpulan data yang tersusun secara sekuensial, saling berhubungan dan juga dinamis. suatu linked list dapat diartikan juga sebagaia suatu simpul/ node yang dikaitkan dengan simpul lain dalam suatu urutan tertentu dan dimana simpul dapat berbentuk struktur atau class dan mempunyai satu atau lebih dari elemen struktur atau class.Jenis jenis linked list
Linked list dibagi menjadi 3, yaitu:
- Circular Single Linked List
- Doubly Linked List
- Circular Doubly Linked List
Circular single linked list
Single Linked List merupakan suatu linked list yang hanya memiliki satu variable pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menujuk ke NULL. Tetapi untuk Circular Single Linked List ada pointer dari tail menuju ke head, sehingga tidak ada pointer yang menujuj ke NULL.
contoh:
Double Linked List
Double Linked List merupakan suatu linked list yang memiliki dua variable 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 Doubly Linked List
Dan untuk yang terakhir adalah Circular Doubly Linked List, yaitu linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berikutnya( next), 1 field menunjuk pointer sebelumnnya(prev), serta sebuah field yang berisi data untuk node tersebut. Double Linked List Circular pinter next dan prev nya menunjuk ke dirinya sendiri secara circular.
contoh:
Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.
Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).
Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.
operasi yang terdapat pada hash table adalah
1. insert : diberikan sebuah key dan nilai, insert nilai pada table
2. find : diberikan sebuah key, temukan nilai yang berhubungan dengan key
3. remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
4. getIterator : mengambalikan iterator,yang memeriksa nilai satu demi satucode untuk insert:
int hashtbl_insert(HASHTBL *hashtbl, const char *key, void
*data)
{
struct hashnode_s *node;
hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;
Penambahan elemen baru dengan teknik pencarian menggunakan linked lists
untuk mengetahui ada tidaknya data dengan key yang sama yang
sebelumnya sudah dimasukkan, menggunakan deklarasi berikut:
node=hashtbl->nodes[hash];
while(node) {
if(!strcmp(node->key, key)) {
node->data=data;
return 0;
}
node=node->next;
}
code untuk find:
void *hashtbl_get(HASHTBL *hashtbl, const char *key)
{
struct hashnode_s *node;
hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;
node=hashtbl->nodes[hash];
while(node) {
if(!strcmp(node->key, key)) return node->data;
node=node->next;
}
return NULL;
}
code untuk remove:
int hashtbl_remove(HASHTBL *hashtbl, const char *key)
{
struct hashnode_s *node, *prevnode=NULL;
hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;
node=hashtbl->nodes[hash];
while(node) {
if(!strcmp(node->key, key)) {
free(node->key);
if(prevnode) prevnode->next=node->next;
else hashtbl->nodes[hash]=node->next;
free(node);
return 0;
}
prevnode=node;
node=node->next;
}
return -1;
}
Hashing benar-benar mendasar dalam penciptaan teknologi blockchain. Jika seseorang ingin memahami apa itu blockchain, mereka pasti harus mengerti apa artinya hashing.
BINARY TREE
Pohon (Tree) adalah graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf terhubung maka pada pohon selalu terdapat path atau jalur yang menghubungkan kedua simpul di dalam pohon. Pohon dilengkapi dengan Root (akar).
Pohon binar (binary tree) adalah himpunan simpul yang terdiri dari 2 subpohon (yang disjoint / saling lepas) yaitu subpohon kiri dan subpohon kanan.Setiap simpul dari pohon binar mempunyai derajat keluar maksimum = 2.
Pendefinisian pohon binar bersifat rekursif. Pohon binar acapkali disajikan dalam bentuk diagram.
Sebuah pohon binar T didefinisikan terdiri atas sebuah himpunan hingga elemen yang disebut simpul(node), sedemikian sehingga :
a.T adalah hampa (disebut pohon null) atau;
b.T mengandung simpul R yang dipilih(dibedakan dari yang lain), disebut “akar: atau “roof” dari T, dan simpul sisanya membentuk 2 pohon binary (subpohon kiri dan subpohon kanan dari akar R).
Terminologi Pada Pohon Binar
Terminologi hubungan keluarga banyak digunakan dalam terminology pada pohon binary. Misalnya istilah anak kiri dan anak kanan, untuk menggantikan suksesor kiri dan suksesor kanan , serta istilah ayah untuk pengganti prodesesor. Selain itu juga istilah saudara (brother) yang diberikan kepada kedua simpul yang mempunyai ayah yang sama. Jelas bahwa setiap simoul kecuali akar mempunyai ayah yang tunggal.
Pohon Binar Lengkap
Setiap simpul dari pohon binary paling banyak mempunyai dua anak. Suatu pohon binar T dikatakan lengkap atau complete, bila setiap tingkatnya kecuali mungkin tingkat yang terakhir, mempunyai semua simpul yang mungkin yakni 21 simpul untuk tingkat ke-r, dan bila semua simpul pada tingkat terakhir muncul dibagian kiri pohon. Jadi, pohon binary lengkap dengan simpul, T adalah tunggal(dalam hal ini mengabaikan label simpul).
Pohon-2
Pohon Binar T dikatakan pohon-2 atau pohon binar yang dikembangkan(extended binary tree) bila setiap simpul mempunyai 0 atau 2 anak. Dalam kasus ini, simpul dengan dua anak disebut simpul internal, sedanglan simpul tanpa anak disebut simpul eksternal. Dalam diagramnya, seringkali diadakan perbedaan antara simpul internal dan eksternal. Simpul internal digambar sebagai lingkaran, sedangkan simpul eksternal sebagai bujur sangkar.
Penyajian Pohon Binar Dalam Memori
Kita dapat menyajikan suatu pohon binary T dalam memori dengan dua cara. Cara pertama adalah penyajian kait (link). Cara ini biasa digunakan. Ia analaog dengan cara list berkaitan (linked list) ketika disajikan dalam memori. Cara kedua adalah dengan menggunakan sebuah array tunggal disebut penyajian sekuensial T.
Kebutuhan utama yang harus dipenuhi pada setiap penyajian T bahwa seseorang dapat mempunyai akses langsung ke akar R dan T, bila diberikan sembarang simpul N, seseorang harus dapat akses langsung ke anak dari N.
AVL Tree
AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).
contohnya:
cara menentukan Height dan balance factor:
- Jika node(root) tidak memiliki subtree heightnya = 0
- Jika node adalah leaf, height = height tertinggi dari anak +1
Balance factor :
- selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.
Insertion
untuk menjaga tree tetap seimbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru -> root. Node pertama yang memiliki[balance factor]>1 diseimbangkan. proses penyeimbangan dilakukan dengan: Single rotation dan double rotation.
terdapat 4 kasus tidak balance, yaitu:
1. Node yang terdalam terletak di sebelah left subtree dari left child node T (LL)
2. Node yang terdalam terletak di sebelah right subtree dari right child node T (RR)
3. Node yang terdalam terletak di sebelah left subtree dari right child node T (LR)
4. Node yang terdalam terletak di sebelah right substree dari left child node T (Rl)
terdapat 2 cara penyelesaian:
- Single Rotation (Kasus 1 & 2)
- Double Rotation (kasus 3 & 4)
Single Rotation
Single rotation dilakukan apabila searah, keft-left atau right-right
gambaran single rotation
Double Rotation
Double rotation dilakukan apabila searah, left-right atau right-left.
gambaran Double Rotation
Step 1(Rotasi pertama)
kasus diatas adalah left-right
Step 2(Rotasi kedua)
kasus diatas, left-left
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.
delete node 60
node 55 tidak seimbang, karena anak kiri 0 dan anak kanan 2, selisih 2.
diseimbangkan dengan single rotation (left-left) karena 55 ke 65 kiri dan 65 ke 70 kiri
akan tetapi, node 50 menjadi tidak seimbang, di subtree kiri 4 dan subtree kanan 2
diseimbangkan dengan double rotation (left-right) karena dari 50 ke 25 kiri dan 25 ke 40 kanan
berikut conoth AVL yang sudah balance
HEAP
heap adalah Complete Binary Tree(CBT) dimana harga-harga key pada node-nodenya sedemikian rupa sehingga harga-harga key pada node-node anaknya lebih kecil dari orang tuanya ataupun juga bisa lebih kecil dari orangtuanya. kedua jenis tersebut adalah max heap dan min heap.
Min-Heap
di heap ini, data pada node lebih kecil dari pada pada anaknya. Node ini memiliki node dengn nilai terkecil dengan letak pada root dan node terbedar terletak pada leaf. Heap dapat diimplementasikan dengan linked list tapi akan lebih mudah jika menggunakakn array.berikut contoh min-heap.
didalam Min-Heap terdapat beberapa operasi yaitu
-Find-min: mencari data terkecil pada Min-Heap(Root).
-Insertion:
1. insert data baru sebagai node terakhir dari heap.
2. lakukan Up-Heap
bandingkan nilai data yang di-insert dengan parentnya. jika lebih kecil dari parent, maka tukar nilainya
3. Uphead dihentikan jika nilai parentnya lebih kecil dari current node atau jika current node adaah root
-Deletion:
1. Tukar nilai dari data terakhir dengan root. Root sebagai current node.
2. karena data yang ingin dihapus sekarang berada pada leaf, langsung hapus.
3. lakukan Down-Heap
bandingkan nilai current node dengan kedua anaknya. jika salah satu anaknya lebih kecil dari current node, tukar posisi. jika kedua anaknya lebih kecil nilainya dari current node,tukar posisi dengan anak yang nilainya paling kecil.
4. Down-Heap dihentikan jika current node bernilai lebih kecil dari kedua anaknya atau jika current node adalah leaf.
Max-Heap
Max-Heap merupakan kebalikan dari Min-Heap dimana data pada node lebih besar dari data pada anaknya. di heap ini, node dengan nilai terbesar terletak pada root sedangkan node dengan nilai terkecil terletak pada leaf. operasi pada Max-Heap hampir sama dengan operasi pada Min-Heap. yang membedakan hanya konsepnya saja(data terbesar ada pada root, parent lebih besar dari anak). berikut contoh dari Max-Heap
Min-Max Heap
kondisi ini merupakan kondisi pada head bergantian antara minimum dan maximum antar level. element pada lebel genap bernilai lebih kecil dari anaknya, sedangkan element pada level ganjil bernilai lebih besar dari anaknya. root memiliki nilai paling kecil dan kedua anaknya memiliki nilai paling besar. berikut contoh dari Min-Max Heap:
operasi operasi pada Min-Max Heap- insertion
1. insert data baru sebagai node terakhir dari heap
2. lakukan upheap
proses upheap pada Min-Max Heap:
- jika node baru ada pada Min-Level:
1. jika parent dari node baru lebih kecil dari node baru tersebut maka tukar nilai dan upheadmax dari parent.
2. selain diataas, upheadmin dari node baru.
- jika node baru ada pada Max-Level:
1. jika parent dari node baru lebih besar dari node baru tersebut maka tukar nilai dan upheapmin dari parent
2. selain diatas, upheapmax dari node baru.
- Upheadmin:
1. bandingkan nilai dari current node dengan nilai dari grand-parent.
2. jika nilai dari current node lebih kecil dari parentnya, maka tukar niai.
- Upheapmax
1. bandingkan nilai dari current node dengan nilai dari grand-parent.
2. jika nilai dari current node lebih besar dari parentnya, maka tukar nilai.
- deletion
- deletion dari data terkecil:
1. tukar ilia root dengan nilai dadri data terakhir pada heap.
2. hapus data terakhir.
3. downheapmin dari root.
- deletion dari data terbesar:
1. tukar nilai anak kiri atau anak kanan dari root dengan nilai dari data terakhir pada heap.
2. hapus data terakhir.
3. downheapmax dari node.
- downheapmin
- m adalah anak dengan nilai terkceil dari current node dan grand children.
- jika m adalah grand children dari current node, maka:
+ jika m lebih kecil dari current node, maka:
1. tukar nilainya
2. jika m lebih besar dari parentnya maka tukar nilainya.
3. lanjutkan downheapmin dari m.
- jika m adalah children dari current node, maka:
+ jika m adalah children dari current node, maka:
1. tukar nilainya.
- downheapmax
kebalikan dari downheapmin.
Tries
tries adalah tree yang dilakukan untuk menyimpan array asosiatif. properties pada tries adalah setip vertex/node merepresentasikn satu huruf dan root merepresentasikan karakter kosong. aplikasi pada trees adalah fitur auto complete yang ada pada web browser. berikut contoh dari tries:
Daftar Pustaka:
