Hari : 11 Juni 2020
Kelas : CB01
Lecturer : Henry Chong (D4460) dan Ferdinand Ariandy Luwinda (D4522)
Linked List
Linked list adalah sebuah struktur data yang terdiri atas urutan data-data yang di tiap datanya memiliki referensi untuk data berikutnya atau sebelumnya dalam suatu urutan data.
 |
| Ilustrasi Linked List |
- Pada array, ukuran array sudah ditentukan saat dideklarasikan sehingga menggunakan memori yang tetap dan tidak bisa berubah ukurannya. Sedangkan pada linked list, memori yang digunakan tergantung jumlah data yang dimasukkan. Memori akan terpakai atau tersedia hanya saat penambahan atau pengurangan data. Sehingga linked list lebih dinamis.
- Pada array, data disimpan di lokasi memori yang berurutan satu dengan yang lain. Sedangkan pada linked list lokasi penyimpanan data tidak secara berurutan.
- Pada array, bisa dilakukan pengaksesan data secara acak karena kita dapat mengakses secara langsung dengan memasukkan index yang diinginkan. Sedangkan pada linked list tidak dapat dilakukan pengaksesan data secara acak karena mengikuti urutan sequence (looping).
Linked list biasanya digunakan untuk memecahkan masalah secara real-time karena cirinya yang mengalokasikan memori seiring program berjalan, hal ini penting agar program yang dijalankan tidak mengalami kendala performa akibat memori penuh yang disebabkan data tidak terpakai. Linked list menggunakan tipe data pointer untuk referensi antar datanya. Posisi dalam suatu linked list ditandai dengan adanya posisi head yang merujuk pada posisi data paling awal dan tail yang merujuk pada posisi data paling akhir.
Linked list terdiri atas 2 metode, yaitu Insert/Push yang merupakan penambahan rekor data/node dan Delete/Pop yang merupakan penghapusan rekor data/node dalam suatu linked list.
Ada 2 jenis linked list yaitu :
Single Linked List
Single Linked List adalah jenis linked list yang memiliki hubungan satu arah sebagai referensi antar datanya. Hubungan antar data direpresentasikan dengan adanya pointer next yang menunjuk data di posisi berikutnya.
 |
| Diagram Single Linked List |
Circular Single Linked List adalah single linked list yang dimana node terakhirnya menunjuk ke node paling awal (head) sehingga tidak ada node yang merujuk ke NULL, seolah-olah looping.
 |
| Circular Single Linked List |
Double Linked List
Double Linked List pada dasarnya sama dengan single linked list, hal yang membedakannya adalah adanya hubungan dua arah antar datanya yaitu next dan prev. Next merujuk pada data sesudah dan prev merujuk pada data sebelumnya.
 |
| Double Linked List |
Circular Double Linked List adalah double linked list yang membentuk suatu sirkuit (tertutup) sehingga tidak ada data yang menuju NULL baik untuk prev maupun nextnya. Karena ada dua arah hubungan, maka ada dua sirkuit yang terbentuk. Pertama adalah next dari data terakhir yang menuju ke data pertama (head) dan yang kedua adalah prev dari data pertama yang menuju ke data terakhir (tail).
 |
