Chaca's Personal Blog

AVL Tree

20:41 cha 0

<div dir="ltr" style="text-align: left;" trbidi="on">
Halo, setelah beberapa lama tidak posting karena masa UTS. akhirnya tugas ini datang lagi. setelah 2 minggu UTS yg cukup berdarah-darah, akhirnya aku bisa menyelesaikan semua soal. gatau sih,bener banyak apa bonyok banyak yang penting udah lewat :) 
 
kali ini, kita bakalan bahas materi yang lebih advanced. kt akan membahas tentang AVL TREE. 
apa itu avl tree? 
 
sebuah pohon biner terurut yang dapat menyeimbangkan dirinya sendiri. Pada sebuah pohon AVL, tinggi dari dua anak sub pohon dari simpul apapun memiliki perbedaan paling besar 'satu'.  
 
AVL Tree ditemukan oleh Adelson-Velskii dan Landis 
 
Lookup, penyisipan (insertion), dan penghapusan (deletion) semuanya memerlukan O(logn) kali dalam kasus biasa dan kasus terburuk.  
 
Penambahan (additions) dan penghapusan membutuhkan pohon tersebut untuk menyeimbangkan kembali dirinya melalui rotasi pohon satu kali atau lebih. 
 
cara perurutannya yaitu sebelah kiri nilai yang paling rendah sedangkan sebelah kanan nilai paling besar dari nilai utamanya (root),left<root<right. 
 
Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu : 
 
anggap T adalah node yang harus diseimbangkan kembali 
 
– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left) 
 
– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right) 
 
– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left) 
 
– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right) 
 
Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi 
– dengan single rotation 
– Kasus 3 dan 4 dengan double rotation 
 
 
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiQQ-5508gvLbXSYixHVPFL6MP-rbiNrYnDOxsuFRmLOyryMrJ2212PtwlphQExU9g2olOqwZpmTpjLdZooiu0Jp-E2CZLsUO5Yh__QGQIVX163Rzs8G-92VjyX6gVdamgg0del4uDq-TzN/s1600/377px-Unbalanced_binary_tree.svg.png" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" data-original-height="377" data-original-width="377" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiQQ-5508gvLbXSYixHVPFL6MP-rbiNrYnDOxsuFRmLOyryMrJ2212PtwlphQExU9g2olOqwZpmTpjLdZooiu0Jp-E2CZLsUO5Yh__QGQIVX163Rzs8G-92VjyX6gVdamgg0del4uDq-TzN/s320/377px-Unbalanced_binary_tree.svg.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">ini adalah unbalanced tree.</td></tr>
</tbody></table>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9VpHDcZ-paGLNVA3VbCNpP-rQXWbAGmbZDmLslpKvyslq_MIHA8mUPUwLQpgUFuDQPA-8E1TIGZLkKM8IjLJJ0sZ5GtlA2ww3KZaIGEkR_4N-fK_kTq6aN0t-ysqLCSXAw0GyHrqt_T9N/s1600/377px-AVLtreef.svg.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="168" data-original-width="377" height="142" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9VpHDcZ-paGLNVA3VbCNpP-rQXWbAGmbZDmLslpKvyslq_MIHA8mUPUwLQpgUFuDQPA-8E1TIGZLkKM8IjLJJ0sZ5GtlA2ww3KZaIGEkR_4N-fK_kTq6aN0t-ysqLCSXAw0GyHrqt_T9N/s320/377px-AVLtreef.svg.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">setelah di rebalance menjadi AVL Tree</td></tr>
</tbody></table>
Ada 2 kasus yang biasanya terjadi saat operasi <em style="border: 0px; box-sizing: border-box; font-family: inherit; font-size: 16px; font-stretch: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;">delete dilakukan, yaitu :<main class="wp-content clear main-read the-640" style="box-sizing: border-box; clear: both; font-family: "Open Sans", Helvetica, Arial, sans-serif; font-size: 16px; margin: 0px auto; max-width: 100%; width: 640px;"></main> 
<div style="border: 0px; box-sizing: border-box; clear: both; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
 
– Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.</div>
<ul style="border: 0px; box-sizing: border-box; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; list-style: url("../images/css/bullet.png") none; margin: 0px 15px 24px; padding: 0px; vertical-align: baseline;">
<li style="border: 0px; box-sizing: border-box; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px 15px; overflow-wrap: break-word; padding: 0px; vertical-align: baseline;">Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.</li>
<li style="border: 0px; box-sizing: border-box; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px 15px; overflow-wrap: break-word; padding: 0px; vertical-align: baseline;">anggap T adalah node yang harus diseimbangkan kembali – Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left) – Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right) – Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left) – Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)<div style="border: 0px; box-sizing: border-box; clear: both; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
</div>
<div style="border: 0px; box-sizing: border-box; clear: both; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
<a href="https://socs.binus.ac.id/files/2017/05/vio-1.jpg" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; box-sizing: border-box; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;"><img alt="" class="aligncenter size-full wp-image-14730" height="116" src="https://socs.binus.ac.id/files/2017/05/vio-1.jpg" style="border: none; box-sizing: border-box; clear: both; display: block; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; height: auto; line-height: inherit; margin: 0px auto; max-width: 100%; padding: 0px; vertical-align: baseline;" width="451" /></a></div>
</li>
</ul>
<div style="border: 0px; box-sizing: border-box; clear: both; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
Berikut contoh dalam menghapus node AVL Tree, terdapat AVL Tree yang kemudian di hapus node 60. Dengan gambaran sebagai berikut :</div>
<div style="border: 0px; box-sizing: border-box; clear: both; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
<a href="https://socs.binus.ac.id/files/2017/05/vio-2.jpg" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; box-sizing: border-box; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;"><img alt="" class="aligncenter size-full wp-image-14731" height="180" src="https://socs.binus.ac.id/files/2017/05/vio-2.jpg" style="border: none; box-sizing: border-box; clear: both; display: block; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; height: auto; line-height: inherit; margin: 0px auto; max-width: 100%; padding: 0px; vertical-align: baseline;" width="378" /></a></div>
<div style="border: 0px; box-sizing: border-box; clear: both; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
Yang akan menggantikan posisi node 60 adalah node 55. Akan terjadi ketidak seimbangan. Dengan tampilan sebagai berikut :</div>
<div style="border: 0px; box-sizing: border-box; clear: both; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
<a href="https://socs.binus.ac.id/files/2017/05/vio-3.jpg" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; box-sizing: border-box; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;"><img alt="" class="aligncenter size-full wp-image-14732" height="167" src="https://socs.binus.ac.id/files/2017/05/vio-3.jpg" style="border: none; box-sizing: border-box; clear: both; display: block; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; height: auto; line-height: inherit; margin: 0px auto; max-width: 100%; padding: 0px; vertical-align: baseline;" width="349" /></a></div>
<div style="border: 0px; box-sizing: border-box; clear: both; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
Maka akan dilakukan <em style="border: 0px; box-sizing: border-box; font-family: inherit; font-stretch: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;">single rotation pada node 55 dengan kasus ketidak seimbangan pada kasus no. 2. Dengan tampilan setelah dilakukan single rotation sebagai berikut :</div>
<div style="border: 0px; box-sizing: border-box; clear: both; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
<a href="https://socs.binus.ac.id/files/2017/05/vio-4.jpg" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; box-sizing: border-box; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;"><img alt="" class="aligncenter size-full wp-image-14733" height="178" src="https://socs.binus.ac.id/files/2017/05/vio-4.jpg" style="border: none; box-sizing: border-box; clear: both; display: block; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; height: auto; line-height: inherit; margin: 0px auto; max-width: 100%; padding: 0px; vertical-align: baseline;" width="373" /></a></div>
<div style="border: 0px; box-sizing: border-box; clear: both; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
Ketika sudah dilakukan single rotation dan dilakukan kembali perbedaan tinggi / level maksimal 1 ternyata terdapat ketidak seimbangan yang terjadi. Sehingga diperlukan double rotation dengan kasus no. 4. Sehingga hasil dari rotasi yang dilakukan adalah sebagai berikut :</div>
<div style="border: 0px; box-sizing: border-box; clear: both; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
<a href="https://socs.binus.ac.id/files/2017/05/vio-5.jpg" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border: 0px; box-sizing: border-box; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;"><img alt="" class="aligncenter size-full wp-image-14734" height="183" src="https://socs.binus.ac.id/files/2017/05/vio-5.jpg" style="border: none; box-sizing: border-box; clear: both; display: block; font-family: inherit; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; height: auto; line-height: inherit; margin: 0px auto; max-width: 100%; padding: 0px; vertical-align: baseline;" width="248" /></a></div>
 
