Data Structure

Heap adalah struktur data “complete binary tree based” yang memenuhi heap property.  Property tersebut adalah:   Min Heap   Max Heap       Min Heap Setiap elemen node lebih kecil dari elemen children-nya. Ini menyiratkan bahwa elemen terkecil terletak di root tree. Elemen terbesar terletak di suatu tempat di salah satu leaves node. Heap dapat diimplementasikan menggunakan linked-list, tetapi jauh lebih mudah untuk mengimplementasikan heap using array. (Insertion) (Delete part 1) (Delete part 2)       Max Heap Setiap elemen Node lebih besar dari elemen children-nya. Ini menyiratkan bahwa elemen terbesar terletak di root tree. Max heap memiliki prinsip yang sama dengan min heap.      Min-Max Heap   Kondisi heap bergantian setiap level, setiap level berselang-seling antara minimum dan maksimum. ·          Setiap elemen pada level...

AVL tree adalah nama berasal dari dua penciptannya yaitu, G.M. Adelson-Veleskii and E.M. Landis. AVL tree adalah self-balancing binary search tree pertama yang pernah diciptakan. AVL tree digunakan untuk menyeimbangkan Binary Search Tree, untuk mempersingkat pencarian dan menyederhanakan bentuk tree. Contoh: Insertion di AVL Tree Insertion pada AVL tree adalah insertion biasa seperti yang digunakan pada binary search tree. Tetapi ini dapat menyebabkan pelanggaran pada properti AVL Tree. Setelah melakukan insertion biasa maka kita harus benarkan menjadi kondisi yang seimbang. Selanjutnya, kembalikan kondisi keseimbangan. Pertama, lacak jalur dari kunci baru menuju root. Untuk setiap node yang A lewati, periksa apakah ketinggian kiri A dan kanan A berbeda pada paling banyak 1. Jika ya, lanjutkan ke parent A. Jika Tidak, perbaiki sub pohon A baik dengan single rotation atau double rotation. Single Rotation Single rotation dilakukan jika searah (left-left atau right-ri...