| Circular Double Linked List |
Stack
Stack adalah jenis struktur data yang menyimpan elemennya dalam urutan tertentu.
Stack menggunakan analogi tumpukan, yang berarti data yang terakhir kali masuk diakses terlebih dahulu dibanding data yang pertama kali masuk. Data tersimpan dalam metode Last In First Out (LIFO).
Stack sendiri dapat direpresentasikan dalam array atau suatu linked list.
Dalam bentuk array, hanya diperlukan dua variabel sebagai penanda yaitu, Top yang berfungsi menyimpan alamat data teratas dan Max yang berfungsi sebagai ukuran array. Jika Top NULL maka stack kosong, sedangkan jika Top adalah Max-1 maka stack penuh.
Dalam bentuk linked list, hampir sama konsepnya seperti linked list biasa, yaitu tiap node memiliki data dan alamat node berikutnya. Pointer awal dari linked list dijadikan Top. Semua proses insertion dan deletion dilakukan di node Top ini. Jika Top NULL artinya stacknya kosong.
Prefix adalah notasi matematika dimana operator ditulis terlebih dahulu sebelum operand.
Contoh : * 5 7 (memiliki arti yang sama dengan (5*7))
Infix adalah notasi matematika dimana operator ditulis diantara operand.
Contoh : 5 * 7 (penulisan pada umumnya)
Postfix adalah notasi matematika dimana operator ditulis setelah operand ditulis.
Contoh : 5 7 * (memiliki arti yang sama dengan (5*7))
Alasan adanya prefix dan postfix adalah karena keduanya tidak memerlukan () sehingga lebih mudah untuk diproses komputer.
:
Proses penghitungan dengan notasi Prefix dan Postfix dapat dilakukan dengan menggunakan metode Stack.
Secara dasar metode yang digunakan ada 2 yaitu :
Hashing
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil keys dengan cepat.
Dalam hashing, sebuah string dirubah menjadi value yang lebih kecil atau key yang merepresentasikan string awalnya.
Metode Hashing digunakan untuk mengambil data dalam sebuah database karena lebih cepat untuk mengakses data menggunakan key daripada string originalnya.
Hashing sendiri dapat didefinisikan sebagai konsep mendistribusi key dalam sebuah array yang diberi nama Hash Table menggunakan fungsi yang disebut Hash Function.
Hash Table
Merupakan array untuk menyimpan string original. Index tabel merupakan hashed key, sedangkan isi index adalah string originalnya.
Ukuran hash table biasanya beberapa urutan lebih sedikit dibandingkan dari jumlah total string yang memungkinkan, jadi beberapa string bisa memiliki key yang sama.
Hash Function
Ada beberapa cara untuk meng-hash string menjadi key. Berikut adalah beberapa metode penting untuk membuat hash functions.
Stack adalah jenis struktur data yang menyimpan elemennya dalam urutan tertentu.
Stack menggunakan analogi tumpukan, yang berarti data yang terakhir kali masuk diakses terlebih dahulu dibanding data yang pertama kali masuk. Data tersimpan dalam metode Last In First Out (LIFO).
Stack sendiri dapat direpresentasikan dalam array atau suatu linked list.
Dalam bentuk array, hanya diperlukan dua variabel sebagai penanda yaitu, Top yang berfungsi menyimpan alamat data teratas dan Max yang berfungsi sebagai ukuran array. Jika Top NULL maka stack kosong, sedangkan jika Top adalah Max-1 maka stack penuh.
Dalam bentuk linked list, hampir sama konsepnya seperti linked list biasa, yaitu tiap node memiliki data dan alamat node berikutnya. Pointer awal dari linked list dijadikan Top. Semua proses insertion dan deletion dilakukan di node Top ini. Jika Top NULL artinya stacknya kosong.
Queue
Jenis struktur data yang bergantung dari urutan input data. Queue sendiri menggunakan analogi antrian, yaitu istilah First In First Out (FIFO). Sehingga pada queue data yang dimasukkan pertama kali akan dikeluarkan atau diakses terlebih dahulu.
Seperti Stack, Queue dapat direpresentasikan dalam bentuk array maupun Linked list. Secara konsep queue memiliki dasar yang sama dengan stack, hanya saja menggunakan konsep FIFO.
Prefix, Infix, PostfixPrefix adalah notasi matematika dimana operator ditulis terlebih dahulu sebelum operand.
Contoh : * 5 7 (memiliki arti yang sama dengan (5*7))
Infix adalah notasi matematika dimana operator ditulis diantara operand.
Contoh : 5 * 7 (penulisan pada umumnya)
Postfix adalah notasi matematika dimana operator ditulis setelah operand ditulis.
Contoh : 5 7 * (memiliki arti yang sama dengan (5*7))
Alasan adanya prefix dan postfix adalah karena keduanya tidak memerlukan () sehingga lebih mudah untuk diproses komputer.
:
Proses penghitungan dengan notasi Prefix dan Postfix dapat dilakukan dengan menggunakan metode Stack.
Secara dasar metode yang digunakan ada 2 yaitu :
- Jika yang diterima adalah operand, maka akan dilakukan metode push().
- Jika yang diterima adalah operator, maka akan dilakukan pop sebanyak 2 kali yang dimana tiap elemennya disimpan ke sebuah variabel A dan B, kemudian dilakukan push(B operator A).
Dengan kedua metode diatas proses perhitungan akan lebih cepat diproses karena iterasinya lebih sedikit.
Hashing
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil keys dengan cepat.
Dalam hashing, sebuah string dirubah menjadi value yang lebih kecil atau key yang merepresentasikan string awalnya.
Metode Hashing digunakan untuk mengambil data dalam sebuah database karena lebih cepat untuk mengakses data menggunakan key daripada string originalnya.
Hashing sendiri dapat didefinisikan sebagai konsep mendistribusi key dalam sebuah array yang diberi nama Hash Table menggunakan fungsi yang disebut Hash Function.
Hash Table
Merupakan array untuk menyimpan string original. Index tabel merupakan hashed key, sedangkan isi index adalah string originalnya.
Ukuran hash table biasanya beberapa urutan lebih sedikit dibandingkan dari jumlah total string yang memungkinkan, jadi beberapa string bisa memiliki key yang sama.
Hash Function
Ada beberapa cara untuk meng-hash string menjadi key. Berikut adalah beberapa metode penting untuk membuat hash functions.
- Mid-Square
Metode ini dilakukan dengan cara mengkuadratkan string (dirubah menjadi integer terlebih dahulu) kemudian menggunakan beberapa bit dari tengah hasil kuadrat untuk mendapatkan hash keynya.
Contoh :
- Division / Pembagian
Penentuan hash key dilakukan dengan membagi string menggunakan operator modulus (biasanya dibagi dengan size tablenya)
Contoh : Misalkan Modulus = 12
hash key dari angka 30 adalah 6 (30 % 12 = 6)
hash key dari angka 40 adalah 4 (40 % 12 = 4)
- Folding / Lipatan
Metode yang memecah-mecah string menjadi beberapa bagian, kemudian menjumlahkan bagian-bagiannya untuk mendapatkan hash key
Contoh :
Jika suatu hash table hanya memiliki 100 lokasi penyimpanan, maka data hanya bisa disimpan pada lokasi yang memiliki 2 digit saja, oleh sebab itu string/data dipecah menjadi 2 digit
untuk key 5786 akan dipecah menjadi 57 + 86 yang menghasilkan 143, karena hanya dipakai 2 digit maka yang terpakai adalah 43.
untuk ke 12345 akan dipecah menjadi 12 + 34 + 5 yang menghasilkan 51, maka lokasinya menjadi 51,
- Digit Extraction
Penentuan lokasi hash dilakukan dengan cara menentukan digit-digit yang akan dijadikan sebagai alamat hash
Contoh :
Jika key = 235146
Digit yang akan diekstrak adalah digit ke 1, 4, 5, dan 6. Maka alamat hash key diatas adalah 2146.
- Rotating Hash
Gunakan metode fungsi hash manapun yang sudah diterangkan diatas, kemudian hasil hash address tersebut akan dilakukan rotasi.
Rotasi dilakukan dengan menggeser digit-digit untuk mendapatkan alamat hash baru
Contoh :
Hasil hash address = 20021
Hasil rotasi = 12002
Collision
Collision adalah hal yang terjadi ketika ada beberapa data yang memiliki hash key yang sama.
Untuk menyelesaikan masalah tersebut, ada 2 metode yang dapat dilakukan :
1. Linear Probing
Mencari slot array yang kosong untuk menempatkan string (Metode ini tidak disarankan untuk digunakan, lebih baik menggunakan metode chaining)
Contoh :
2. Chaining
Meletakkan string didalam slot yang sama menggunakan linked list. Dengan melakukan cara ini maka tidak perlu takut tidak memiliki array yang cukup untuk menyimpan data karena penyimpanan data secara dinamis (linked list).
Contoh :
Binary Tree
Binary Tree adalah struktur data yang menyerupai tree dimana tiap nodenya memiliki paling banyak dua children, yaitu left dan right. Node yang tidak memiliki children disebut leaf.
Jenis-jenis binary tree :
- Perfect Binary Tree : binary tree yang setiap tingkatnya memiliki kedalaman yang sama.
- Complete Binary Tree : binary tree yang pada tiap tingkatnya, kecuali yang paling terakhir terisi semua, semua nodenya terposisi paling kiri sebisanya. Perfect Binary Tree termasuk Complete Binary Tree.
- Skewed Binary Tree : binary tree yang tiap nodenya memiliki paling banyak 1 child. Secara tidak langsung, skewed tree akan membentuk relasi linked list biasa.
Penggunaan Binary Tree :
- Melakukan penghitungan operasi prefix dan postfix
- Melakukan searching dengan menggunakan BST (Binary Search Tree)
Binary Search Tree
Binary Search Tree adalah salah satu jenis struktur data yang memungkinkan pencarian secara cepat, melakukan sorting, serta kemudahan untuk memasukkan dan menghapus data.
Binary Search Tree
 |
