Posts

Heap & Tries

Image
Heap Heap adalah data structure tree yang terdiri dari 3 properti heap, yaitu: 1. Min Heap: setiap node memiliki value yang lebih kecil dari childnya (value terkecil di root). 2. Max Heap: setiap node memiliki value yang lebih besar dari childnya (value terbesar di root). 3. Min-Max Heap: terdiri dari level dan setiap level memiliki heap yang berbeda. Heap biasa direpresentasikan dalam bentuk array sehingga lebih mudah di digunakan. Index array pada heap dimulai dari 1, dan setiap melakukan insert akan dimasukkan ke index paling akhir. Untuk mengetahui index dari parent, left child, dan right child digunakan: Parent(x) = x/ 2 left-child(x) = 2 * x right-child(x) = 2 * x + 1 Min Heap https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm Max Heap https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm Min-Max Heap https://www.google.com/url?sa=i&url=https%3A%2F%2Fstackoverflow.com%2Fques

AVL Tree

Image
AVL Tree AVL Tree adalah singkatan untuk Adelson-Velskii and Landis, AVL adalah bagian atau subtype dari Binary Search Tree (BST). Konsep AVL Tree adalah selisih dari height kiri dan kanan subtree tidak boleh lebih dari 1. AVL tree harus selalu balance, sehingga setiap melakukan operasi akan di cek selisih height kiri dan kanan subtree jika lebih dari 1 maka disebut violation. Berikut adalah contoh dari violation, jika dilihat height dari subtree kiri 17 adalah 2 dan subtree kananya 0 maka selisihnya 2 ( violation ). https://www.google.com/url?sa=i&url=http%3A%2F%2Fivansrarudiandi.blogspot.com%2F2016%2F05%2Favl-tree.html&psig=AOvVaw0u6xLhAVqqwO6eNKpO-PM4&ust=1588413552562000&source=images&cd=vfe&ved=0CAIQjRxqFwoTCMih2u6zkukCFQAAAAAdAAAAABAE AVL Tree Rotation Seperti yang telah saya katakan bahwa setiap operasi kita perlu mengecek balance nya, jika tidak balance maka kita harus membuatnya balance dengan operasi rotation. Terdapat 2 jenis rot

Summary of Data Structures

Image
Summary Yang saya pelajari pada mata kuliah Data Struct selama semester 2 ini adalah Singly Linked List, Doubly Linked List, Hash Table, Binary Tree, dan Binary Search Tree. Singly Linked List Adalah linked list yang hanya memiliki satu pointer menuju ke node selanjutnya. https://www.geeksforgeeks.org/data-structures/linked-list/ Circular Singly Linked List Adalah linked list dimana semua node terhubung oleh satu pointer next saja dan membentuk sebuah loop satu arah dan tidak memiliki NULL pada akhir dari node. Node mana saja bisa menjadi starting point karena dia hanya berhenti ketika node yang sama terulang.  https://static.javatpoint.com/ds/images/circular-singly-linked-list.png Implementasi singly linked list: struct Data{ int num; Data *next;  // pointer penunjuk node selanjutnya }*head, *tail;      // head sebagai penanda node pertama dan tail sebgai node paling ujung (terakhir) Operasi singly linked list: 1. Push Adalah memasukkan d