Heap and Tries

Heaps & Tries

Heaps adalah Binary Tree yang terdiri dari 2 anak seperti layaknya BST namun memiliki 2 konsep yaitu :
- Max Heap
- Min Heap

Max Heap artinya nilai parent lebih besar dibandingkan dengan anaknya

Min Heap artinya nilai parent lebih kecil dibandingkan dengan anaknya

Heaps biasanya diimplementasikan di Array

seperti pada gambar dibawah ini:


Seperti pada gambar, heaps index dimulai dari 1 karena untuk mempermudah melakukan perhitungan sebuah lokasi nodenya

ini adalah rumus indexnya
Parent = x/2
L-Child = 2*x
R-Child = 2*x+1

untuk pencarian data terkecil di Min Heap sudah pasti terletak pada root
untuk pencarian data terbesar di Max Heap sudah pasti terletak pada root

Insertion
Min Heap : apabila pada tree di insert nilai yang kecil dibandingkan dengan parentnya, otomatis akan melakukan penukaran nilai child dengan parentnya, hal ini dilakukan secara terus menerus sampai bertemu parent yang nilainya lebih kecil dibandingkan yang di insert.

Max Heap : apabila pada tree di insert nilai yang besar dibandingkan dengan parentnya, otomatis akan melakukan penukaran nilai child dengan parentnya, hal ini dilakukan secara terus menerus sampai bertemu parent yang nilainya lebih besar dibandingkan yang di insert.

Mix Max Heap : Karena setiap level berbeda beda jenis heap, misalkan pada level 0 itu Min Heap, maka level 1 itu Max Heap, selanjutnya akan ditentukan dengan ganjil genap levelnya. bagaimana insertionnya ? sama seperti Min Heap dan Max Heap hanya saja terdapat perbedaan saat melakukan proses koding atau algorithmnya yaitu setiap mau mengecek antara nilai child dan parentnya, harus memperhatikan levelnya setiap bertemu level genap maka akan melakukan pengecekan insert Min Heap, dan jika bertemu level ganjil akan melakukan pengecekan insert Max Heap.

Deletion
Min Heap : saat mendelete akan mengambil element terakhir pada tree untuk menggantikan posisinya, lalu melakukan downheapmin yang berarti melakukan pengecekan ke anaknya apakah ada nilai yang lebih kecil dari nilai anaknya.

Max Heap : saat mendelete akan mengambil element terakhir pada tree untuk menggantikan posisinya, lalu melakukan downheapmax yang berarti melakukan pengecekan ke anaknya apakah ada nilai yang lebih besar dari nilai anaknya.

Min Max Heap :  saat mendelete akan mengambil element terakhir pada tree untuk menggantikan posisinya, lalu melakukan downheapmax/downheap min tergantung pada level berapa yang di delete.

Heap Complexity :
- Searching : O(1)
- Insert : O(log(n))
- Delete : O(log(n))

Applications of Heaps :
- Heap Sort
- Selection Algorithms
- Graph Algoriths

Tries, adalah tree yang setiap nodenya terdapat sebuah huruf, rootnya berisikan empty character


Gambar diatas adalah contoh dari Tries

Sekian penjelasan singkat tentang Heaps dan Tries.

avltree2

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 node (root) tidak memiliki subtree heightnya = 0
– Jika node adalah leaf, height =  1
– Jika internal node, maka height =  height tertinggi dari anak + 1

Balance Factor :
-selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.

AVL Tree Operations : Insertion

Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di insert.
Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
anggap T adalah node yang harus diseimbangkan kembali
– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

AVL Tree Operations : Deletion

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.

Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :

– 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.
• anggap T adalah node yang harus diseimbangkan kembali
  – Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
  – Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
  – Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
  – Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)