| Binary Search Tree |
Pada dasarnya Binary Search Tree adalah Binary Tree yang sudah disorting demi memudahkan pencarian data.
Konsep pada Binary Search Tree memiliki kemiripan dengan konsep Linked List, yaitu menggunakan pointer untuk menunjuk data tertentu. Jika pada Linked List terdapat head dan tail, pada BST menggunakan istilah root yang menunjuk kepada node yang paling awal dimasukkan/sebagai penentu awal. Untuk melakukan pencarian jika pada Linked List menggunakan next dan prev, namun pada BST menggunakan istilah left dan right. Left merujuk pada lokasi node yang nilainya lebih kecil dari posisi node yang dicek saat itu, sedangkan right merujuk ke lokasi node yang nilainya lebih besar. Hal yang perlu diperhatikan adalah tiap nilai dari node dalam BST tidak sama.
Operasi Pada Binary Search Tree
Pada dasarnya BST memiliki 3 metode dasar yaitu :
- Search
Metode search merupakan salah satu alasan mengapa pada BST dilakukan secara berurutan(sorting). Dengan dilakukan secara sorting besar dan kecil maka proses pencarian dapat dilakukan secara efisien dibandingkan melakukan iterasi satu per satu untuk mencari sebuah data.
Cara kerja metode search ;
- Masukkan data yang ingin kita cari
- Pencarian akan dilakukan dari data teratas yang akan kita jadikan sebagai root
- Jika nilai data lebih kecil dari root maka root akan menjadi root->left dan jika lebih besar maka root akan menjadi root-> right
- Proses pencarian dilakukan sampai data ditemukan dan akan return root agar didapatkan datanya, jika tidak ditemukan bisa di return NULL.
Code :
 |
| Contoh searching nama |
- Insert
Insert adalah metode untuk memasukkan data ke dalam BST. Proses insertion di BST memperhatikan nilai dari data karena akan dipertimbangkan agar data tersorting dengan benar.
Cara kerja metode insert :
- Akan dilakukan pengecekan terlebih dahulu apakah di posisi root NULL atau tidak
- Jika iya maka dilakukan metode Insert
- Jika tidak akan dicek apakah nilainya lebih besar atau kecil dari root
- Hal tersebut dilakukan sampai ditemukan posisi root yang kosong
- Jika ketemu posisi kosong akan dilakukan langkah ke 2
Code :
 |
