Name: Ignatius Hansen
NIM: 2301853275
Class: CB01-CL, LL01
Lecturer: Henry Chong (D4460), Ferdinand Ariandy Luwinda (D4522), dan Reinert Yosua Rumagit (D6191)
Single Linked List
adalah sebuah Linked List yang menggunakan satu variabel pointer saja untuk menyimpan banyak data.
Dalam single Linked List, pointer hanyak bergerak ke satu arah saya, kedepan/kebelakang.
Single Linked List dibagi menjadi 2 yaitu:
- Circular Single Linked List.
- Non Circular Single Linked List.
Circular Single Linked List
- Adalah Single Linked List yang pointernya menunjuk pada dirinya sendiri, kata circular dalam Circular Single Linked List memiliki arti bahwa pointer selanjutnya akan menunjuk pada dirinya sendiri sehingga akan berputar.
Non Circular Single Linked List
- Perbedaanya dengan Circular adalah Single Linked List ini, pointer selanjutnya tidak akan menunjuk pada dirinya sendiri sehingga tidak akan berputar.
Double Linked List
- Adalah Linked List yang memiliki 2 variabel pointer yaitu pointer yang menunjuk pada node setelahnya dan satu lagi yang menunjuk pada node sebelumnya. Setiap head and tailnya menunjuk Null
- Elemennya terdiri dari 3 bagian:
- Pointer next yang menunjuk elemen setelahnya
- Pointer prev yang menunjuk elemen sebelumnya
- Bagian data informasi
Circular Double Linked List
- Adalah Linked List yang disetiap nodenya memiliki 3 field yaitu:
- 1 Field pointer menunjuk next
- 1 Field pointer menunjuk prev
- 1 Field yang berisi data dari node
- Pointer next dan prevnya menunjuk kedirinya sendiri secara circular.
- Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node setelahnya serta ke node sebelumnya
- Untuk membuat node baru, pada awalnya pointer next dan prev akan menunjuk pada NULL
- Selanjutnya pointer prev akan menunjuk ke yang sebelumnya dan next menunjuk pada node setelahnya
Stack & Queue
Stack adalah tumpukan data yang diletakkan bertumpukkan. Stack menggunakan konsep yang bernama LIFO yang berarti Last in First Out, data yang terakhir dimasukkan merupakan data yang pertama kali diakses atau dikeluarkan.
Terdapat 2 operasi di dalam Stack yang sering digunakan yaitu:
- Push: digunakan untuk menambahkan data pada Stack
- Pop: digunakan untuk mengambil data pada Stack
Queue adalah stuktur data linear dimana penambahan data dilakukan disatu sisi, disalah satu ujungnya, untuk penguruangannya dilakukan diujung lain, Queue menggunakan konsep FIFO yang berarti First in First Out, data yang pertama kali dimasukkan merupakan data yang pertama kali diakses.
Terdapat 2 operasi dalam Queue yang sering digunakan yaitu:
- Enqueue: digunakan untuk memasukkan sebuah data ke dalam queue. pada proses enqueue, bagian tail yang berjalan sendiri seiring dengan masuknya data baru ke dalam queue.
- Dequeue: digunakan untuk menghapuskan sebuah data yang paling pertama masuk ke dalam queue
Perbedaan antara Stack & Queue
- Prinsip kerjanya, Stack menggunakan prinip kerja tumpukan sementara Queue menggunakan prinsip kerja antrian.
- Konsep kerjanya, Stack menggunakan LIFO, Last in First Out sementara Queue menggunakan FIFO, First in First Out.
- Pada proses penambahan dan penghapusan elemen, pada Stack operasi penambahan atau pengurangannya dilakukan pada satu ujungnya. Pada Queue operasi penambahan atau pengurangannya dilakukan di tempat yang berbeda.
Hash Table
- Merupakan salah satu stuktur data yang digunakan untuk menyimpan data sementara. Hash Table digunakan untuk mempercepat pencarian kembali dari banyak data yang telah disimpan. Haah table menggunakan teknik penyimpanan sehingga waktu yang dibutuhkan untuk insertions, deletions, dan searching relatif sama dibandingkan dengan struktur data yang lain.
- Kelebihan Hash table:
- Hash table relatif lebih cepat.
- Kecepatan dalam insertions, deletions, dan searching relatif sama.
- Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Intinya hash table merupakan penyimpanan data yang menggunakan key value yang didapat dari nilai data itu sendiri.
- Beberapa hal yang perlu diperhatikan dalam membuat hash function:
- Ukuran array
- Key value
- Hash value/ Hash index
Tree
- Merupakan salah satu bentuk struktur data yang tidak linear, menggambarkan hubungan ont to many antara elemen-elemen. Tree terdiri dari kumpulan node di mana ada yang disebut root dan node lainnya disebut subtree.
- Bagian-bagian dari tree:
- Root, jika tree kosong maka node pertama dan merupakan node unik merupakan root.
- Branch, banyaknya cabang sidebut degree dari node tersebut.
- Leave, merupakan node yang nilai outdegreenya 0, merupakan node yang tidak memiliki successor.
- Parent, disebut parent ketika outdegreenya lebih dari 0.
- Child, cabang terakhir dari sebuah tree.
Binary Tree
- Merupakan tree yang memiliki syarat tiap nodenya hanya memiliki maksimal dua subtree dan kedua subtreenya harus terpisah. Maka tiap node dalam binary tree hanya dapat memiliki 2 child.
- Ada dua cara representase binary tree:
- Representasi sekuensial
- Representasi terkait
- Jenis-jenis binary tree:
- Full Binary Tree
- Complete Binary Tree
- Skewed Binary Tree
Binary Search Tree
- Disebut juga pohon biner yang dalam struktur data bersifat hirarkis. Binary Tree merupakan suatu tree dengan dyarah bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binaty tree boleh memiliki paling banyak 2 child, secara khusus anaknya dinamakan kiri dan kanan.
- Binary Search Tree berfungsi menyimpan informasi nama atau bilangan yang disimpan dalam memory. Dengan membagi data menjadi dua dengan mencari titik tengah sbagai patokannya. Binary tree terdiri dari simpul pertama yang disebut root.
- Binary Search memungkinkan pencarian dengan cepat, penambahan, dan penghapusan menggunakan informasi kunci atau key.
- Dua aturan yang harus dipenuhi:
- Semua data dibagian kiri sub-tree node t selalu lebih kecil dari data dalam node t itu sendiri.
- Ada beberapa metode di dalam Binary Search Tree:
- Insert, pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat
- Update, update akan mempengaruhi posisi node tersebut. Setelah diupdate yang awalnya Binary Search Tree, menjadi bukan Binary Search Tree. Maka perubahan perlu dilakukan dengan melakukan rotasi agar tetap menjadi Binary Search Tree.
- Delete, delete dalam Binary Search Tree juga memperngaruhi posisi tree tersebut.
AVL Tree
- AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian danbentuk tree dapat dipersingkat dan disederhanakan. Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru→root. Node pertama yang memiliki balance factor > 1 diseimbangkan. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.
- Proses penyeimbangan dilakukan dengan:
- Single rotation adalah rotasi yang dilakukan apabila data yang diinsert searah, left-left atau right-right.
- Double rotation adalah rotasi yang dilakukan apabila data yang diinsert tidak searah, left-right atau right-left.
- Operasi pada AVL:
- Insertion atau insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam.
- Deletion 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.
Red Black Tree
- Red Black Tree adalah suatu BST( Binary Search Tree) dimana node-node dan edge-edge memiliki warna merah atau hitam. Warna dari root selalu hitam. Warna dari edge yang menghubungkan ayah dengan anaknya selalu berwarna sama dengan warna node anak tersebut.
- Aturan pada Red Black Tree :
- Setiap simpul/node adalah berwarna merah atau hita,
- Akar selalu berwarna hitam
- Nilai sebuah node adalah lebih besar anak kirinya dan lebih kecil dari anak kanannya.
- Jika node berwarna merah, anaknya harus berwarna hitam
- Node berwarna merah secara berturut-turut tidak diperkenankan.
- Setiap path dari node yang menuju ke nil harus mengandung nilai yang sama dengan node yang berwarna hitam.
- Tree dikatakan setimbang jika selisih level dari anak kiri dan anak kanan maksimal dua.
- Node dibawah root yang berada pada level yang sama disebut sibling.
- Aturan Insert pada Red Black Tree :
- Setiap node baru yang disisipkan kedalam tree akan diberi warna merah.
- Jika kita memberi warna hitam pada node baru yang masuk, maka jumlah node dari root akan berbeda.
- Jika kita memasukkan node baru yang berwarna merah kedalam parent yang berwarna hitam tidak akan menjadi masalah, yang menjadi masalah adalah jika kita menyisipkan node baru ke dalam parent yang berwarna merah
- Jika parent berwarna merah kita akan membuat dua node merah yang berurutan, jadi kita harus melakukan rotasi atau pewarnaan ulang.
- Hal penting yang harus diingat adalah node yang tidak mempunyai daun harus berwarna hitam.
Heap & Tries
Heap
Heap
- Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifatnya, yaitu jika B adalah anak dari A, maka nilai yang tersimpan di node A lebih besar atau sama dengan nilai yang tersimpan di node B.
- Heap terbagi menjadi 2 yaitu:
- Min Heap, setiap elemen node adalah lebih kecil daripada childrennya. Ini menunjukan bahwa elemen terkecil terletak pada root dari tree. Unsur terbesar adalah terletak di suatu tempat di salah satu node leaves.
- Max Heap, setiap elemen node adalah lebih besar daripada childrennya. Karena urutan sibling dalam heap tidak ditentukan oleh sifat heap, dua node tunggal anak-anak bisa secara bebas dipertukarkan.
- Sifat dari Heap:
- Setiap node lebih besar dari atau sama dengan masing-masing anak sesuai dengan perbandingan predikat yang ditetapkan untuk struktur data.
Tries
- Adalah Binary Tree dimana didalamnya terdapat kumpulan dari kata-kata. Tree ini dibuat untuk mempermudah pencarian suatu kata-kata (biasanya digunakan pada saat pembuatan fitur search pada kamus).
Minimum Spanning Tree
- Algoritma Prim membangun pohon spanning minimum untuk grafik, yang merupakan pohon yang menghubungkan semua node dalam grafik dan memiliki biaya total terkecil di antara semua pohon yang menghubungkan semua node. Prosesnya dengan mencari nilai terkecil lalu menghubungkannya satu dengan yang lain namun tetap mencari yang terkecil sehingga pada akhirnya mendapatkan nilai minimum.
- Algoritma Kruskal membangun pohon spanning minimum untuk grafik, yang merupakan pohon yang menghubungkan semua node dalam grafik dan memiliki biaya total terkeci; di antara semua pohon yang menghubungkan semua node. Prosesnya dimulai dengan mencari nilai terkecil lalu menandainya dan pada akhirnya satu sama lain akan terhubung dan mendapatkan total dengan nilai terkecil.
- Algoritma Dijkstra membangun pohon jalur terpendek mulai dari beberapa simpul sumber. Pohon jalur terpendek adalah pohon yang menghubungkan semua node dalam grafik kembali ke simpul sumber dan memiliki properti bahwa panjang jalur apa pun dari simpul sumber ke simpul lain dalam grafik diminimalkan.
https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/
https://bayusetyapramana.wordpress.com/2011/06/18/red-black-tree/
https://bayusetyapramana.wordpress.com/2011/06/18/red-black-tree/
No comments:
Post a Comment