Posts

Heap

Image
Halo semuanya, setelah kita belajar macam-macam balancing tree (AVL Tree, Red Black Tree, dan B-Tree), maka sekarang kita akan belajar tree yang direpresentasikan dalam bentuk array, yaitu heap. Apa itu heap? Heap adalah salah satu varian dari binary tree, namun Ia memiliki prinsip dan aturan sebagai berikut: Heap adalah binary tree yang direpresentasikan dalam bentuk array. Untuk melakukan traverse node dari heap, kita tidak menggunakan cara recursive, namun menggunakan proses iteratif. Berikut ini adalah contoh gambar dari heap: Sumber:   https://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Max-Heap.svg/1200px-Max-Heap.svg.png Jika direpresentasikan dalam bentuk array, maka terlihat sebagai berikut: Index 0 1 2 3 4 5 6 7 8 Value 100 19 36 17 3 25 1 2 7 Catatan: Heap selalu berupa balanced binary tree. Heap ini memiliki 3 varian, yaitu...
Post a Comment
Read more

AVL Tree

Image
AVL Tree AVL Tree secara dasarnya sama seperti Binary Search Tree yang umumnya, namun tree ini memiliki perbedaan-perbedaan yang mendasar: Bisa dibilang bahwa tree ini hampir selalu berupa perfect binary tree. Hal ini terjadi karena AVL Tree mengoptimasi cabang-cabang anakannya sehingga cabangnya tidak terlalu ke kiri atau ke kanan Akibatnya, perbedaan ketinggian pada setiap cabang yang terdapat di tree ini tidak boleh lebih dari 1. Inilah yang kita sebut sebagai Balanced Binary Tree. Berikut ini adalah contoh perbandingan gambar AVL Tree dan yang bukan: Kiri – Bukan AVL Tree karena perbedaan ketinggian di node 8 dan 18 lebih dari 1, namun gambar kanan memenuhi persyaratan AVL Tree Sumber: https://www.geeksforgeeks.org/avl-tree-set-1-insertion/ Mengapa AVL Tree perlu dipakai? Bayangkan jika kita menggunakan binary search tree. Jika kita lihat, anakan yang lebih besar dari parentnya, maka nodenya ditaruh di kanan dan sebaliknya. Bagaimana jika data ya...
Post a Comment
Read more