| Contoh insert untuk nama |
- Delete
Metode delete digunakan untuk menghapus node dalam BST.
Dalam metode delete harus dipertimbangkan node mana yang akan dihapus.
Ada 3 skenario yang perlu diperhatikan :
- Jika node yang akan dihapus tidak memiliki child maka hapus node tersebut.
- Jika node memiliki 1 child maka hapus node tersebut kemudian sambungkan child tersebut dengan parent dari node yang dihapus.
- Jika node memiliki 2 child maka carilah child terkanan dari subtree kiri node, kemudian rubahlah isi dari node dengan node child terkanan tersebut kemudian hapus node child terkanan tersebut (jika ada childnya maka sambungkan dengan skenario ke 2 secara rekursif).
Code :
 |
| Contoh Delete Nama |
Selain 3 metode utama diatas, ada 1 lagi metode yang bisa digunakan pada BST yaitu metode Display untuk melihat isi dari BST tersebut.
Ada 3 cara yang biasa dipakai untuk display yaitu :
- In Order : Cara display seperti ini digunakan untuk menampilkan data secara urut (sorting)
Code :
void inOrder(Data *root){
if(root != NULL){
inOrder(root->left);
printf("%d\n",root->num);
inOrder(root->right);
}
}
- Pre Order : Cara display dengan menampilkan urutan data dari paling atas (tetap dari kiri ke kanan)
Code :
void preOrder(Data *root){
if(root != NULL){
printf("%d\n",root->num);
preOrder(root->left);
preOrder(root->right);
}
}
- Post Order : Cara display mirip dengan in order namun yang di display bagian kanan dari subtree kiri terlebih dahulu (jika kiri sudah mentok, bergerak ke kanan sampai mentok baru diprint hasilnya)
Code :
void postOrder(Data *root){
if(root != NULL){
postOrder(root->left);
postOrder(root->right);
printf("%d\n",root->num);
}
}
AVL Tree
Angka-angka yang terletak diatas tiap node adalah selisih kedalaman node untuk sisi kiri dan kanan.
Dapat dilihat pada node A di tree paling kiri tertulis angka 2, hal ini karena kedalaman node A (bukan jumlah node dibawah A) di sisi kanan adalah 2 sedangkan sisi kirinya tidak memiliki child alias 0, sehingga jika dihitung selisihnya adalah 2. Begitu pula di node B memiliki selisih 1 karena sisi kanan kedalamannya 1 dan sisi kirinya 0, sedangkan node C selisihnya 0 karena sisi kiri dan kanannya tidak ada node.
Berdasarkan aturan AVL, jika ada node yang memiliki selisih kedalaman lebih dari 1, maka akan melanggar aturan AVL. Untuk mengatasi masalah tersebut maka akan dilakukan proses penyeimbangan pohon dengan 2 metode, yaitu yang disebut Single Rotation dan Double Rotation.
Sebelum mengetahui kedua metode tersebut, kita harus tahu kondisi kondisi apa saja yang perlu diperhatikan saat akan melakukan rotasi :
Pada ilustrasi tersebut dapat dilihat bahwa setelah dilakukan deletion pada node 56 maka tree menjadi tidak seimbang (Berat di kiri karena kedalaman kiri node 50 adalah 3 sedangkan sisi kanannya kedalaman 1 sehingga selisihnya 2).
Ilustrasi diatas menggambarkan Double Rotation Kanan-Kiri, hal tersebut ditandai karena pada node E terjadi pelanggaran karena sisi kiri kedalamannya 1 (sampai W) dan sisi kanannya kedalaman 3 (sampai node X dan Y) sehingga berat sebelah di kanan. Kemudian jika dilihat traversal 2 node pertama dari node E ke node X atau Y adalah kanan kemudian kiri (bengkok) sehingga diperlukan metode Double Rotation.
Heaps
Heaps adalah salah satu jenis struktur data yang menggunakan konsep perfect binary tree sebagai dasarnya. Meskipun secara dasarnya menggunakan konsep binary tree, implementasi heap biasanya dilakukan menggunakan array, hal tersebut karena dengan menggunakan array akan lebih mudah untuk dilakukan dan karena heap sendiri memiliki aturan penyimpanan data yang sedikit berbeda daripada binary tree pada umumnya. Untuk melihat perbedaannya bisa dilihat gambar dibawah ini :
AVL Tree
AVL Tree adalah salah satu jenis Binary Search Tree seimbang yang paling dasar. Dalam bentuk AVL, akan dilakukan konsep menyeimbangkan bentuk BST agar di kedua sisi memiliki kedalaman yang sama dan maksimum selisih kedalaman child tiap nodenya 1. Hal ini dilakukan untuk mempercepat dalam proses pencarian dan menghindari kemungkinan worst case scenario pada BST biasa (worst case = n kali pencarian) karena AVL Tree memiliki worst case yang mendekati log n.
Seperti yang diketahui, AVL Tree merupakan BST yang dimodifikasi dengan cara menyeimbangkan sisi kiri dan kanan tree agar proses pencarian dapat berjalan lebih cepat. Oleh sebab itu, metode dasar AVL menyerupai BST biasa yaitu dengan memiliki aturan insert, delete, dan searching yang sama. Hal yang membedakan hanyalah dilakukannya proses penyeimbangan setiap kali metode insert dilakukan. Contohnya pada kasus berikut ini :
 |
