Final Review

<div dir="ltr" style="text-align: left;" trbidi="on"> <div class="MsoNormal" style="background-color: white; font-size: 15.84px; line-height: normal; margin-bottom: 0.0001pt;"> <span style="font-family: inherit;">Chrysanti Anastasya Silaban</span></div> <div class="MsoNormal" style="background-color: white; font-size: 15.84px; line-height: normal; margin-bottom: 0.0001pt;"> <span style="font-family: inherit;">2301877464</span></div> <div class="MsoNormal" style="background-color: white; font-size: 15.84px; line-height: normal; margin-bottom: 0.0001pt;"> <span style="font-family: inherit;">Kelas : CB01</span></div> <div class="MsoNormal" style="background-color: white; line-height: normal; margin-bottom: 0.0001pt;"> <span style="font-family: inherit; font-size: 15.84px;">Lecture : Henry Chong (D4460) dan <span style="background-color: transparent;">Ferdinand Ariandy Luwinda(</span><span style="background-color: transparent;">D4522)</span></span></div> <div class="MsoNormal" style="background-color: white; font-size: 15.84px; line-height: normal; margin-bottom: 0.0001pt;"> <span style="font-family: inherit;"><br /></span> <br /> <div style="font-size: medium;"> <span style="font-family: inherit;">apa itu avl tree?</span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><br /></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">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'. </span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><span style="font-family: "arial" , "helvetica" , sans-serif;"><br /></span><span style="font-family: "arial" , "helvetica" , sans-serif;">AVL Tree ditemukan oleh Adelson-Velskii dan Landis</span></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><br /></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">Lookup, penyisipan (insertion), dan penghapusan (deletion) semuanya memerlukan O(logn) kali dalam kasus biasa dan kasus terburuk. </span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><br /></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">Penambahan (additions) dan penghapusan membutuhkan pohon tersebut untuk menyeimbangkan kembali dirinya melalui rotasi pohon satu kali atau lebih.</span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><br /></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">cara perurutannya yaitu sebelah kiri nilai yang paling rendah sedangkan sebelah kanan nilai paling besar dari nilai utamanya (root),left<root<right.</span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><br /></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :</span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><span style="font-family: "arial" , "helvetica" , sans-serif;"><br /></span><span style="font-family: "arial" , "helvetica" , sans-serif;">anggap T adalah node yang harus diseimbangkan kembali</span></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><span style="font-family: "arial" , "helvetica" , sans-serif;"><br /></span><span style="font-family: "arial" , "helvetica" , sans-serif;">– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)</span></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><span style="font-family: "arial" , "helvetica" , sans-serif;"><br /></span><span style="font-family: "arial" , "helvetica" , sans-serif;">– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)</span></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><span style="font-family: "arial" , "helvetica" , sans-serif;"><br /></span><span style="font-family: "arial" , "helvetica" , sans-serif;">– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)</span></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><span style="font-family: "arial" , "helvetica" , sans-serif;"><br /></span><span style="font-family: "arial" , "helvetica" , sans-serif;">– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)</span></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><span style="font-family: "arial" , "helvetica" , sans-serif;"><br /></span><span style="font-family: "arial" , "helvetica" , sans-serif;">Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi</span></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">– dengan single rotation</span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">– Kasus 3 dan 4 dengan double rotation</span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><br /></span></div> <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;"><span style="color: black; font-family: inherit;"><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" /></span></a></td></tr> <tr><td class="tr-caption" style="font-size: 12.8px;"><span style="font-family: inherit;">ini adalah unbalanced tree.</span></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;"><span style="color: black; font-family: inherit;"><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" /></span></a></td></tr> <tr><td class="tr-caption" style="font-size: 12.8px;"><span style="font-family: inherit;">setelah di rebalance menjadi AVL Tree</span></td></tr> </tbody></table> <div style="font-size: medium;"> <span style="font-family: inherit;"><span style="font-style: inherit; font-weight: inherit;">A</span><span style="font-size: 16px; font-style: inherit; font-weight: inherit;">da 2 kasus yang biasanya terjadi saat operasi </span><em style="border: 0px; box-sizing: border-box; font-size: 16px; font-stretch: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;">delete</em><span style="font-size: 16px; font-style: inherit; font-weight: inherit;"> </span><span style="font-size: 16px; font-style: inherit; font-weight: inherit;">dilakukan, yaitu :</span><main class="wp-content clear main-read the-640" style="box-sizing: border-box; clear: both; font-size: 16px; margin: 0px auto; max-width: 100%; width: 640px;"></main></span></div> <div style="border: 0px; box-sizing: border-box; clear: both; font-size: medium; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;"> <span style="font-family: inherit;"><br /></span> <span style="font-family: inherit;">– Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.</span></div> <ul style="border: 0px; box-sizing: border-box; font-size: medium; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; list-style: url("about:blank") none; margin: 0px 15px 24px; padding: 0px; vertical-align: baseline;"> <li style="border: 0px; box-sizing: border-box; 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;"><span style="font-family: inherit;">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.</span></li> <li style="border: 0px; box-sizing: border-box; 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;"><span style="font-family: inherit;">anggap T adalah node yang harus diseimbangkan kembali<br style="box-sizing: border-box;" />– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)<br style="box-sizing: border-box;" />– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)<br style="box-sizing: border-box;" />– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)<br style="box-sizing: border-box;" />– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)</span><div style="border: 0px; box-sizing: border-box; clear: both; 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-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="border: 0px; box-sizing: border-box; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;"><span style="color: black; font-family: inherit;"><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-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" /></span></a></div> </li> </ul> <div style="border: 0px; box-sizing: border-box; clear: both; font-size: medium; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;"> <span style="font-family: inherit;">Berikut contoh dalam menghapus node AVL Tree, terdapat AVL Tree yang kemudian di hapus node 60. Dengan gambaran sebagai berikut :</span></div> <div style="border: 0px; box-sizing: border-box; clear: both; font-size: medium; 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="border: 0px; box-sizing: border-box; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;"><span style="color: black; font-family: inherit;"><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-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" /></span></a></div> <div style="border: 0px; box-sizing: border-box; clear: both; font-size: medium; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;"> <span style="font-family: inherit;">Yang akan menggantikan posisi node 60 adalah node 55. Akan terjadi ketidak seimbangan. Dengan tampilan sebagai berikut :</span></div> <div style="border: 0px; box-sizing: border-box; clear: both; font-size: medium; 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="border: 0px; box-sizing: border-box; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;"><span style="color: black; font-family: inherit;"><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-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" /></span></a></div> <div style="border: 0px; box-sizing: border-box; clear: both; font-size: medium; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;"> <span style="font-family: inherit;">Maka akan dilakukan <em style="border: 0px; box-sizing: border-box; font-stretch: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;">single rotation</em> pada node 55 dengan kasus ketidak seimbangan pada kasus no. 2. Dengan tampilan setelah dilakukan single rotation sebagai berikut :</span></div> <div style="border: 0px; box-sizing: border-box; clear: both; font-size: medium; 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="border: 0px; box-sizing: border-box; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;"><span style="color: black; font-family: inherit;"><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-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" /></span></a></div> <div style="border: 0px; box-sizing: border-box; clear: both; font-size: medium; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 27px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;"> <span style="font-family: inherit;">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 :</span></div> <div style="border: 0px; box-sizing: border-box; clear: both; font-size: medium; 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="border: 0px; box-sizing: border-box; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline;"><span style="color: black; font-family: inherit;"><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-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" /></span></a></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><br /></span></div> <h2 style="text-align: left;"> <span style="font-family: inherit;"> HEAP</span></h2> <div style="font-size: medium;"> <span style="font-family: inherit;">Nah, jadi guys Heap adalah complete binary tree (bukan binary search tree) yang mempunyai properties sebagai berikut:</span></div> <div style="font-size: medium;"> <span style="font-family: inherit;"><br /></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">Min Heap terdiri atas Setiap <b>node(parents)</b> lebih kecil dari masing-masing childnya</span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">Root merupakan node<b> paling kecil</b>, sedangkan node <b>terbesar</b> terletak pada leaf node</span></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://media.geeksforgeeks.org/wp-content/cdn-uploads/binaryheap.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><span style="font-family: inherit;"><img border="0" height="320" src="https://media.geeksforgeeks.org/wp-content/cdn-uploads/binaryheap.png" width="272" /></span></a></td></tr> <tr><td class="tr-caption" style="font-size: 12.8px;"><span style="font-family: inherit;">min heap</span></td></tr> </tbody></table> <div style="font-size: medium;"> <span style="font-family: inherit;"><br /></span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">Max Heap terdiri atas Setiap <b>node(parents)</b> lebih besar dari masing-masing childnya</span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">Root merupakan node <b>paling besar</b>, sedangkan node <b>terkecil</b> terletak pada leaf node</span></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://media.geeksforgeeks.org/wp-content/uploads/MaxHeap.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><span style="font-family: inherit;"><img alt="max-heap" border="0" src="https://media.geeksforgeeks.org/wp-content/uploads/MaxHeap.png" /></span></a></td></tr> <tr><td class="tr-caption" style="font-size: 12.8px;"><span style="font-family: inherit;">max heap</span></td></tr> </tbody></table> <div style="font-size: medium;"> <span style="font-family: inherit;">Setelah itu ada juga min-max heap.</span></div> <div style="font-size: medium;"> <span style="font-family: inherit;">Min-max heap adalah Heap dengan <u>Min heap pada level ganjil(1,3,5 dst)</u> dan <u>Max heap pada level genap(2,4,6,8,dst)</u></span><br /> <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;"><span style="font-family: inherit;"><img alt="Min-max heap - Wikipedia" src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/50/Min-max_heap.jpg/400px-Min-max_heap.jpg" style="margin-left: auto; margin-right: auto;" /></span></td></tr> <tr><td class="tr-caption" style="font-size: 12.8px;"><span style="font-family: inherit;">min max heap</span></td></tr> </tbody></table> <span style="font-family: inherit;"><br /></span> <span style="font-family: inherit;"><br /></span> <span style="font-family: inherit;"><br /></span> <span style="font-family: inherit;">Heap bisa diimplementasi dengan array maupun dengan linked list. Aplikasi heap merupakan menjadi berikut:</span><br /> <span style="font-family: inherit;"><br /></span> <u><span style="font-family: inherit;">Priority Queue</span></u><br /> <span style="font-family: inherit;"><br /></span> <br /> <ol style="text-align: left;"> <li><span style="font-family: inherit;">Selection algorithm</span></li> <li><span style="font-family: inherit;">Dijkstra's Algorithm</span></li> <li><span style="font-family: inherit;">Prim Algorithm</span></li> </ol> <span style="font-family: inherit;"><br /></span> <span style="font-family: inherit;">Implementasi heap memakai array yaitu Array dimulai menggunakan indeks ke 1</span><br /> <span style="font-family: inherit;">Rumus umum pelaksanaan heap dengan array (x adalah current node):</span><br /> <span style="font-family: inherit;"><br /></span> <br /> <ul style="text-align: left;"> <li><span style="font-family: inherit;">Parent(x): x/2</span></li> <li><span style="font-family: inherit;">Left-child(x): 2*x</span></li> <li><span style="font-family: inherit;">Right-Child(x): 2*x+1</span></li> </ul> <span style="font-family: inherit;"><br /></span> <br /> <h3 style="text-align: left;"> <b><span style="font-family: inherit;">Operasi pada Min Heap</span></b></h3> <div> <div> <ul style="text-align: left;"> <li><span style="font-family: inherit;">Find-Min</span></li> </ul> </div> <div> <span style="font-family: inherit;">Minimum node terletak pada root</span></div> <div> <ul style="text-align: left;"> <li><span style="font-family: inherit;">Insertion pada Min-heap</span></li> </ul> </div> <div> <span style="font-family: inherit;">Insert node selalu berurutan berdasarkan level paling rendah menggunakan urutan left ke right</span></div> <div> <span style="font-family: inherit;">New node selalu menjadi leaf node</span></div> <div> <span style="font-family: inherit;">Sesuikan sesuai heap properties secara rekursif</span></div> <div> <ul style="text-align: left;"> <li><span style="font-family: inherit;">Deletion-Min dalam Min-Heap</span></li> </ul> </div> <div> <span style="font-family: inherit;">Node yg dihapus selalu root karena merupakan node paling kecil, kemudian diganti dengan node yang paling terakhir di insert</span></div> <div> <span style="font-family: inherit;">Sesuaikan dengan heap properties secara rekursif</span></div> <h3 style="text-align: left;"> <span style="font-family: inherit;"> Operasi pada Max Heap</span></h3> <div> <span style="font-family: inherit;">Insertion dan deletion untuk Max heap, hanya saja disesuakan menggunakan properties Max-Heap</span></div> <div> <span style="font-family: inherit;"><br /></span></div> <div> <ul style="text-align: left;"> <li><span style="font-family: inherit;">Min-Max Heap</span></li> </ul> </div> <div> <span style="font-family: inherit;">Insert node sinkron urutan, lalu cek upheap lalu sesuaikan dengan properties level.</span></div> <div> <span style="font-family: inherit;">Umumnya dilakukan penyesuaian rekursif dengan urutan menjadi berikut:</span></div> <div> <ol style="text-align: left;"> <li><span style="font-family: inherit;">Parent</span></li> <li><span style="font-family: inherit;">Grand Parent</span></li> </ol> </div> <div> <ul style="text-align: left;"> <li><span style="font-family: inherit;">Deletion selalu dilakukan dalam root, kemudian sesuaikan menggunakan downheap sesuai properties</span></li> </ul> </div> <div> <span style="font-family: inherit;">Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebahai berikut:</span></div> <div> <ol style="text-align: left;"> <li><span style="font-family: inherit;">Grand child</span></li> <li><span style="font-family: inherit;">Child ( grand child disesuaikan menggunakan parentnya)</span></li> </ol> <h2 style="text-align: left;"> <span style="font-family: inherit;"> TRIES</span></h2> <div> <span style="font-family: inherit;">Trie adalah struktur data pencarian informasi yang efisien.</span></div> <div> <span style="font-family: inherit;"> Menggunakan Trie, kompleksitas pencarian dapat dibawa ke batas optimal (panjang kunci). Jika kita menyimpan kunci dalam BST, BST yang seimbang akan membutuhkan waktu yang proporsional dengan M * log N, di mana M adalah panjang string maksimum dan N adalah jumlah kunci dalam pohon. Dengan menggunakan Trie, kita dapat mencari kunci dalam waktu O (M).</span></div> <div> <span style="font-family: inherit;"><br /></span></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;"><span style="font-family: inherit;"><img height="400" src="https://media.geeksforgeeks.org/wp-content/cdn-uploads/Trie.png" style="margin-left: auto; margin-right: auto;" width="303" /></span></td></tr> <tr><td class="tr-caption" style="font-size: 12.8px;"><span style="font-family: inherit;">tries</span></td></tr> </tbody></table> <span style="font-family: inherit;"><br /></span> <br /> <div> <div> <span style="font-family: inherit;">Jadi kesimpulannya Tries adalah tree yang dilakukan buat menyimpan array asosiatif</span></div> <div> <span style="font-family: inherit;">Properties pada tries terdiri atas:</span></div> <div> <ol style="text-align: left;"> <li><span style="font-family: inherit;">Setiap vertex/node merepresentasikan satu huruf</span></li> <li><span style="font-family: inherit;">Root merepresentasikan karakter kosong</span></li> <li><span style="font-family: inherit;">Aplikasi pada trees adalah fitur auto-complete yg ada pada web-browser</span></li> </ol> <div> <span style="font-family: inherit;"><br /></span></div> </div> </div> </div> </div> <div> <span style="font-family: inherit;">SEKIAN DAN TERIMA KASIH</span></div> <div> <span style="font-family: inherit;"><br /></span></div> <span style="font-family: inherit;">credit:</span><br /> <span style="font-family: inherit;"><br /></span> <a href="https://www.geeksforgeeks.org/binary-heap/"><span style="font-family: inherit;">https://www.geeksforgeeks.org/binary-heap/</span></a><br /> <a href="https://en.wikipedia.org/wiki/Min-max_heap"><span style="font-family: inherit;">https://en.wikipedia.org/wiki/Min-max_heap</span></a><br /> <a href="https://www.geeksforgeeks.org/minimum-element-in-a-max-heap/"><span style="font-family: inherit;">https://www.geeksforgeeks.org/minimum-element-in-a-max-heap/</span></a><br /> <a href="https://www.geeksforgeeks.org/max-heap-in-java/"><span style="font-family: inherit;">https://www.geeksforgeeks.org/max-heap-in-java/</span></a><br /> <a href="https://www.geeksforgeeks.org/trie-insert-and-search/"><span style="font-family: inherit;">https://www.geeksforgeeks.org/trie-insert-and-search/</span></a></div> <div style="font-size: medium;"> <a href="https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/"><span style="color: black; font-family: inherit;">https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/</span></a></div> <div style="font-size: medium;"> <span style="color: black; font-family: inherit;"><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></span></div> <div> <br /></div> </div> </div>

SOCS Final Review

Chrysanti Anastasya Silaban 2301877464 Kelas : CB01 Lecture : Henry Chong (D4460) dan  Ferdinand Ariandy Luwinda( D4522) apa it...

Baca selengkapnya »