Final Review
Frans/2301852096/CB01
Dosen:
1. Ferdinand Ariandy Luwinda/ D4522
2.Henry Chong/ D4460
Selama 1 semester yang penuh pandemi ini, berikut yang saya dapatkan dari mata kuliah Data Structure:
1.Linked List
Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian Linked list juga merupakan suatu cara untuk menyimpan data dengan struktur sehingga dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data yangdiperlukan. Struktur ini lebih dinamis karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan array yang ukurannya tetap. berikut gambaran kecil mengenai linked list. Linked list terbagi menjadi 2,
a.Circular single linked list
Circular Single Linked List adalah Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,
maka pointer next pada node terakhir akan menunjuk ke node terdepannya.
b.Doubly linked list
Double Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list.
Berikut adalah cara cara dalam membuat linked list:
a.Pembuatan Struct
Hal pertama yang harus kita lakukan sebelum membauat linked list adalah yaitu membuat structnya terlebih dahulu, contoh codingnnya adalah sebagai berikut,
AVL Tree
AVL Tree merupakan salah satu jenis BST (binary Search Tree). BST digunakan dengan tujuan untuk mempercepat pencarian data. Apabila BST yg terbentuk cukup seimbang (mendekati complete binary tree) maka waktu pencarian data tidak lebih dari log2n langkah.
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 dan bentuk tree dapat dipersingkat dan disederhanakan.
Heap
Heap is a complete binary tree based data stucture that satisfies heap property and Leaf Node should be as left as possible.
Heap dibagi 2,
1.Min Heap
Min heap adalah heap yang setiap node memiliki value parent lebih kecil dari pada value nodenya.
e.g. Insert(20)
Deletion in Min Heap:
Tahap dalam melakukan Deletion Min Heap
1.Kita hanya bisa menghapus root node, oleh karena itu kita tinggal hapus root node lalu tukar dengan leaf node paling kanan
2.Setelah itu kita tinggal melakukan pembenaran, karena ini min heap, maka yang harus kita lakukan adalah mencari child dengan vaue paling kecil dan menukar valuenya dengan parentnya.
3.Lakukan langkah 2 terus menerus sampai Heap terbentuk dengan benar.
e.g. Delete(7)
2.Max Heap
Min heap adalah heap yang setiap node memiliki value parent lebih besar dari pada value nodenya.
Deletion in Max Heap:
Tahap dalam melakukan Deletion Min Heap
1.Kita hanya bisa menghapus root node, oleh karena itu kita tinggal hapus root node lalu tukar dengan leaf node paling kanan
2.Setelah itu kita tinggal melakukan pembenaran, karena ini max heap, maka yang harus kita lakukan adalah mencari child dengan vaue paling besar dan menukar valuenya dengan parentnya.
3.Lakukan langkah 2 terus menerus sampai Heap terbentuk dengan benar.
Tries
Tries is an ordered tree data structure that is used to store an associative array(usually string). The trem tree comes form word Retrieval. 'cause tries can find a single word in a dictionary with only a prefix of the word.
Refferences:
- http://blog-arul.blogspot.com/2012/01/queue-pada-struktur-data.html
- http://blog-arul.blogspot.com/2012/01/stack-pada-struktur-data.html
- https://www.beritabebas.com/definisi/hashing/
- https://sourcecodegeneration.blogspot.com/2018/08/pengertian-binary-tree-binary-search.html
- https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/
- Binus Sources
- Jenny's lectures CS/IT NET & JRF(yt channel) --> she's the best ^^
Frans/2301852096/CB01
Dosen:
1. Ferdinand Ariandy Luwinda/ D4522
2.Henry Chong/ D4460
Selama 1 semester yang penuh pandemi ini, berikut yang saya dapatkan dari mata kuliah Data Structure:
1.Linked List
Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian Linked list juga merupakan suatu cara untuk menyimpan data dengan struktur sehingga dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data yangdiperlukan. Struktur ini lebih dinamis karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan array yang ukurannya tetap. berikut gambaran kecil mengenai linked list. Linked list terbagi menjadi 2,
a.Circular single linked list
Circular Single Linked List adalah Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node,
maka pointer next pada node terakhir akan menunjuk ke node terdepannya.
b.Doubly linked list
Double Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list.
Berikut adalah cara cara dalam membuat linked list:
a.Pembuatan Struct
Hal pertama yang harus kita lakukan sebelum membauat linked list adalah yaitu membuat structnya terlebih dahulu, contoh codingnnya adalah sebagai berikut,
b.Push Head
Push head adalah metode untuk menambahkan node yang kita ingin masukan di paling depan, contoh codingnya sebagai berikut,
c.Push Tail
Push Tail adalah metode untuk menambahkan node yang ingin kita masukan di paling belakang, contoh codingannya sebagai berikut,
d.Push
Push adalah metode untuk menambahkan node yang kita inginkan di urutan yang kita inginkan, contoh codingnnya sebagai berikut, hanya bisa digunakan menggunakan double linked list.
e.Pop
Pop adalah metode untuk menghilangkan node yang kita inginkan, contoh codingnya adalah sebagai berikut,
2.Stack
Stack adalah sebagai tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain, koleksi dari objek-objek homogen, atau Suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja.
3.Queue
Queue adalah sekumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung disebut dengan sisibelakang(rear), dan penghapusan(pengambilan elemen) dilakukan lewat ujung lain (disebut dengan sisi depan atau front).
4.Hashing
Hashing adalah transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau kunci yang mewakili string asli. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli. Itu juga digunakan dalam banyak algoritma enkripsi.
5.Binary Tree
Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.
6.Binary Search Tree
Binary Search Tree atau sering disingkat BST. Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.
Stack adalah sebagai tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain, koleksi dari objek-objek homogen, atau Suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja.
Queue adalah sekumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung disebut dengan sisibelakang(rear), dan penghapusan(pengambilan elemen) dilakukan lewat ujung lain (disebut dengan sisi depan atau front).
Hashing adalah transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau kunci yang mewakili string asli. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli. Itu juga digunakan dalam banyak algoritma enkripsi.
5.Binary Tree
Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.
6.Binary Search Tree
Binary Search Tree atau sering disingkat BST. Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.
Binary Search Tree has the following basic operations:
1.Find(x) : find key x in the BST
2.Insert(x) : insert new key x into BST
3.Remove(x) : remove key x from BST
AVL Tree
AVL Tree merupakan salah satu jenis BST (binary Search Tree). BST digunakan dengan tujuan untuk mempercepat pencarian data. Apabila BST yg terbentuk cukup seimbang (mendekati complete binary tree) maka waktu pencarian data tidak lebih dari log2n langkah.
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 dan bentuk tree dapat dipersingkat dan disederhanakan.
Cara menentukan Height dan Balance Factor:
Height:
- Jika node(root) tidak memilik subtree heightnya = 0
- Jika node adalah leaf, height = 1
- Jika internal node, maka height = height tertinggi dari anak+1
Balance Factor:
- Selisih Height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0
AVL Tree Operation
A.Insertion
Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam.
Ada 4 Kasus yang biasanya terjadi saat operasi insert:
1. Node terdalam terletak pada subtree kiri dari naak kiri T (left-left)
2. Node terdalam terletak pada subtree kanan dari anak kanan T (right - right)
3. Node terdalam terletak pada subtree kanan dari anak kiri T (right - left)
4. Node terdalam terletak pada subtree kiri dari anak kanan T(left- right)
Cara menangani keempat kasus tersebut ada 2 cara:
1. Single rotation
Single rotation(rotasi 1x) dilakukan apabila searah, left - left atau right- right.
Berikut gambar dari operasi single rotation
2.Double rotation
Double rotation(rotasi 2x) apabila searah, left- right atau right -left
berikut gambar dari operasi double rotation,
B. Deletion
Operasi deletion node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantukan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adlaah 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 sama seperti operasi insertion.
Berikut contoh dari operasi Deletion
*Kita ingin menghapus node (60)
Heap
Heap is a complete binary tree based data stucture that satisfies heap property and Leaf Node should be as left as possible.
Heap dibagi 2,
1.Min Heap
Min heap adalah heap yang setiap node memiliki value parent lebih kecil dari pada value nodenya.
Insertion in Min Heap:
Tahap dalam melakukan insertion Min Heap
1.Masukan node baru ke node yang masih memiliki tempat
2.Bandingkan node baru dengan parentnya
3.Jika value parent lebih kecil, proses insertion berhasil. Jika lebih besar tukar value node baru dengan parentnya.
4.Lakukan terus langkah ini sampai Node memiliki parent yang mempunyai value lebih kecil darinya.
Deletion in Min Heap:
Tahap dalam melakukan Deletion Min Heap
1.Kita hanya bisa menghapus root node, oleh karena itu kita tinggal hapus root node lalu tukar dengan leaf node paling kanan
2.Setelah itu kita tinggal melakukan pembenaran, karena ini min heap, maka yang harus kita lakukan adalah mencari child dengan vaue paling kecil dan menukar valuenya dengan parentnya.
3.Lakukan langkah 2 terus menerus sampai Heap terbentuk dengan benar.
e.g. Delete(7)
2.Max Heap
Min heap adalah heap yang setiap node memiliki value parent lebih besar dari pada value nodenya.
Insertion in Max Heap:
Tahap dalam melakukan insertion Max Heap
1.Masukan node baru ke node yang masih memiliki tempat
2.Bandingkan node baru dengan parentnya
3.Jika value parent lebih besar, proses insertion berhasil. Jika lebih kecil tukar value node baru dengan parentnya.
4.Lakukan terus langkah ini sampai Node memiliki parent yang mempunyai value lebih besar darinya.
Deletion in Max Heap:
Tahap dalam melakukan Deletion Min Heap
1.Kita hanya bisa menghapus root node, oleh karena itu kita tinggal hapus root node lalu tukar dengan leaf node paling kanan
2.Setelah itu kita tinggal melakukan pembenaran, karena ini max heap, maka yang harus kita lakukan adalah mencari child dengan vaue paling besar dan menukar valuenya dengan parentnya.
3.Lakukan langkah 2 terus menerus sampai Heap terbentuk dengan benar.
Tries
Tries is an ordered tree data structure that is used to store an associative array(usually string). The trem tree comes form word Retrieval. 'cause tries can find a single word in a dictionary with only a prefix of the word.
Refferences:
- http://blog-arul.blogspot.com/2012/01/queue-pada-struktur-data.html
- http://blog-arul.blogspot.com/2012/01/stack-pada-struktur-data.html
- https://www.beritabebas.com/definisi/hashing/
- https://sourcecodegeneration.blogspot.com/2018/08/pengertian-binary-tree-binary-search.html
- https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/
- Binus Sources
- Jenny's lectures CS/IT NET & JRF(yt channel) --> she's the best ^^
Komentar
Posting Komentar