source : 
<a href="https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/">https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/</a> 
<a href="https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/">https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/</a> 
 </div>

SOCS AVL Tree

Halo, setelah beberapa lama tidak posting karena masa UTS. akhirnya tugas ini datang lagi. setelah 2 minggu UTS yg cukup berdarah-darah, ak...

Baca selengkapnya »

Summary

23:09 cha 0

<div dir="ltr" style="text-align: left;" trbidi="on">
pa sih itu Linked List? 
sederhananya adalah sebuah struktur data yang sangat dinamis di mana elemen dapat ditambahkan atau dihapus dari mana saja sesuka hati kita, Juga, setiap elemennya disebut node atau koleksi linear dari data dimana setiap node menunjuk pada node lain melalui pointer. 
 Pada semester sebelumnya, kita sudah belajar tentang pointer bukan? 
Tentunya teman-teman harus masih inget dong. 
 Nah, Pada linked list terdapat beberapa jenis tuh . kali ini spesial banget aku bakalan bahas tiga hal dibawah ini yaitu : 
<div style="line-height: 24px; margin-bottom: 0pt; margin-left: 0.5in; margin-top: 4.8pt; text-indent: -0.5in; unicode-bidi: embed; word-break: normal;">
1.Circular Single Linked List</div>
<div style="line-height: 24px; margin-bottom: 0pt; margin-left: 0.5in; margin-top: 4.8pt; text-indent: -0.5in; unicode-bidi: embed; word-break: normal;">
2.Doubly Linked List</div>
<div style="line-height: 24px; margin-bottom: 0pt; margin-left: 0.5in; margin-top: 4.8pt; text-indent: -0.5in; unicode-bidi: embed; word-break: normal;">
3.Circular Doubly Linked List</div>
<div style="line-height: 24px; margin-bottom: 0pt; margin-left: 0.5in; margin-top: 4.8pt; text-indent: -0.5in; unicode-bidi: embed; word-break: normal;">
mari kita bahas satu persatu! </div>
<div style="line-height: 24px; margin-bottom: 0pt; margin-left: 0.5in; margin-top: 4.8pt; text-indent: -0.5in; unicode-bidi: embed; word-break: normal;">
1. Circular single linked list</div>
<div style="line-height: 24px; margin-bottom: 0pt; margin-left: 0.5in; margin-top: 4.8pt; text-indent: -0.5in; unicode-bidi: embed; word-break: normal;">
Q : apa sih itu circular single linked list? </div>
<div style="line-height: 24px; margin-bottom: 0pt; margin-left: 0.5in; margin-top: 4.8pt; text-indent: -0.5in; unicode-bidi: embed; word-break: normal;">
A: Dari kata circular sebenarnya bisa langsung kita tahu bhwa linked list yang satu ini membentuk sebuah siklus nih. Artinya, simpul di awal dan akhirnya bersebelahan atau ismpul terakhir berisi pointer ke simpul pertama. Di linked list yang satu ini juga Tidak ada penyimpanan nilai NULL dalam list.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLw3oldA_e_R8nwsPNE-DuiQIDJVdjba08qTMTeR2s0ihJiK2iN_Ujp6sXQoALQ7gbyIiDR8rxRHufmRbWz4ptlsDY-PRs4u8eA9hhj1uYh-4s4b4mvMYun8zNu3wtH-0IlrkJZ8mFFtMH/s1600/circular-singly-linked-list.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="286" data-original-width="795" height="143" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLw3oldA_e_R8nwsPNE-DuiQIDJVdjba08qTMTeR2s0ihJiK2iN_Ujp6sXQoALQ7gbyIiDR8rxRHufmRbWz4ptlsDY-PRs4u8eA9hhj1uYh-4s4b4mvMYun8zNu3wtH-0IlrkJZ8mFFtMH/s400/circular-singly-linked-list.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 12.8px;">sumber :<a href="https://www.javatpoint.com/circular-singly-linked-list">https://www.javatpoint.com/circular-singly-linked-list</a></td></tr>
</tbody></table>
Dalam linked list ini kan sudah disebutkan tuh bisa ngapain aja, bisa nambahin atau menghapus. Nah aku bakalan sebutin apa aja yang bisa dilakuin sama linked list satu ini: 
<div>
<ol style="text-align: left;">
<li> Menambahkan diawal yaitu Menambahkan simpul ke circular singly linked list yang ditautkan sendiri di awal.</li>
<li>Menambahkan diakhir Menambahkan node ke circular singly linked listyang ditaukan di akhir</li>
<li>Penghapusan di awal. Menghapus simpul dari circular singly linked list yang ditautkan di awal. </li>
<li> Penghapusan di bagian akhir Menghapus simpul dari daftar tertaut tunggal melingkar di bagian akhir.</li>
<li> Pencarian Membandingkan setiap elemen dari simpul dengan item yang diberikan dan kembalikan lokasi di mana item tersebut ada dalam daftar jika tidak mengembalikan null.</li>
<li>Traversing Mengunjungi setiap elemen daftar setidaknya satu kali untuk melakukan beberapa operasi tertentu.</li>
</ol>
<div>
2.Doubly Linked List 
Q: Apa itu double linked list? apa bedanya sama double linked list? 
A : Iya bener banget! itu sama aja kok. Cuma beda penyebutan aja tuh hehehe. jadi , doubly/double linked list itu struktur data yang mempunyai dua tautan , satu yang merujuk kepada data setelahnya , satu lagi yang merujuk pada sebelumnya.  
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjrkULRaSqVHlSKIdp3I2f742oUWnYsoqYY8CYTupoYnLupIa1JFKkasrSe3OmlMaA0ClrzT-FjKy7KiSo1YLxLc_UFSRwZT6Gh_He9Zv63o7-1F1b8hWJPO9QLtEv0a23qHoErU3wARxRt/s1600/doubly-linked-list2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="202" data-original-width="703" height="114" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjrkULRaSqVHlSKIdp3I2f742oUWnYsoqYY8CYTupoYnLupIa1JFKkasrSe3OmlMaA0ClrzT-FjKy7KiSo1YLxLc_UFSRwZT6Gh_He9Zv63o7-1F1b8hWJPO9QLtEv0a23qHoErU3wARxRt/s400/doubly-linked-list2.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="font-size: 12.8px;">sumber : <a href="https://javatpoint.com/doubly-linked-list">https://javatpoint.com/doubly-linked-list</a></td></tr>
</tbody></table>
 
 
<ol style="text-align: left;">
<li> Penyisipan di awal Menambahkan simpul ke dalam Linked List di awal.</li>
<li> Penyisipan di akhir Menambahkan simpul ke Linked List  ke akhir. </li>
<li>Penyisipan setelah simpul yang ditentukan Menambahkan simpul ke dalam daftar tertaut setelah simpul yang ditentukan.</li>
<li> Penghapusan di awal.  Menghapus simpul dari awal daftar</li>
<li>Penghapusan di bagian akhir Menghapus simpul dari akhir daftar.</li>
<li> Penghapusan dibagian terten Menghapus node yang hadir tepat setelah node yang berisi data yang diberikan.</li>
<li> Pencarian/Searching Membandingkan setiap data node dengan item yang akan dicari dan mengembalikan lokasi item dalam daftar jika item yang ditemukan lain kembali nol.</li>
<li> Traversing Mengunjungi setiap node daftar setidaknya sekali untuk melakukan beberapa operasi tertentu seperti pencarian, pengurutan, tampilan, dll. Stack and Queue</li>
<li>Q :apa sih itu stack ?   
A: Sederhananya nih, stack adalah tumpukan. kalian pasti tau dong tumpukan piring atau tumpukan buku. Nah, jadi stack itu ya gitu. data yang bentuknya ditumpuk gitu. jadi data yang terakhir masuk, akan menjadi data yang pertama keluar. LIFO : Last in, Frist Out. 
Q: trus kalau Queue apa dong? 
A: nah, kalau si queue(bacanya Q ya buka kueue :) ) itu antrian. Semua pada tau dong apa itu antrian? ya ngantri aja. Jadi disini data yang pertama masuk juga menjadi data yang pertama keluar. FIFO : First In, First Out 
 
