Nama: Michael Owen
NIM: 2301848584
Kelas Besar (CB01): Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460)
Kelas Kecil (LC07) : Rita Layona (D5026), Ari Davis(AA191)Linked List:
Hampir sama seperti arrays, linked list merupakan data struktur bersifat linear. Tapi bedanya linked list menggunakan pointer. Dalam arti linked list terdiri dari zona/nodes yang mempunyai data dan referensi
No.
|
Linked List
|
Array
|
1.
|
Setiap elemen linked list terdiri dari 2 bagian, data dan pointer address.
|
Setiap elemen array hanya berisi data saja.
|
2.
|
Pengalokasian ruang memori dilakukan tanpa pendeklarasian sebelumnya dan terbatas pada jumlah ruang memori yang tersisa (dapat dipakai).
|
Pengalokasian ruang memori terbatas pada jumlah ruang yang dideklarasikan sebelumnya.
|
Ada 3 macam linked list: Circular Singly, Circular Doubly dan Doubly Linked List
· Circular single ini berulang dari node akhir ke node pertama, dan tidak ada nilai NULL dalam list ini
· Circular Doubly Linked List sama seperti singly tapi ada 2 referensi
· Doubly Linked list merupakan linked list 2 arah dimana node satu memegang referensi ke node 2 dan sebaliknya juga
Untuk membuat linked list butuh pakai data struct
struct basket{
char Name[109];
int quant;
int price;
basket *next,*prev;
} *head, *tail, *curr; ->merupakan linked list kita yang harus di declare
Hashing adalah bentuk data struktur yang menggunakan Hash Function yang digunakan untuk memetakan sebuah value dengan kunci tertentu supaya dapat di akses lebih cepat.
Dalam arti Hashing adalah cara untuk menrubah nilai kunci menjadi range index di array. Hashing juga merupakan cara untuk melakukan program search lebih efektif dibandingkan binary search dan linear search
Hash function adalah proses yang merubah kunci dan memetakannya menjadi panjang tertentu menjadi hash value, maka menjadi hash key.
Hash value adalah versi kecil pada string karakter awal. Dengan digital signature dan hash value dikirim ke receiver. Receiver lalu menggunakan hash function yang sama dan dibanding dengan pesan yant tadi. Jika hash valuesnya sama maka akan menampilkan error.
Trees
Tree merupakan salah Satu bentuk Struktur Data tidak linier Yang menggambarkan hubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan Satu elemen khusus. Yang disebut root Dan Node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree).
Istilah-istilah umum dalam tree:
- Parent : predecssor satu level di atas suatu node.
- Child : successor satu level di bawah suatu node.
- Sibling : node-node yang memiliki parent yang sama dengan suatu node.
- Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
- Size : banyaknya node dalam suatu tree.
- Height : banyaknya tingkatan/level dalam suatu tree.
- Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
- Leaf : node-node dalam tree yang tak memiliki seccessor.
- Degree : banyaknya child yang dimiliki suatu node.
Pohon biner atau Binary Tree adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.
AVL tree adalah Binary Search Tree/BST yang mempunyai sifat self-balancing . AVL Tree ditemukan oleh Adelson-Velsky dan Landis dan tree ini dinamakan AVL/inisial nama penemunya. AVL tree melakukan penyeimbangan sendiri dengan faktor dimana setiap node mempunyai perbedaan Tinggi atau level maksimal 1 dengan jumlah anaknya.
Contoh AVL Tree:
Tree ini diklasifikasikan AVL Tree karena setiap node mempunyai perbedaan bernilai 1 Bandingkan rute 1->10->11 dengan tingkat 2 sama rute 1->0 dengan tingkat 1. Jika diselisihkan node 1 adalah puncak node yang mempunyai perbedaan nilai 1
Insertion AVL Tree
Sifatnya AVL Tree adalah setiap node harus mempunyai perbedaan tingkat nilai 1. Jika ditambahkan atau dikurangkan node maka Tree akan tidak dibilangkan berjenis AVL jika tingkatnya lebih dari nilai 1. Untuk membenarkan tree tersebut dilakukannlah rotasi. Ada 2 macam rotasi yaitu Single dan Double Rotation
Rotasi ini tergantung pada bagian tree yang ditambahkan. Jika ada satu bagian dimana node puncaknya menjadi tidak stabil atau tidak bernilai 1 maka node yang mempunyai tidak nilai seimbang tersebut akan menjadi poros rotasi untuk menyesuaikan tree yang barunya.
Tree ini sama seperti tree yang diatas sebelumnya. Tapi ditambahkan Node 20 dia bagian kanannya. Sekarang jika dihitung perbedaan tinggi rute 1->0 dengan 1 tingkat, dengan rute 1->10->11->20 dengan tingkat 3 maka dinyatakan tidak seimbang dan tidak menjadi AVL Tree.
Untuk menyelesaikan masalah ini dilakukannya rotasi. Dalam kasus ini dilakukannya Single Rotation ke kiri
Dan ini hasilnya. Node 10 dijadikan puncak tree dan seluruh tree dikatrol atau digeser ke kiri. Tapi Node 10 sudah mempunyai anak 10 dan 11 di tree sebelumnya, jadi mengapa node 9 menjadi anaknya node 1?
Ini dikarenakan peraturan BST dimana node sebelumnya disesuaikan. Node 1 ditarik ke kiri dengan anaknnya 0 dan 10 menjadi puncak barunya. Node 9 akan mengikuti node yang kurang dari 10 tapi lebih dari 1 sehingga menjadi anak Node 1.
Gambar diatas merupakan proses penyeimbangan tree dengan Double Rotation. Beda dengan Single Rotation, rotasi ini melibat melakukan 2 kali rotasi. Biasa rotasi ini dilakukan bila ketidak seimbangannya bersifat lekuk atau kiri-kanan. Tree diatas dilakukan rotasi kiri sekal dengan node 5 sebagai porosnya. Tapi setelah rotasi pertama tree masih tidak seimbang maka dilakukanlah rotasi kedua ke kanan dengan 10 sebagai porosnya. Dan hasil akhirnya menjadi seimbang.
Deletion AVL Tree
Untuk membahas Deletion kita akan menggunakan AVL tree berikut:
Tree ini sudah mempunyai semua node seimbang dengan nilai 1. Tapi jika misalnya node 7 dihilangkan maka node 5 akan mengambil posisi 7
Tapi Jika dilihat Hasilnya, Tree ini menjadi tidak seimbang. Untuk menyelesaikan masalah ini kita lakukan single rotation ke kiri dengan Node 5 sebagai poros.
Sehingga menjadi begini. Node 10 dinaikan dan node 5 menjadi anaknya 10 dan node 9 menjadi anaknya 5.
Heap adalah Binary Tree khusus yang berbentuk complete. Tapi bedanya dengan AVL Tree, Heap mempunyai heap property atau kondisi:
· Max Heap: dimana nilai parent harus lebih tinggi daripada anaknya
· Min Heap: Dimana nilai root/puncaknya harus nilai terkecil dari semua node
Ada juga yang disebut min-max heap. Heap ini merupakan gabungan dari min heap dan max heap. Heap ini akan berganti-ganti antara min heap dan max heap di tiap level. Heap ini berguna untuk mencari nilai min max dalam 1 heap saja.
Insertion
Dalam melakukan inert node dalam suatu heap, kita lakukan Up-heap. Up-heap akan menaikan node jika nilai node lebih besar hingga mempunyai urutan yang benar
Deletion
Dalam deletion, jika ingin menghapus node akan dilakukan down-heap. Beda dengan Up-Heap, Down -Heap mengganti node root dengan elemen terakhir pada level terakhir. Contohnya dengan heap ini.
Trie
Trie adalah struktur data berupa pohon terurut untuk menyimpan suatu himpunan string dimana setiap node pada pohon tersebut mengandung awalan yang sama. Sebenarnya kata Tries diambil dari kata reTRIEval, karena tries menemukan kata tunggal dalam kamus dengan hanya awalan katanya.