| Contoh Tree yang tidak balance menjadi balance |
Dapat dilihat pada node A di tree paling kiri tertulis angka 2, hal ini karena kedalaman node A (bukan jumlah node dibawah A) di sisi kanan adalah 2 sedangkan sisi kirinya tidak memiliki child alias 0, sehingga jika dihitung selisihnya adalah 2. Begitu pula di node B memiliki selisih 1 karena sisi kanan kedalamannya 1 dan sisi kirinya 0, sedangkan node C selisihnya 0 karena sisi kiri dan kanannya tidak ada node.
Berdasarkan aturan AVL, jika ada node yang memiliki selisih kedalaman lebih dari 1, maka akan melanggar aturan AVL. Untuk mengatasi masalah tersebut maka akan dilakukan proses penyeimbangan pohon dengan 2 metode, yaitu yang disebut Single Rotation dan Double Rotation.
Sebelum mengetahui kedua metode tersebut, kita harus tahu kondisi kondisi apa saja yang perlu diperhatikan saat akan melakukan rotasi :
- Hal pertama yang harus diingat adalah proses penyeimbangan tree akan dilakukan dari bagian terdalam dahulu, jadi apabila ada 2 node atau lebih yang melanggar aturan AVL, node paling dalam akan diselesaikan terlebih dahulu, kemudian jika node atasnya masih mengalami masalah baru akan diselesaikan kemudian (Tetapi pada umumnya jika node terdalam sudah diperbaiki, node node diatasnya yang bermasalah akan terbaiki juga).
- Apabila tree berat sisi di sebelah kanan, proses rotasi yang akan dilakukan adalah menarik tree ke sisi kiri dan begitu juga sebaliknya.
- Jika ada node yang bermasalah, ada 2 jenis kasus yang perlu diperhatikan, kasus pertama adalah jika 2 link pertama dari node yang terlanggar ke node pelanggarnya lurus (kiri dan kiri atau kanan dan kanan) yang dimana proses rotasi akan dilakukan dengan cara Single Rotation. Kasus kedua adalah jika 2 link pertama dari node yang terlanggar ke node pelanggarnya bengkok (kiri dan kanan atau kanan dan kiri) yang dimana perlu menggunakan metode Double Rotation untuk menyeimbangkan tree.
- Jika ada 2 node yang menjadi penyebab masalah ketidakseimbangan tree dan kedua metode dapat digunakan (Single dan Double Rotation) maka umumnya dipilih Single Rotation.
Single Rotation :
Sesuai namanya, metode ini akan menyeimbangkan tree dengan seolah-olah melakukan rotasi (perpindahan posisi node) sebanyak satu kali. Berikut adalah contohnya :
 |
| Kasus Single Rotation pada saat Deletion |
Pada ilustrasi tersebut dapat dilihat bahwa setelah dilakukan deletion pada node 56 maka tree menjadi tidak seimbang (Berat di kiri karena kedalaman kiri node 50 adalah 3 sedangkan sisi kanannya kedalaman 1 sehingga selisihnya 2).
Hal yang menjadi penyebab Tree tidak seimbang adalah node 10, jika kita lihat traversal 2 garis pertama dari node 50 ke node 10 adalah lurus (kiri terus kiri) sehingga dapat dilakukan single rotation untuk menyeimbangkan tree.
Hal yang terjadi adalah kita anggap 50 (atau node yang melanggar) sebagai pivot yang akan menarik node dibawahnya ke atas, dalam hal ini akan dilakukan tarikan ke arah kanan. Seolah-olah node 50 menarik node 40 ke posisi node 50 dan kemudian node 50 akan turun ke kanan sehingga terlihat node 50 menjadi child sebelah kanannya node 40. Semua node bagian kiri dari node 40 juga akan ikut terangkat keatas, kemudian jika awalnya node 40 memiliki child dibagian kanan akan secara otomatis child tersebut akan menjadi bagian kiri dari node 50 (hanya node teratas saja, jika ada child lagi dibawahnya maka akan tetap normal).
Setelah dilakukan metode penyeimbang tersebut maka Tree akan kembali menjadi AVL Tree.
Double Rotation :
Metode ini sama seperti Single Rotation, bedanya adalah rotasi dilakukan 2 kali. Jika 2 garis utamanya kiri kemudian ke kanan maka akan dilakukan rotasi ke kiri dengan node pertama dibawahnya node yang melanggar sebagai pivot kemudian rotasi ke kanan dengan node yang bermasalah sebagai pivotnya. Untuk 2 garis pertama kanan kemudian kiri dilakukan sebaliknya (rotasi kanan kemudian rotasi ke kiri). Ilustrasinya sebagai berikut :
 |