Pada Stack, menggunakan push Head dan PopHead Pada Queue , digunakan PushHead dan PopTail</li>
</ol>
<div>
Q: Apa itu Hash Table? 
A: sebuah Table(array) dimana kita menyimpan string. index dari table tersebut adalah tempat terisinya dan berisi value dari string tersebut. 
 penempatan value dari string yang akan ditempatkan di sebuah index berdasarkan cara berikut: 
misalkan: 
 h item = item % (size of table)    
mari kita asumsikan ukuran dari table = 11, maka  
 54 % 11 = 10   26 % 11 = 4    93 % 11 = 5   
17 % 11 = 6    77 % 11 = 0    31 % 11 = 9     
 
maka tempat yang akan diisi akan menjadi seperti ini : 
 <img alt="DAA Hash Tables" height="84" src="https://static.javatpoint.com/tutorial/daa/images/daa-hash-table.png" style="background-color: white; height: auto; max-width: 100%;" width="320" /> 
 Kenapa kita menggunakan Hash Table? 
<ol class="points" style="background-color: white;">
<li style="line-height: 21px; margin-top: 4px; padding: 0.2em;">jika U (Universe of keys) sangat  besar , meletakkan sebuat table T dari size [U] bisa saja tidak mungkin.</li>
<li style="line-height: 21px; margin-top: 4px; padding: 0.2em;">Penempatan k dari keys mungkin saja relatif kecil untuk U sehingga ruang untuk menggalokasikan memori untuk T akan terbuang.</li>
</ol>
Lalu, bagaimana jika dua buat string mempunyai value yang sama sehingga index yang perlu diletakkan juga sama? 
itu disebut collisions/tabrakan . 
Ada dua cara untuk menangani tabrakan tersebut: 
 Probing Linier 
