GSLC

Heap adalag binary tree lengkap yang berdasarkan struktur data dimana value key pada node nya diatur sedemikian rupa sehungga value key pada node anaknha tidak ada yang lebih besar dari value key node orang tuanya. Terdapat 2 macam heap : •    Min Heap Setiap elemen node lebih kecil dari anaknya •    Max Heap Setiap elemen node lebih besar dari anaknya MIN HEAP Setiap elemen node lebih kecil dari elemen anaknya. Element heap terbesar terleta di salah satu leaf node. Heap bisa diimplementasikan dengan linked-list, tetapi lebih mudah diimplementasikan dengan array. Contoh Min-Heap Aplikasi penggunaan Heap •    Priority Queue •    Selection Algorithm •    Dijkstra’s Algortihm •    Prim Algorithm •    Heap Sort Insertion di Min-Heap Menginput element baru di akhir heap. Membandingkan nilai node sekarang dengan nilai parent nya. Jika nilai node sekarang lebih kecil dari parent nya, tukar nilainya. Berhenti menukar jika nilai p

AVL Tree adalah binary search tree yang dapat menyeimbangkan dirinya sendiri. Tiap subtree kiri dan kanan memiliki perbedaan tinggi maksimal 1. Terdapat 2 operation pada AVL Tree, yaitu : Insertion Deletion Proses insertion pada AVL Tree sama halnya dengan insertion pada Binary Search Tree. Dimana Node baru diposisikan sebagai leaf. Rebalance pada AVL Tree dapat dilakukan dengan Single Rotation dan Double Rotation. Terdapat 4 kasus dalam proses rebalance AVL Tree Yang pertama, node terdalam terletak pada subtree kiri dari anak kiri T. Yang kedua, node terdalam terletak pada subtree kanan dari anak kanan T. Yang ketiga, node terdalam terletak pada subtree kanan dari anak kiri T. Yang keempat, node terdalam terletak pada subtree kiri dari anak kanan T. Untuk kasus 1&2 dapat diselesaikan dengan Single Rotation. Sedangkan, untuk kasus 3&4 dapat diselesaikan dengan Double Rotation. Contoh Single Rotation Contoh Double Rotation P