Heaps and Tries

Heap and Trie

Heap

Heap adalah bentuk unik dari balanced binary tree dimana ia akan selalu melakukan pengecekan value node yang dimasukkan dengan parentnya. Sehingga diperoleh hasil yang rapi dan teratur.

Jenis-jenis heap dapat dibagi sesuai dengan value root dan childnya menjadi:
  • Min Heap
  • Max Heap
  • Min-max Heap

I. Min Heap

1.1. Min Heap Example (sumber: https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm)
Min Heap adalah bentuk dimana nilai root-nodenya akan menjadi yang terkecil dari semua node yang ada.

II. Max Heap

1.2. Max Heap Example (sumber: https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm)
Max Heap adalah bentuk dimana nilai root-nodenya akan menjadi yang terbesar dibandingkan dengan semua node yang ada.

III. Min-Max Heap
1.3 Min-Max Heap Example
Min-max Heap adalah gabungan dari Min Heap dan Max Heap. Height genap diisi minimal value, sedangkan height ganjil diisi maximal value atau sebaliknya. 

Trie

Trie adalah tree yang khusus diciptakan untuk menampung string-string keyword. Implementasinya dapat kita jumpai di autocorrect dan word suggestions. Trie menyimpan setiap character dalam keyword sebagai node-node yang saling berhubungan. Rootnya dikosongkan sebagai syarat utama Trie untuk memudahkan pencarian child-node keyword yang ada. Ia juga menggunakan isFinal untuk mengetahui apakah di node tersebut sudah terbentuk kata atau belum.
2.1. Trie Example (sumber: https://www.weheartswift.com/working-trie-data-structure-part-1/)

Comments

Post a Comment

Popular posts from this blog

AVL Tree

Image
Pendahuluan Binary Search Tree (BST) yang telah dipelajari selama ini masih memiliki kekurangan. Jika tree yang terbentuk berupa Skewed Tree, maka diperlukan pencarian sebanyak jumlah data yang ada (n). Untuk itu, kita akan menggunakan AVL Tree. AVL Tree merupakan subtipe dari Binary Search Tree. Fyi, AVL Tree diambil dari nama penemunya yaitu Adelson, Velskii dan Landis (sumber: https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/ ). Dengan adanya AVL Tree, maka pencarian yang dilakukan dapat dikurangi hingga berjumlah 2 log(n). Ciri-ciri Konsep tree :  https://linked-list-dikky.blogspot.com/2020/03/hashmap-and-binary-tree.html BST               :  https://binustreereview.blogspot.com/2020/03/binary-search-tree.html AVL Tree memiliki semua ciri yang dimiliki oleh Tree dan BST dengan satu tambahan ciri, yaitu: - Perbedaan tingkat (depth) dari subtree kiri dan kanan dari setiap node tidak bo...
Read more

Review Materi Data Structure

Image
Nama : Dikky Larson NIM   : 2301853930 Pada kesempatan kali ini , saya akan mereview apa yang saya telah dipelajari sejauh ini. Langsung saja kita bahas satu per satu topik mengenai data structure ini 😊. Linked List 1. Definisi 1.1.  Linked List  illustration - https://www.geeksforgeeks.org/wp-content/uploads/gq/2013/03/Linkedlist.png Linked List  merupakan sebuah metode penyimpanan koleksi secara dinamis ( dynamic collection ) yang digunakan untuk mempermudah penyisipan data diantara kumpulan data yang telah ada. Meski memiliki konsep yang mirip dengan  Array ,  Linked List  memiliki keuntungan dalam penyisipan dan pembuangan data dibandingkan  Array . Hanya saja, kelemahannya terletak pada cara mengakses data didalamnya. Pada konsep  Linked List , pengaksesan data didalamnya harus secara berurutan dari awal, hal ini dikarenakan linked list tidak mengenal indeks seperti  Array . Jika pada  Array ...
Read more