Heap and tries

Heap

Heap adalah pohon complete binary tree biner yang berdasarkan memenuhi properti heap. Property heaps antara lain :

• Min Heap
• Setiap node lebih kecil dari masing-masing childnya
• Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node

• Max Heap
• Setiap node lebih besar dari masing-masing childnya
• Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node

• Min-Max Heap
• Heap dengan Min heap pada level ganjil dan Max heap pada level genap

Heap dapat diimplementasi dengan array maupun dengan linked list. Aplikasi heap adalah sebagai berikut:

• Priority Queue
• Selection algorithm
• Dijkstra's Algorithm
• Prim Algorithm

Implementasi heap menggunakan array :

1. Array dimulai dengan indeks ke 1
2. Rumus umum aplikasi heap dengan array (x adalah current node):
1. Parent(x): x/2
2. Left-child(x): 2*x
3. Right-Child(x): 2*x+1
4. Min Head
3. Find-Min
4. Minimum node terletak pada root
5. Insertion pada Min-heap
6. Insert node selalu berurutan dari level paling rendah dengan urutan left ke right
7. New node selalu menjadi leaf node
8. Sesuikan sesuai heap properties secara rekursif

• Deletion-Min pada Min-Heap
• Node yang dihapus selalu root karena merupakan node paling kecil, lalu diganti dengan node yang paling terakhir di insert
• Sesuaikan dengan heap properties secara rekursif

• Max Heap
• Insertion dan deletion untuk Max heap, hanya saja disesuakan dengan properties Max-Heap

• Min-Max Heap

1. Insert node sesuai urutan, lalu cek upheap lalu sesuaikan dengan properties level.
2. Umumnya dilakukan penyesuaian rekursif dengan urutan sebagai berikut:
3. Parent
4. Grand Parent
5. Deletion selalu dilakukan pada root, lalu sesuaikan dengan downheap sesuai properties
6. Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebahai berikut:
7. Grand child
8. Child ( grand child disesuaikan dengan parentnya)

Tries

• Tries adalah tree yang dilakukan untuk menyimpan array asosiatif.
• Properties pada tries: 

- Setiap vertex/node merepresentasikan satu huruf.

- Root merepresentasikan karakter kosong.

Aplikasi pada trees adalah fitur auto-complete yang ada pada web-browser

AVL Tree

AVL Tree dinamai menurut 2 penemunya yaitu G.M. Adelson Veleskii and E.M. Landis. AVLtree adalah binary search tree (BST) yang secara otomatis menyeimbangka tangan kiri dan tangan kanan. Perbedaan tinggi antara tangan kanan dan tangan kiri dari AVL tree tidak boleh lebih dari satu untuk semua node.
Operas yang terdapat dalam AVL Tree  :

I. 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)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
- Kasus 1 dan 2 dengan single rotation
- Kasus 3 dan 4 dengan double rotation

->Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right

pada contoh diatas, left-left karena dari 30 ke 22 ke kiri, dan dari 22 ke 15 ke kiri juga

->Double rotasi (rotasi 2x) dilakukan apabila searah, left-right atau right-left.

Step 1 (Rotasi pertama)

kasus diatas adalah left-right

Step 2 (Rotasi kedua)

kasus diatas, left-left

II. 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.

delete node 60

node 55 tidak seimbang, karena anak kiri 0 dan anak kanan 2, selisih 2.

diseimbangkan dengan single rotation (left-left) karena 55 ke 65 kiri dan 65 ke 70 kiri

akan tetapi, node 50 menjadi tidak seimbang, di subtree kiri 4 dan subtree kanan 2

diseimbangkan dengan double rotation (left-right) karena dari 50 ke 25 kiri dan 25 ke 40 kanan

AVL yang sudah balance