Nama : Muhamad Faqih
NIM : 2301887931
Kelas : CB01
Lecturer : Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460)
SUMMARY DATA STRUCTURE DARI PERTEMUAN AWAL
Linked List II
1. Circular single Linked list
Single linked list adalah satu variabel pointer untuk menyimpan data dengan metode linked list. Data disimpan ke dalam node, setiap node memiliki pointer untuk menunjuk ke node berikutnya. Nah, kalau Circular single linked list itu sama seperti single linked list tetapi setiap node awalnya menyambung dengan node akhir seperti lingkaran, selalu menyambung.
Ini adalah ilustrasi perbedaan single linked list (atas) dan circular single linked list(bawah)
2. Doubly linked list
Adalah Linked list yang mempunya dua pointer yaitu pointer prev dan next. Pointer prev digunakan untuk menunjukkan ke data sebelumnya dan sebaliknya kalau pointer next menunjukkan ke data selanjutnya
Contoh code untuk double linked list :
Insert pertama (Dari Depan)
Insert dari depan itu adalah penyisipan yang ada di awal, dan pointer head akan pindah ke elemen / data baru, contohnya:
Insert Terakhir (Dari Belakang)
Insert dari belakang itu adalah penyisipan yang ada di akhir, dan pointer tail akan pindah ke elemen / data baru, contohnya:
Delete satu node
Menghapus node apabila hanya ada satu node saja dapat menguunakan:
Delete Depan
Delete atau menghapus yang ada di awal list, pointer yang ada di head akan pindah ke data / elemen selanjutnya, contohnya :
Delete Akhir
Delete atau menghapus yang ada di akhir list, pointer yang ada di tail akan pindah ke data / elemen sebelumnya, contohnya :
Print
Untuk meperlihatkan atau print link listnya dapat dicontohkan sebagai berikut:
3. Circular Doubly Linked List
Doubly linked list yang mempunyai 3 field pointer, maksudnya seperti biasa doubly mempunyai pointer prev dan next tetapi kalau circular pointer prev dan nextnya selalu menunjuk ke dirinya sendiri sehingga membentuk circular atau selalu saling menyambung. Agar lebih mudah dimengerti dapat melihat Ilustrasi dibawah ini:
Pertemuan 2 linked list
Pada pertemuan kedua ini kami dijelaskan tentang linked list dan cara insert, dan juga menghapusnya serta dicontohkan untuk kodenya.
Biasanya di dalam linked list dimulai dengan membuat struct terlebih dahulu seperti berikut:
1. Insert
a. Insert dari depan (pushDepan)
Artinya data yang palling baru yang dimasukkan ada di depan data yang lain
Contoh kodenya adalah seperti berikut:
Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 7, 8, 9 dan anda ingin menginput dengan pushDepan satu data ‘10’ maka hasilnya menjadi 10, 7, 8, 9.
b. Insert dari belakang (pushBelakang)
Seperti pushDepan ini adalah kebalikannya, artinya data yang paling baru yang dimasukkan ada di belakang data yang lain.
Contoh kodenya adalah seperti berikut:
Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 7, 8, 9 dan anda ingin menginput dengan pushBelakang satu data ’10’ maka hasilnya menjadi 7, 8, 9, 10.
c. Insert dari tengah (pushTengah)
Seperti pushDepan dan pushBelakang, pushTengah yaitu data yang paling baru yang dimasukkan ada di tengah dari data yang lain.
Contoh kodenya adalah sebagai berikut :
Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 7, 8, 10, 11 dan anda ingin menginput dengan pushTengah satu data ‘9’ maka hasilnya menjadi 7, 8, 9, 10, 11.
2. Delete
a. Delete dari depan (popDepan)
Artinya data yang dihapus adalah data yang paling depan.
Contoh kodenya adalah seperti berikut:
Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 10, 7, 8, 9 dan anda ingin mendelete dengan popDepan maka hasilnya menjadi 7, 8, 9.
b. Delete dari belakang (popBelakang)
Ini merupakan kebalikan dari popdepan, artinya data yang paling belakang adalah data yang dihapus.
Contoh kodenya adalah seperti berikut:
Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 10, 7, 8, 9 dan anda ingin mendelete dengan popBelakang maka hasilnya menjadi 10, 7, 8.
-HASHING AND HASH TABLE, TREES AND BINARY TREE-
Hashing adalah sebuah teknik yang dibuat dengan bertujuan untuk membuat nilai kunci unik agar menjadi hasil yang lebih pendek dan kecil. Hashing dibuat menjadi pendek dan kecil agar mudah dicari dan juga dilokasikan.
Hash Table adalah Tabel yang dibuat dan diisi oleh kunci hash ( index di hash table) dan juga string aslinya (value di hash table). Hash table memiliki beberapa kelebihan salah satunya adalah agar lebih cepat untuk dicari dan lebih mudah untuk dilokasikan. Hash table juga juga dapat memiliki angka/key hash yang sama tetapi terkadang angka hash yang sama bisa juga menjadi menjadi tubrukan. Biasanya ini diatasi dengan membuat kebijakan untuk hash nya.
Contoh:
dibawah ini adalah list dari nama mahasiswa yang ada di kelas
Anton, Bella, Deni, Galih, Hasan.
dalam hash table yang huruf depannya ‘A’ akan mempunyai index 0, ‘B’ mempunyai index 1, ‘C’ mempunyai index 2, ‘D’ mempunyai index 3 dan seterusnya.
Maka tabel Hashnya akan menjadi seperti ini :
Function Hash : Banyak sekali cara untuk Hashing tetapi cara yang paling pentingnya ada 5 yaitu :
1. Mid-square
Mid square adalah metode hashing dengan mengkuadratkan nilai atau valuenya. Apabila itu string akan dikonversikan ke angka. Sesudah di kuadratkan akan di ambil nilai tengah dari hasil pangkatannya.
Contoh :
Nilai = 1234
Nilai 1234 dikuadratkan menjadi 1522756
Nilai tengah dari hasil kuadrat tersebut adalah 227. Inilah hasil dari Mid-Square Hashing.
2. Division
Division adalah metode hashing yang paling mudah dan juga metode yang paling terkenal. Caranya adalah dengan me-modulo.
Contoh :
Apabila dibuat tabel yang berisikan 10 dan ada 6 data yaitu 75, 16, 23, 62, 37, 21
Maka dengan division akan menjadi
75 mod 10 = 5 + 1 = 6. Maka data 75 akan dilokasikan ke 6
16 mod 10 = 6 + 1 = 7. Maka data 16 akan dilokasikan ke 7
23 mod 10 = 3 + 1 = 4. Maka data 23 akan dilokasikan ke 4
62 mod 10 = 2 + 1 = 3. Maka data 62 akan dilokasikan ke 3
37 mod 10 = 7 + 1 = 6. Maka data 37 akan dilokasikan ke 8
21 mod 10 = 1 + 1 = 6. Maka data 21 akan dilokasikan ke 2
3. Folding
Folding adalah metode hashing yaitu apabila kita mempunyai data, data akan di bagi 2 dan data yang kedua akan dibalik dan digabungkan dengan data yang pertama.
Contoh :
Ada data Nim mahasiswa yaitu: 235482, 415381, 654321
Maka:
235+284 = 519 maka data 235482 di lokasikan di 519
415+183 = 598 maka data 415381 di lokasikan di 598
654+123 = 777 maka data 654321 di lokasikan di 777
4. Digit Extraction
Digit Extraction adalah metode hashing yang men-ekstrak atau mengambil angka secara terpilih dari data.
Contoh :
Ada data Nim mahasiswa yaitu: 235482, 415381, 654321 dan yang diambil itu angka ke-1, ke-3, dan ke-6 maka:
235482 -> 252 maka data 235482 di lokasikan di 252
415381 -> 451 maka data 415381 di lokasikan di 451
654321 -> 641 maka data 654321 di lokasikan di 641
5. Rotating Hash
Rotating hash adalah metode hashing yang dapat menggunakan metode hashing lainnya sperti Digit Extraction atau Division dan memutarnya.
Contoh:
Apabila Hash yang sudah di division hasilnya 245638 maka hasil dari rotationnya adalah 836542
Collision
Collision adalah apabila nilai atau key-nya sama dan bertubrukan, cara menanggulanginya dapat dengan menggunakan Linear Probing atau Chaining
Linear Probing adalah apabila ada key hash yang sama maka akan ditempatkan di tempat index kosong yang terdekat
Chaining adalah apabila ada key hash yang sama maka akan ditempatkan disampingnya sehingga membentuk rantai atau Linked list
Trees & Binary Tree
Tree adalah kumpulan dari beberapa node yang dihubungkan oleh pointer. Apabila diibaratkan, node yang paling atas dan mempunyai cabang disebut Parent(root), dan node yang menyambung dengan parent disebut children. Garis yang mengubungkan antara parent dengan childrennya disebut edge. Node yang tidang menyambung lagi atau tidak mempunyai children disebut leaf. Node yang menyambung ke parent yang sama disebut sibling. Dibuat seperti pohon keluarga.
Binary tree adalah tree yang dipastikan hanya memiliki children paling banyak hanya 2. Biasanya anaknya dibedakan dengan right child dan left child. Node yang tidak memepunyai anak disebut leaf. Binary tree paling banyak sampai level 3 atau tingginya 3 tingkatan.
Binary tree juga memiliki beberapa tipe
1. Perfect binary tree
Yaitu binary tree yang mempunyai 2 children yang bercabang dan rata antara yang kanan dan yang kiri.
Contoh:
2. Complete Binary tree
Yaitu binary tree yang mempunyai 2 children tetapi salah satu dari cabang terakhirnya tidak ada dan sisanya terisi semua.
Contoh :
3.Skewed Binary Tree
Yaitu binary tree yang hanya mempunyai paling banyak satu anak.
Contoh:
4. Balenced Binary Tree
Yaitu binary tree yang leaf kanan tidak lebih jauh dari root dengan leaf kirinya sehingga balenced.
Contoh :
Expression Tree
Adalah Binary tree yang mempunyai cabang adalah operatornya dan yang tidak mepunyai cabang atau (leaf) adalah operan(angkanya).
Expression tree mempunyai Prefix, postfix dan infix.
Prefix adalah expression yang operator nya ada terlebih dahulu sebelum operannya.
Contoh : *+WX-YZ
Postfix adalah expression yang operatornya ada di belakang dari operannya.
Contoh : WX+YZ-*
Infix adalah expression yang operatornya beradi di tengah operannya.
Contoh : (W+X)*(Y-Z)
Threaded Binary Tree adalah binary tree tetapi mempunayi pointer yang NULL di kanan dan di kirinya. Ini mempunyai beberapa kelebihan seperti dapat mengunnakan linear traversal dan dapat mengurangi penggunaan stacks sehingga tidak memakan memory yang banyak. Tetapi Threaded binary tree juga memiliki kekurangan seperti lebih sulit untuk membuat binary treenya dan lebih sering mendapat error apabila tidak ada children-nya atau nodenya menunjuk kepada ancestornya.
Contoh Threaded Binary Tree:
Hash Table dalam Block chain dan apakah digunakan dalam blockchain sekarang : Hash table dapat digunakan dalam blockchain karena keduanya (hash table & blockchain) menggunakan data structure yang terdistribusi dan dapat digunakan di dalam blockchain. Tetapi blockchain dan hash table memiliki tujuan yang berbeda, blockchain bertujuan untuk menyediakan data structure yang tahan dengan kerusakan dan untuk menyimpan data yang makin banyak tanpa adanya gangguan atau kerusakan, sedangkan Hash table tujuan utamanya adalah memberikan data structure yang lebih efisien dengan arti lebih cepat dalam mencari dan tidak memakan memory yang besar.
Linkled list dengan double pointer : apabila menggunakan double pointer maka kalau kita ingin merubah head / memperbaharui list, tidak perlu untuk mengembalikan head-nya lagi sedangkan kalau single pointer harus mengembalikan head-nya lagi
Contoh code dengan double pointer:
Binary Search Tree atau biasanya disingkat menjadi BST itu adalah Struktur data Binary Tree yang mempunyai node dan yang berstruktur yaitu (Subtree kiri dan Subtree kanan harus binary tree):
- Subtree sebelah kiri hanya terdiri dari node yang lebih kecil dari parents dan rootnya
- Subtree sebelah kanan hanya terdiri dari node yang lebih besar dari parents dan rootnya
Binary Search Tree juga mempunyai kelebihan yaitu lebih cepat dama mencari, lebih cepat untuk sorting data dan juga lebih cepat dan lebih mudah untuk insert data dan delete data.
Berikut adalah contoh dari Binary search tree :
Didalam Binary Search Tree kita dapat melakukan Search, Insert dan juga delete:
Search:
Untuk search dalam Binary Search Tree, pertama-tama harus disamakan dengan root apabila nilainya sama dengan root maka return root-nya. Apabila nilai nya lebih besar daripada root maka cari di sebelah kanan dari Subtreenya, apabila lebih kecil daripada root-nya maka cari disebelah kiri dari rootnya.
Contoh codenya adalah sebagai berikut:
Insert:
Data baru yang di-insert selalu berada di leaf dalam binary tree. Sama seperti search, kita cari apabila datanya lebih kecil daripada root makacari secara recursive ke sebelah kiri dan apabila lebih besar maka kesebalah kanan. Setelah di search dan apabila sudah ketemu tempat yang memenuhi persyaratan maka data barunya menjadi leaf child dari nodenya.
Contoh codenya adalah sebagai berikut:
Delete:
Data yang ingin di-delete dapat berupa leaf, parent yang mempunyai satu child atau parent yang mempunyai dua child. Apabila yang ingin dihapus hanya leaf maka tinggal hapus saja, apabila ynag dihapus parent yang mempunyai satu child maka tinggal copy child-nya ke node dan hapus parentnya, dan apabila yang ingin dihapus parent yang mempunyai dua anak maka cari penerus dari parent tersebut setelah itu maka tinggal hapus dan replace dengan penerus dari parent yang sudah ditemukan
Contoh codenya adalah sebagai berikut:
LINKED LIST
1. Circular single Linked list
Single linked list adalah satu variabel pointer untuk menyimpan data dengan metode linked list. Data disimpan ke dalam node, setiap node memiliki pointer untuk menunjuk ke node berikutnya. Nah, kalau Circular single linked list itu sama seperti single linked list tetapi setiap node awalnya menyambung dengan node akhir seperti lingkaran, selalu menyambung.
Ini adalah ilustrasi perbedaan single linked list (atas) dan circular single linked list(bawah)
2. Doubly linked list
Adalah Linked list yang mempunya dua pointer yaitu pointer prev dan next. Pointer prev digunakan untuk menunjukkan ke data sebelumnya dan sebaliknya kalau pointer next menunjukkan ke data selanjutnya
Contoh code untuk double linked list :
Insert pertama (Dari Depan)
Insert dari depan itu adalah penyisipan yang ada di awal, dan pointer head akan pindah ke elemen / data baru, contohnya:
Insert Terakhir (Dari Belakang)
Insert dari belakang itu adalah penyisipan yang ada di akhir, dan pointer tail akan pindah ke elemen / data baru, contohnya:
Delete satu node
Menghapus node apabila hanya ada satu node saja dapat menguunakan:
Delete Depan
Delete atau menghapus yang ada di awal list, pointer yang ada di head akan pindah ke data / elemen selanjutnya, contohnya :
Delete Akhir
Delete atau menghapus yang ada di akhir list, pointer yang ada di tail akan pindah ke data / elemen sebelumnya, contohnya :
Print
Untuk meperlihatkan atau print link listnya dapat dicontohkan sebagai berikut:
3. Circular Doubly Linked List
Doubly linked list yang mempunyai 3 field pointer, maksudnya seperti biasa doubly mempunyai pointer prev dan next tetapi kalau circular pointer prev dan nextnya selalu menunjuk ke dirinya sendiri sehingga membentuk circular atau selalu saling menyambung. Agar lebih mudah dimengerti dapat melihat Ilustrasi dibawah ini:
Pada pertemuan kedua ini kami dijelaskan tentang linked list dan cara insert, dan juga menghapusnya serta dicontohkan untuk kodenya.
Biasanya di dalam linked list dimulai dengan membuat struct terlebih dahulu seperti berikut:
1. Insert
a. Insert dari depan (pushDepan)
Artinya data yang palling baru yang dimasukkan ada di depan data yang lain
Contoh kodenya adalah seperti berikut:
Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 7, 8, 9 dan anda ingin menginput dengan pushDepan satu data ‘10’ maka hasilnya menjadi 10, 7, 8, 9.
b. Insert dari belakang (pushBelakang)
Seperti pushDepan ini adalah kebalikannya, artinya data yang paling baru yang dimasukkan ada di belakang data yang lain.
Contoh kodenya adalah seperti berikut:
Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 7, 8, 9 dan anda ingin menginput dengan pushBelakang satu data ’10’ maka hasilnya menjadi 7, 8, 9, 10.
c. Insert dari tengah (pushTengah)
Seperti pushDepan dan pushBelakang, pushTengah yaitu data yang paling baru yang dimasukkan ada di tengah dari data yang lain.
Contoh kodenya adalah sebagai berikut :
Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 7, 8, 10, 11 dan anda ingin menginput dengan pushTengah satu data ‘9’ maka hasilnya menjadi 7, 8, 9, 10, 11.
2. Delete
a. Delete dari depan (popDepan)
Artinya data yang dihapus adalah data yang paling depan.
Contoh kodenya adalah seperti berikut:
Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 10, 7, 8, 9 dan anda ingin mendelete dengan popDepan maka hasilnya menjadi 7, 8, 9.
b. Delete dari belakang (popBelakang)
Ini merupakan kebalikan dari popdepan, artinya data yang paling belakang adalah data yang dihapus.
Contoh kodenya adalah seperti berikut:
Contoh kasus: apabila mepunyai sekumpulan data yang terdiri dari 10, 7, 8, 9 dan anda ingin mendelete dengan popBelakang maka hasilnya menjadi 10, 7, 8.
-HASHING AND HASH TABLE, TREES AND BINARY TREE-
Hashing adalah sebuah teknik yang dibuat dengan bertujuan untuk membuat nilai kunci unik agar menjadi hasil yang lebih pendek dan kecil. Hashing dibuat menjadi pendek dan kecil agar mudah dicari dan juga dilokasikan.
Hash Table adalah Tabel yang dibuat dan diisi oleh kunci hash ( index di hash table) dan juga string aslinya (value di hash table). Hash table memiliki beberapa kelebihan salah satunya adalah agar lebih cepat untuk dicari dan lebih mudah untuk dilokasikan. Hash table juga juga dapat memiliki angka/key hash yang sama tetapi terkadang angka hash yang sama bisa juga menjadi menjadi tubrukan. Biasanya ini diatasi dengan membuat kebijakan untuk hash nya.
Contoh:
dibawah ini adalah list dari nama mahasiswa yang ada di kelas
Anton, Bella, Deni, Galih, Hasan.
dalam hash table yang huruf depannya ‘A’ akan mempunyai index 0, ‘B’ mempunyai index 1, ‘C’ mempunyai index 2, ‘D’ mempunyai index 3 dan seterusnya.
Maka tabel Hashnya akan menjadi seperti ini :
Function Hash : Banyak sekali cara untuk Hashing tetapi cara yang paling pentingnya ada 5 yaitu :
1. Mid-square
Mid square adalah metode hashing dengan mengkuadratkan nilai atau valuenya. Apabila itu string akan dikonversikan ke angka. Sesudah di kuadratkan akan di ambil nilai tengah dari hasil pangkatannya.
Contoh :
Nilai = 1234
Nilai 1234 dikuadratkan menjadi 1522756
Nilai tengah dari hasil kuadrat tersebut adalah 227. Inilah hasil dari Mid-Square Hashing.
2. Division
Division adalah metode hashing yang paling mudah dan juga metode yang paling terkenal. Caranya adalah dengan me-modulo.
Contoh :
Apabila dibuat tabel yang berisikan 10 dan ada 6 data yaitu 75, 16, 23, 62, 37, 21
Maka dengan division akan menjadi
75 mod 10 = 5 + 1 = 6. Maka data 75 akan dilokasikan ke 6
16 mod 10 = 6 + 1 = 7. Maka data 16 akan dilokasikan ke 7
23 mod 10 = 3 + 1 = 4. Maka data 23 akan dilokasikan ke 4
62 mod 10 = 2 + 1 = 3. Maka data 62 akan dilokasikan ke 3
37 mod 10 = 7 + 1 = 6. Maka data 37 akan dilokasikan ke 8
21 mod 10 = 1 + 1 = 6. Maka data 21 akan dilokasikan ke 2
3. Folding
Folding adalah metode hashing yaitu apabila kita mempunyai data, data akan di bagi 2 dan data yang kedua akan dibalik dan digabungkan dengan data yang pertama.
Contoh :
Ada data Nim mahasiswa yaitu: 235482, 415381, 654321
Maka:
235+284 = 519 maka data 235482 di lokasikan di 519
415+183 = 598 maka data 415381 di lokasikan di 598
654+123 = 777 maka data 654321 di lokasikan di 777
4. Digit Extraction
Digit Extraction adalah metode hashing yang men-ekstrak atau mengambil angka secara terpilih dari data.
Contoh :
Ada data Nim mahasiswa yaitu: 235482, 415381, 654321 dan yang diambil itu angka ke-1, ke-3, dan ke-6 maka:
235482 -> 252 maka data 235482 di lokasikan di 252
415381 -> 451 maka data 415381 di lokasikan di 451
654321 -> 641 maka data 654321 di lokasikan di 641
5. Rotating Hash
Rotating hash adalah metode hashing yang dapat menggunakan metode hashing lainnya sperti Digit Extraction atau Division dan memutarnya.
Contoh:
Apabila Hash yang sudah di division hasilnya 245638 maka hasil dari rotationnya adalah 836542
Collision
Collision adalah apabila nilai atau key-nya sama dan bertubrukan, cara menanggulanginya dapat dengan menggunakan Linear Probing atau Chaining
Linear Probing adalah apabila ada key hash yang sama maka akan ditempatkan di tempat index kosong yang terdekat
Chaining adalah apabila ada key hash yang sama maka akan ditempatkan disampingnya sehingga membentuk rantai atau Linked list
Trees & Binary Tree
Tree adalah kumpulan dari beberapa node yang dihubungkan oleh pointer. Apabila diibaratkan, node yang paling atas dan mempunyai cabang disebut Parent(root), dan node yang menyambung dengan parent disebut children. Garis yang mengubungkan antara parent dengan childrennya disebut edge. Node yang tidang menyambung lagi atau tidak mempunyai children disebut leaf. Node yang menyambung ke parent yang sama disebut sibling. Dibuat seperti pohon keluarga.
Binary tree adalah tree yang dipastikan hanya memiliki children paling banyak hanya 2. Biasanya anaknya dibedakan dengan right child dan left child. Node yang tidak memepunyai anak disebut leaf. Binary tree paling banyak sampai level 3 atau tingginya 3 tingkatan.
Binary tree juga memiliki beberapa tipe
1. Perfect binary tree
Yaitu binary tree yang mempunyai 2 children yang bercabang dan rata antara yang kanan dan yang kiri.
Contoh:
2. Complete Binary tree
Yaitu binary tree yang mempunyai 2 children tetapi salah satu dari cabang terakhirnya tidak ada dan sisanya terisi semua.
Contoh :
3.Skewed Binary Tree
Yaitu binary tree yang hanya mempunyai paling banyak satu anak.
Contoh:
4. Balenced Binary Tree
Yaitu binary tree yang leaf kanan tidak lebih jauh dari root dengan leaf kirinya sehingga balenced.
Contoh :
Expression Tree
Adalah Binary tree yang mempunyai cabang adalah operatornya dan yang tidak mepunyai cabang atau (leaf) adalah operan(angkanya).
Expression tree mempunyai Prefix, postfix dan infix.
Prefix adalah expression yang operator nya ada terlebih dahulu sebelum operannya.
Contoh : *+WX-YZ
Postfix adalah expression yang operatornya ada di belakang dari operannya.
Contoh : WX+YZ-*
Infix adalah expression yang operatornya beradi di tengah operannya.
Contoh : (W+X)*(Y-Z)
Threaded Binary Tree adalah binary tree tetapi mempunayi pointer yang NULL di kanan dan di kirinya. Ini mempunyai beberapa kelebihan seperti dapat mengunnakan linear traversal dan dapat mengurangi penggunaan stacks sehingga tidak memakan memory yang banyak. Tetapi Threaded binary tree juga memiliki kekurangan seperti lebih sulit untuk membuat binary treenya dan lebih sering mendapat error apabila tidak ada children-nya atau nodenya menunjuk kepada ancestornya.
Contoh Threaded Binary Tree:
Hash Table dalam Block chain dan apakah digunakan dalam blockchain sekarang : Hash table dapat digunakan dalam blockchain karena keduanya (hash table & blockchain) menggunakan data structure yang terdistribusi dan dapat digunakan di dalam blockchain. Tetapi blockchain dan hash table memiliki tujuan yang berbeda, blockchain bertujuan untuk menyediakan data structure yang tahan dengan kerusakan dan untuk menyimpan data yang makin banyak tanpa adanya gangguan atau kerusakan, sedangkan Hash table tujuan utamanya adalah memberikan data structure yang lebih efisien dengan arti lebih cepat dalam mencari dan tidak memakan memory yang besar.
Linkled list dengan double pointer : apabila menggunakan double pointer maka kalau kita ingin merubah head / memperbaharui list, tidak perlu untuk mengembalikan head-nya lagi sedangkan kalau single pointer harus mengembalikan head-nya lagi
Contoh code dengan double pointer:
BST
Binary Search Tree atau biasanya disingkat menjadi BST itu adalah Struktur data Binary Tree yang mempunyai node dan yang berstruktur yaitu (Subtree kiri dan Subtree kanan harus binary tree):
- Subtree sebelah kiri hanya terdiri dari node yang lebih kecil dari parents dan rootnya
- Subtree sebelah kanan hanya terdiri dari node yang lebih besar dari parents dan rootnya
Binary Search Tree juga mempunyai kelebihan yaitu lebih cepat dama mencari, lebih cepat untuk sorting data dan juga lebih cepat dan lebih mudah untuk insert data dan delete data.
Berikut adalah contoh dari Binary search tree :
Didalam Binary Search Tree kita dapat melakukan Search, Insert dan juga delete:
Search:
Untuk search dalam Binary Search Tree, pertama-tama harus disamakan dengan root apabila nilainya sama dengan root maka return root-nya. Apabila nilai nya lebih besar daripada root maka cari di sebelah kanan dari Subtreenya, apabila lebih kecil daripada root-nya maka cari disebelah kiri dari rootnya.
Contoh codenya adalah sebagai berikut:
Insert:
Data baru yang di-insert selalu berada di leaf dalam binary tree. Sama seperti search, kita cari apabila datanya lebih kecil daripada root makacari secara recursive ke sebelah kiri dan apabila lebih besar maka kesebalah kanan. Setelah di search dan apabila sudah ketemu tempat yang memenuhi persyaratan maka data barunya menjadi leaf child dari nodenya.
Contoh codenya adalah sebagai berikut:
Delete:
Data yang ingin di-delete dapat berupa leaf, parent yang mempunyai satu child atau parent yang mempunyai dua child. Apabila yang ingin dihapus hanya leaf maka tinggal hapus saja, apabila ynag dihapus parent yang mempunyai satu child maka tinggal copy child-nya ke node dan hapus parentnya, dan apabila yang ingin dihapus parent yang mempunyai dua anak maka cari penerus dari parent tersebut setelah itu maka tinggal hapus dan replace dengan penerus dari parent yang sudah ditemukan
Contoh codenya adalah sebagai berikut:
AVL TREE
AVL Tree merupakan Binary Search Tree (BST) yang seimbang sehingga lebih cepat untuk mencarinya dibanding dengan BST. Didalam AVL keseimbangan haruslah sangat diperhatikan tiap node tidak boleh kurang dari -1 dan tidak boleh juga lebih dari 1. Cara menentukan apabila balance atau tidak adalah dengan jumlah bagian terpanjang sebelah kanan - bagian terpanjang sebelah kiri.
Berikut adalah Contoh AVL Tree:
Di AVL Tree setiap setelah melakukan Insertion atau deletion harus di cek kembali keseimbangan di dalam AVL Tree-nya, Apabila AVL Tree belum seimbang maka ada dua kemungkinan cara untuk menyeimbangkan Tree tersebut.
Yang pertama adalah dengan menggunakan Single Rotation
Dibawah ini adalah contoh AVL Tree yang tidak seimbang:
Karena yang bagian sebelah kiri – bagian sebelah kanan adalah 2 maka AVL Tree diatas belum lah seimbang dan AVL Tree diatas dapat diseimbangkan dengan menggunakan Single Rotaion sehingga hasilnya menjadi :
Di AV L Tree yang salah diatas setelah angka 50 dari bagian sebelah kiri dengan bagian sebalah kanan perbedaannya adalah 2 sehingga jika diselesaikan menggunakan single rotation angka 28 di tarik kekanan dan angka 50 nya juga ditarik kekanan agar seimbang. Untuk anak sebelah kanan dari angka 28 tadi akan di insert ulang dari atas sehingga menjadi anak sebelah kiri angka 50.
Untuk Single rotation kiri dan kanan (LL & RR) itu caranya sama seperti yang diatas perbedaannya adalah dalam LL Single Rotation setiap node atau angka bergerak satu posisi ke sebelah kiri dari posisi saat ini dan kalau RR Single Rotation setiap node atau angka bergerak satu posisi ke kanan dari posisi saat ini.
Cara yang kedua adalah dengan menggunakan Double Rotation
Diatas merupakan AVL Tree yang belum seimbang karena diangka 55 di bagian anak sebalah kanannya jika dikurang dengan anak disebelah kirinya merupakan 2 sehingga perlu diseimbangkan dengan menggunakan Double Rotation seperti berikut:
Langkah pertamanya adalah dengan menarik angka 58 sehingga anak dari angka 58 ketika di insert menjadi anak sebelah kiri dari angka 60, langkah yang keduanya adalah menarik lagi angka 58 sehingga angka 55 menjadi anak sebelah kiri dari angka 58 (cara mudah untuk menentukan letak anaknya adlaah dengan insert dari pusat teratas).
Dalam double rotation juga dapat dilakukan melalui Left Double rotation dan Right Double Rotation seperti namanya rebalancingnya dilakukan melalui sebelah kiri dan sebelah kanan.
Heap and Tries
Heap itu pada dasarnya adalah BST (Binary Search Tree) yang memenuhi psayarat dari properti heap. Heap juga dapat dibilang implementasi efisien dari tipe abstrak dengan antrian prioritas.
Ada 3 tipe heap, yaitu :
Min Heap
Dalam min heap, setiap node di atas lebih kecil dari pada childrennya. Contohnya seperti dibawah ini,
Untuk insert, urutannya selalu dari kiri baru ke kanan. Sebagai contoh apabila di insert angka 14 maka seperti dibawah ini,
Untuk deletion, nilai terakhir dinakkan ke atas dan melakukan heapifi apabila lebih kecil, sebagi contoh apabila root dihapus maka seperti ini,
Max Heap
Max hepa adalah kebalikan daripada min heap, Jadi node yang diatas lebih besar daripada childrennya, contohnya seperti berikut ini,
Untuk insert sama seperti min heap semuanya dimulai dari sebalah kiri, sebagai contoh apabila di insert angka 2 maka jadi seperti,
Untuk deletiosn juga sama seperti min heap jadi apabila di hapus rootnya maka angka terakhirnya naik menggantikan root dan heapifi apabila childrennya ada yang lebih besar. Sebagai contoh apabila root nya dihapus menjadi,
Min-Max Heap
Min max heap adalah gabungan dari min heap dan max heap, jadi bagian paling atas itu adalah min heap dan children dari min heap tersebut adalah max heap dan seterusnya.
Untuk insert min max heap dimulai dari sebelah kiri seperti biasa tetapi abis itu dilakukan heapifi agar urutannya tidak salah. Sebagai contoh apabila di insert angka 49 maka akan di cek ke grand parentnya apakah lebih besar atau tidak, karena 50 lebih besar dari 34 maka di tukar tempatnya. Karena tidak ada grand parent lagi maka sudah selesai. Contoh treenya seperti dibawah ini
Untuk delete sama seperti heap lainnya, apabila masih belum urut maka dilakukan heapifi. Jadi apabila kita ingin menghapus angka terbesar yaitu 49, maka angka terakhir yaitu 34 ditukar dengan 49. Karena sudah urut dan tidak merusak syarat dan properti min max heap maka sudah selesai. Jadi treenya menjadi seperti berikut ini,
Tries
Tries adalah tree yang digunakan untuk menyimpan set yang dinamis atau associative array, biasanya berupa string. Dapat lebih efektif dan juga efisien. Tries itu biasanya digunakan dalam game-game bubble words. Contoh tries adalah sebagai berikut,
Comments
Post a Comment