Tugas Data Sturcture

Heap dan Tries Heap Adalah complete binary tree yang berbasis struktur data dan memenuhi aturan heap. Tree pada heap and deap tidak memenuhi aturan BST yang harus terurut secara inorder, yang penting tree tersebut mengikuti aturan heap. Heap Terbagi menjadi 3 jenis: MIN HEAP TREE Adalah node yang parentnya lebih kecil dari anaknya tetapi parentnya lebih besar dari rootnya. Dapat disimpulkan bahwa root adalah bagian terkecil dari Min-Heap. Contoh: Cara Insert: a. Jika min heap(elemen terkecil terletak di root): a.         Masukkan data nya tidak seperti BST , melainkan dengan konsep array, sehingga kekanan terus, lalu kebawah, dst, atau bisa dikatakan bahwa elemen terakhir akan masuk ke index terakhir/menjadi anak paling kanan dan bawah. b.        Data yang diinsert kemudian dibandingkan dengan parentnya, jika lbh kecil maka swap, lakukan terus menerus sampai root atau sampai data baru tersebut lbh besar dr parentnya. c.         Implementasi dengan

AVL TREE AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru - > root. Node pertama yang memiliki balance factor >1 diseimbangkan. Proses penyeimbangan dilakukan dengan Single rotation dan Double rotation Single Rotation Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right Gambaran Single Rotation : Double Rotation Double rotasi (rotasi 2x) dilakukan apabila searah, left-right atau right-left. Gambaran Double Rotation : Step 1 (Rotasi pertama) kasus diatas adalah left-right Step 2 (Rotasi kedua) kasus diatas, left-left Cara menentukan Height dan Balance Factor :Note : Height : – Jika no