Cari slot kosong berikutnya dan letakkan talinya di sana. 
 Chaining 
Masukkan string ke dalam slot sebagai daftar rantai (linked list). 
Binary Search Tree 
 Binary search tree disebut juga kelas pohon biner, di mana node diatur dalam urutan tertentu. 
nilai semua node di sub-pohon kiri kurang dari nilai root dan nilai semua node di sub-pohon kanan lebih besar atau sama dengan nilai root. 
Aturan ini akan diterapkan secara rekursif ke semua sub-pohon kiri dan kanan root. 
<img alt="Binary Search Tree" src="https://static.javatpoint.com/ds/images/binary-search-tree.png" /> 
 
 
ada beberapa operation yang bisa dilakukan di binary search tree , yaitu : 
1 Mencari di BST 
Mencari lokasi beberapa elemen tertentu dalam BST. 
 2.Penyisipan dalam BST  
Menambahkan elemen baru ke BST di lokasi yang sesuai sehingga properti BST tidak melanggar. 
3.Penghapusan dalam BST Menghapus beberapa node tertentu dari pohon pencarian biner. Namun, bisa ada berbagai kasus dalam penghapusan tergantung pada jumlah anak, yang dimiliki simpul. 
 
 
sekian untuk materi kali ini! 
sampai jumpa minggu depan~~ 
 
 
source: <a href="https://www.javatpoint.com/daa-hash-tables">https://www.javatpoint.com/</a></div>
</div>
</div>
</div>

SOCS Summary

pa sih itu Linked List? sederhananya adalah sebuah struktur data yang sangat dinamis di mana elemen dapat ditambahkan atau dihapus dar...

Baca selengkapnya »