Final Review
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.
Insertion
Di dalam AVL Tree ketika melakukan insertion terdapat 2 metode yaitu Single Rotation dan Double Rotation.
Single Rotation(Insertion)
Double Rotation(Insertion)
Deletion
Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus. Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1, penyeimbangan BST bisa dilakukan setelah pengecekan, kita bisa menentukan menggunakan SIngle Rotation atau Double Rotation.Heap
Heap sort adalah sebuah metode sorting (pengurutan) angka pada sebuah array dengan cara menyerupai binary tree, yaitu dengan cara memvisualisasikan sebuah array menjadi sebuah binary tree yang nantinya pada binary tree tersebut nilai pada masing-masing index array akan diurutkan. Heap tree terbagi menjadi 2 jenis yaitu Max-Heap dan Min-Heap, dimana max-heap adalah kondisi heap tree yang memiliki nilai tertinggi berada di node root dan setiap child node memiliki nilai yang lebih kecil dari nilai yang dimiliki parent nodenya. Sedangkan pada min-heap adalah kondisi kebalikan dengan max-heap, pada min-heap nilai terkecil berada di node root dan setiap child node memiliki nilai yang lebih besar dari nilai yang dimiliki parent nodenya. Kemudian ada pula yang diberi nama Min-Max Heap yaitu min-heap dan max-heap levelnya saling bergantian pada treeMin Heap
Di dalam konsep Min Heap, node yang berada dibawahnya atau parent nilainya akan lebih kecil dibandingkan dengan node anaknya. Maka dapat disimpulkan node root merupakan node dengan nilai paling kecil , dan salah satu node dari leaf node merupakan node yang nilainya paling besar.
Max Heap
Konsep Max Heap hanya berbeda sedikit , perbedaannya hanya ada di node paling atas akan memiliki node dengan nilai terbesar dan salah satu node dari leaf node akan memiliki nilai yang terkecil.
Min-Max Heap
Konsep Min Max Heap adalah level root akan bernilai minimum, selanjutnya akan bernilai maximum, dan seterusnya. Nilai terkecil berada di root dan nilai terbesar berada di salah satu node pada level setelah root. Level min hanya dapat dibandingkan dengan level min, dan sebaliknya.
Komentar
Posting Komentar