Data Structure

Heap Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. Min-Heap Where the value of the root node is less than or equal to either of its children. Min-heap construction Algorithm 1. Create a new node at the end of the heap 2. Assign new value to the node. 3. Compare the value of this child node with its parent 4. if value of parents is more than child, then swap them 5. repeat step 3 & 4 until heap property holds Min-heap deletetion 1. Remove root node 2. Move last element of the last root to root 3. Compare the value of this child node with its parent 4. If the value is more than child, then swap them. 5. Repeat step 3 & 4 until heap property holds Max-Heap Where the value of the root node is greater than or equal to either of its children. Max-heap construction Algorithm 1. Create a new node at the end of the heap 2. Assign new value to the node. 3. Compar...

AVL Tree AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi 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 di persingkat dan lebih sederhana. contoh: subtree dari 12 yang sebelah kanan ada maksnya ada 2 dan di sebelah kiri maksnya ada 3 sehingga memiliki beda tinggi hanya 1. ini masih diperbolehkan karena beda tinggi hanya 1 Penambahan node di AVL Tree single rotation single rotation dilakukan bila kondisi AVL tree saat akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut. T1,T2, dan T3 adalah sub tree yang urutannya harus seperti demikian serta height-nya harus sama (>=0). double rotation Double rotation dilakukan bila kondisi AVL Tree saat akan ditambahkan node baru dan posisi node baru seperti pada gambar brikut. T1, T2, T3, dan T4 adalah subtree yang urutannya harus seperti demikian. Tinggi subtree T1 h...