| Double Rotation Kanan Kiri |
Ilustrasi diatas menggambarkan Double Rotation Kanan-Kiri, hal tersebut ditandai karena pada node E terjadi pelanggaran karena sisi kiri kedalamannya 1 (sampai W) dan sisi kanannya kedalaman 3 (sampai node X dan Y) sehingga berat sebelah di kanan. Kemudian jika dilihat traversal 2 node pertama dari node E ke node X atau Y adalah kanan kemudian kiri (bengkok) sehingga diperlukan metode Double Rotation.
Karena node E yang bermasalah, akan dilakukan rotasi ke kanan dari node pertama dibawahnya, yaitu node G. Node G menarik node F ke posisi node G dan G mejadi child kanan F, sedangkan child kanan F sebelumnya (node Y) menjadi child kiri node G. Rotasi pertama selesai.
Rotasi kedua dilakukan di node yang bermasalah (node E), karena berat ke kanan maka dilakukan rotasi ke kiri. Node E sebagai pivot menarik node F ke atas dan node E sekarang menjadi child kiri node F. Karena dilakukan rotasi kiri, maka child kiri F sebelumnya (node X) menjadi child kanan node E. Semua child kanan F pun seolah-olah ikut naik keatas sehingga pada akhirnya membentuk BST yang seimbang (dalam kasus ini perfect binary tree) dan fungsional seperti BST pada biasanya.
Bisa dilihat bahwa tree diatas terlihat aneh dan tidak sesuai dengan aturan binary tree pada biasanya. Bentuk Tree diatas disebut dengan nama Max Heap. Max Heap sendiri adalah salah satu jenis dari heap. Heap diimplementasi menggunakan array, namun yang perlu diingat penyimpanan data pada heap dimulai dari index 1, alasannya untuk mempermudah pencarian untuk left right dan parentnya.
Jenis Heap sendiri dibagi menjadi 3 yaitu :
- Min Heap
Min Heap adalah Heap yang dimana nilai teratas/parentnya lebih kecil daripada childnya, contohnya sebagai berikut :
Dapat dilihat bahwa di root heap tersebut adalah nilai terkecil dari keseluruhan heap. Perlu diingat bahwa aturan pada heap berbeda dengan binary tree. Bisa dibilang pada heap untuk urutannya berjalan secara vertikal (per level) dan bukan seperti tree yang memecah ke kiri dan kanan tergantung nilainya. Oleh sebab itu hal diatas seperti 2 menjadi left childnya 1 dan 3 menjadi right childnya 1 bisa terjadi di heap karena heap tergantung dengan urutan input (bisa diimplementasi menjadi priority queue).
- Max Heap
Dapat dilihat bahwa semakin kebawah nilai semakin mengecil. Urutannya pun juga terlihat acak karena bergantung dari urutan input, tetapi untuk hubungan parent dan child di tiap node masih memenuhi aturan.
- Min Max Heap
Heap jenis ini bisa dibilang merupakan campuran antara min heap dan max heap. Hal yang membuat jenis heap ini unik adalah datanya selang seling tiap level/tingkatannya. Aturannya adalah untuk tingkat ganjil bersifat minimum, sedangkan genap bersifat maximum. Berikut contohnya :
Dapat dilihat di contoh diatas bahwa pada level 1 terdapat nilai 7 yang merupakan nilai terkecil dari heap ini, kemudian left childnya yaitu nilai 70 adalah nilai terbesar dari heap ini. Maka bisa dibilang bahwa nilai di root adalah nilai terkecil dari heap, sedangkan salah satu child dari root adalah nilai maksimum dari heap.
Operasi-operasi pada heap :
Insertion :
Proses insertion pada heap menggunakan index seperti pada array. Jadi inputnya dari index terakhir kali inputan dimasukkan. Kalau seperti itu, bagaimana relasinya bisa menyerupai tree ? Nah, untuk menentukan mana parent, left child, dan right childnya maka digunakan pattern sebagai berikut :
(n=index node saat ini)
Untuk mencari parent suatu node, indexnya adalah : n/2 (catatan indexnya harus integer).
Untuk mencari left child suatu node, indexnya adalah : 2*n.
Untuk mencari right child suatu node, indexnya adalah : 2*n +1.
Sebagai contoh data ke 2 dari suatu heap parentnya adalah data ke 1 karena data ke 2 adalah left childnya data ke-1. Kalau ingin mencari parentnya data ke-2 dengan rumus diatas maka : 2/2 = data ke 1. Begitu juga sebaliknya untuk mencari left child data 1 dengan rumus diatas maka : 2*1 = data ke 2.
Berdasarkan gambar, right childnya data ke 1 adalah data ke 3. Mari kita buktikan dengan rumus diatas : 2*1 +1 = 3. Maka right childnya data 1 adalah data ke 3. Untuk parent data 3 pun dapat dicari dengan cara : 3/2 = 1 (Integer). Sehingga parent data 3 terbukti data ke 1.
Setelah dilakukan insertion seperti itu, hal yang dilakukan berikutnya adalah melakukan upHeap / Heapify Up. Berikut penjelasannya :
Kalau kita lihat contoh diatas, bisa dilihat bahwa kita memasukkan angka 25 ke heap tersebut. Berdasarkan aturan index tadi maka 25 menjadi child dari node 90. Jenis heap diatas adalah min heap, sehingga aturannya adalah nilai parent harus lebih kecil dibanding kedua childnya. Akan tetapi, dengan dimasukkan angka 25, maka aturan tersebut terlanggar karena 25 lebih kecil dari 90 tetapi 90 berada diatas 25. Untuk menyelesaikannya, kita harus menukar nilai dari child dan parentnya.
Proses penukaran inilah yang disebut dengan UpHeap/ Heapify Up. Caranya dengan membandingkan node yang baru masuk dengan parentnya (sekaligus dengan grandparentnya jika min-max heap). Aturan penukarannya tergantung jenis heapnya (parentnya lebih besar dari node jika min heap, parentnya lebih kecil dari node jika max heap). Proses penukaran ini dilakukan sampai aturannya tidak terlanggar atau node sudah di posisi root.
Deletion :
Proses deletion pada heap umumnya menghapus node paling atasnya terlebih dahulu, kemudian digantikan nilainya dengan node index terakhir dimasukkan, kemudian menghapus node terakhir tersebut. Berikut contohnya :
Pada gambar diatas adalah proses delete pada heap. Pada heap biasa (bukan modifikasi) proses delete dilakukan dari root, sehingga pada gambar diatas node yang dihapus adalah node 4. Seperti aturan yang sudah disebut diatas, nilai yang akan menggantikan nilai root sebelumnya adalah nilai di node urutan paling terakhir dimasukkan, dalam kasus ini node 8. Lokasi node 8 sendiri seolah dihapus/dibuat NULL. Setelah proses penggantian tersebut, kita perlu mengecek kondisi heap apakah masih sesuai dengan heap yang kita buat.
Untuk heap ini yaitu min heap, masih terlihat bahwa 8 bukanlah nilai terkecil dari heap. Untuk mengembalikan menjadi status heap, maka perlu dilakukan penukaran nilai dengan childnya. Proses penukaran ini disebut dengan DownHeap / Heapify Down. Prosesnya dilakukan dari node pengganti root kemudian bandingkan dengan child terkecilnya/terbesarnya tergantung tipe heapnya (dari antara 2 childnya cari yang paling memenuhi). Jika sudah ditemukan, posisi mereka ditukar lalu dicek lagi di posisi barunya yang sekarang apakah child dibawahnya masih belum memenuhi aturan heap. Proses DownHeap ini dilakukan sampai posisinya kembali menjadi heap/nodenya berada di posisi leaf.
Implementasi Heap : Heap Sort
Seperti yang kita ketahui, heap ini direpresentasikan dalam array seperti ini :
Seperti yang kita lihat juga bahwa pada heap tidak terlihat ada urutan yang jelas, namun berdasarkan aturan min heap atau max heap tetap memenuhi syarat. Nah, bagaimana jika kita ingin membuat heap secara berurutan (misalnya dari kecil ke besar dan sebaliknya) dan tetap masih mengikuti aturan heap ?
Untuk itulah ada yang namanya Heap Sort, berikut ilustrasinya :
HeapSort sendiri ada 2 jenis, yaitu secara ascending (dari kecil ke besar) dengan menggunakan kaidah min heap dan secara descending (dari besar ke kecil) dengan kaidah max heap.
Sebagai contoh saya menggunakan aturan max heap. Pada dasarnya, proses Heap Sort ini sebenarnya adalah proses melakukan delete berulang-ulang sampai heap habis yang dimana data yang di delete ditampung di array lain. Kemudian setelah heap kosong, array lain yang menampung data di delete akan menjadi berurutan dan bisa dicopy kembali ke array heap sebelumnya.
Saya akan menjelaskan alurnya, pada contoh diatas merupakan max heap sehingga proses deletion akan menghapus node 16 dan berdasarkan cara deletion nilai 16 akan digantikan dengan angka 1 yang kemudian dilakukan downheaping sampai akhirnya nilai root adalah 14. Nilai 16 ini ditampung di suatu array baru sementara (dalam kasus contoh diatas node 16 diletakkan di akhir array, sehingga setelah jadi akan membentuk sorting secara ascending). Kemudian proses berikutnya adalah delet 14 dan proses delete dilakukan berulang-ulang sampai heap habis. Jika mengikut pattern seperti ini, array penampung akan menjadi berurutan dan hal inilah yang disebut Heap Sort. Jika dimasukkan kembali ke dalam bentuk tree akan terlihat bahwa data sudah berurutan dari kiri kanan dan secara vertikal sesuai dengan aturan heap.
Tries
Tries adalah jenis struktur data yang membentuk trees bercabang-cabang yang didalamnya merupakan kumpulan karakter-karakter yang membentuk suatu kata. Tries ini biasanya digunakan untuk fitur autocomplete, spell checker dari kamus, atau mencari validitas suatu kata.
Berikut adalah gambaran Tries :
Jika dilihat dari ilustrasi diatas, bisa diketahui bahwa konsep tries ini memiliki fungsi untuk mempermudah dalam proses pencocokan kata dalam waktu yang singkat. Hal ini dikarenakan adanya rute rute yang memecah yang kemudian membentuk kata yang baru dan unik. Sebagai contoh pada rute r-o ada 2 branch, yaitu rute l-l dan rute u-n-d. Kedua rute ini membentuk suatu kata yang berbeda, tetapi dalam proses pencocokannya hanya perlu dilakukan pencarian sebanyak panjang kata tanpa perlu mengeceknya dari awal setiap pengecekan. Hal ini akan sangat membantu jika ada banyak kata yang memiliki beberapa huruf yang sama namun memiliki akhiran berbeda/panjangnya berbeda.
Tries ini sendiri bisa tidak terbatas jumlahnya tergantung seberapa banyak kita ingin memasukkan data. Sebagai contoh, kita bisa menambahkan kata "read" pada Tries diatas. Hal tersebut dapat dilakukan dengan membuat branch baru pada node 'r' kemudian membuat rute baru yaitu 'e-a-d'. Dengan begitu sudah dibentuk Trie baru tanpa perlu membuat dari awal lagi.
Bisa diperhatikan bahwa di beberapa node ada tulisan isFinal. Apakah isFinal itu ?
isFinal ini adalah suatu variabel boolean yang menandakan akhir dari suatu kata yang memiliki arti. Jika isFinal true maka dari awal sampai node tersebut telah terbentuk suatu kata, meskipun Trienya sendiri masih ada lanjutannya. Jadi apabila traversal berhenti di node yang memiliki tulisan isFinal dan kata yang dicari/dimasukkan sesuai maka pencarian berhenti dan tidak dilanjutkan kebawah. Dalam satu rute bisa saja banyak node yang memiliki isFinal karena pada node tersebut telah terbentuk kata yang baru.
Kesimpulannya, adanya Tries ini mempermudah dalam proses pencarian/pencocokan kata terutama kata pada kamus.
Materi Tambahan / Trivia
Materi Tambahan / Trivia
Linked List banyak digunakan dalam berbagai jenis program-program komersial maupun non-komersial. Hal ini bertujuan agar performa program dapat dijalankan dengan baik. Tidak hanya itu, penggunaan Linked List juga sangat digunakan dalam industri Video Games.
Dalam pembuatan game Linked List digunakan untuk merepresentasikan sesuatu yang disebut Game Objects. Hal ini mengatur tentang objek objek yang terdapat di sebuah game, seperti player, enemies, rintangan, power up, dan lain lain.
Penggunaan Linked List dalam video game lebih ditujukan untuk kepentingan render suatu objek. Sebagai contoh, apabila suatu objek akan di spawn maka akan dilakukan metode insert node, sedangkan jika objek tersebut memenuhi suatu kondisi tertentu yang mengharuskan objek tersebut menghilang maka dapa dilakukan metode delete agar tidak berinteraksi lagi dengan objek lain di game tersebut.
Akan tetapi tidak semua hal dalam suatu game menggunakan linked list, untuk beberapa hal sebaiknya tidak menggunakan linked list melainkan array. Hal tersebut mencakup terrain, pohon, tanaman, 2D tiles dan lain lain dalam sebuah game tampak atas (top down games).
Untuk mengetahui lebih lanjut saya lampirkan referensi saya dibawah ini
Selain Single Linked List dan Double Linked List, implementasi Linked List dalam dunia kerja ada berbanyak macam, jenis ini disebut Multi Linked List. Berdasarkan pengertiannya, Multi Linked List adalah Linked List yang mempunyai 2 atau lebih relasi antara nodenya, arah hubungannya tersebut bervariasi sesuai kebutuhan.
Sebagai contoh pada implementasi Video Game bisa saja tiap node memiliki relasi left, right, up, down atau bahkan hubungan 8 arah. Logicnya sama dengan Linked List seperti biasa namun disesuaikan dengan jumlah relasi yang diperlukan.
Aplikasi Hashing pada Blockchain
1. Industri Makanan
Saat ini banyak pusat perbelanjaan seperti Walmart bekerja sama dengan IBM untuk menggabungkan blockchain dalam sistem manajemen makanan mereka. Semakin banyak orang yang tidak memedulikan asal makanan mereka. Ini menyebabkan banyak masalah tidak hanya bagi konsumen tetapi juga pemasok.
2. Aplikasi Blockchain pada Cyber Security
Terdapat 3 fitur blockchain yang bisa membantu mencegah serangan keamanan cyber.
Fitur #1: Sistem yang Tidak Terpercaya
Sistem blockchain berjalan tanpa konsep ‘kepercayaan manusia’. Seperti pernah dituliskan Derin Cag dalam artikelnya yang berjudul Richtopia, “Ini mengasumsikan bahwa insider atau outsider dapat berkompromi dengan sistem kapanpun, karenanya ini bersifat bebas dari ‘etika manusia’.”
Fitur #2: Kekekalan
Blockchain membolehkan untuk menyimpan data dan mengamankannya menggunakan aturan kriptografi seperti digital signature dan hashing. Satu dari fitur terbaik adalah ketika data memasuki block dalam blockchain, data tidak bisa dirusak. Ini disebut ‘kekekalan’.
Fitur #3: Desentralisasi dan Konsensus
Blockchain adalah sistem terdistribusi yang bersifat desentralisasi. Blockchain terbuat dari banyak node. Untuk mengambil keputusan, mayoritas node harus mencapai konsensus dan mengambil keputusan. Sehingga, kita memiliki sistem demokrasi dan bukan figur otoritatif yang terpusat.
Untuk mempelajari lebih lanjut, dapat dilihat pada web berikut ini :
