HEAP

Heap adalah salah satu bentuk binary tree.
Heap terdiri dari 2 jenis yaitu:

 1. Max Heap
  Heap yang rootnya adalah data yang paling maksimum.
          

2. Min Heap

Heap yang rootnya adalah data yang paling minimum.

Insert pada heap dilakukan dengan meletakkan data tempat terakhir sesuai complete binary tree. Lalu selanjutnya akan dibandingkan dengan parentnya. 

Untuk max heap, swap dilakukan saat newdata>parent. Ini akan dilakukan terus menerus keatas sampai newdata<parent. 

Untuk min heap, swap dilakukan saat newdata<parent. Ini akan dilakukan terus menerus keatas sampai newdata>parent.

Contoh:

Delete pada heap hanya dapat dilakukan pada root. Setelah dihapus kemudian root akan digantikan dengan data terakhir sesuai complete binary tree. 

Untuk max heap:

1. Jika leftchildren dan rightchildren > data maka bandingkan LC dengan RC, jika LC > RC maka swap data dengan LC, jika LC < RC maka swap data dengan RC.
2. Jika leftchildren > data dan rightchildren < data maka swap data dengan LC.
3. Jika leftchildren < data dan rightchildren > data maka swap data dengan RC.

Lakukan ke bawah berulang kali sampai leftchildren dan rightchildren < data.

Untuk min heap:

1. Jika leftchildren dan rightchildren < data maka bandingkan LC dengan RC, jika LC < RC maka swap data dengan LC, jika LC > RC maka swap data dengan RC.
2. Jika leftchildren < data dan rightchildren > data maka swap data dengan LC.
3. Jika leftchildren > data dan rightchildren < data maka swap data dengan RC.

Lakukan ke bawah berulang kali sampai leftchildren dan rightchildren > data.

Contoh:

AVL Tree

AVL Tree adalah binary tree yang memenuhi syarat minimal height atau ketinggian dari jumlah node yang ada. AVL Tree merupakan salah satu dari Balanced Search Tree.

Balanced Search Tree digunakan agar binary tree memiliki height terkecil sehingga bisa mempertahankan complexity-nya O(log n) dimana n adalah jumlah node.

Dalam AVL Tree terdapat yang namanya balance factor yang nantinya akan digunakan untuk menentukan perlu atau tidaknya rebalancing dilakukan. Balance factor (bf) dihitung dengan mengurangkan tinggi dari anak kiri dengan tinggi dari anak kanan.

Rebalancing dilakukan ketika pada suatu node terjadi violated, dimana bf (balance factor) bernilai lebih dari 1 atau kurang dari -1. 

Dapat dilihat dari contoh diatas, dengan adanya AVL Tree maka tinggi dari sebuah tree dapat diminimalisir. Pada awalnya tinggi tree tersebut 4 lalu berubah menjadi 3 jika dijadikan AVL tree, sehingga jika melakukan pencarian pada suatu node hanya perlu maksimal 3 step yang sebelumnya maksimal 4 step.