Senin, 11 Mei 2020

Heaps and Tries

Heap & Tries

Heap

Apa sih heap itu? Heap adalah sebuah binary tree komplit data structure yang memenuhi properti-properti dari heap itu sendiri. Node-node yang merupakan node dari heap terurut dengan urutan tertentu. Heap sendiri memiliki beberapa jenis, apa saja?

  1. Minimum Heap
  2. Maximum Heap
  3. Min-Max Heap
Pada dasarnya semua heap itu sama. Pembedanya hanya ada pada letak urutan node nya.

1. Minimum Heap

Urutan minimum heap ini yakni nilai node yang paling kecil berada di root nya. Sementara susunan node ke bawah nya itu berdasarkan besar-kecil nilai node nya. Node yang memiliki nilai paling besar/maximum pasti selalu berada di bagian leaf node tree ini. Bisa kita lihat pada gambar di bawah ini:

Max Heap Example

Gambar di atas menunjukkan bahwa nilai node yang menjadi root dari minimum heap ini merupakan node yang memiliki nilai terkecil di antara semua nilai node-node yang lainnya. Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika kita menggunakan array saat meng-implementasikannya.

Berikut adalah step simulasi dalam menyusunan minimum heap hingga urutannya benar:

enter image description here

Dibawah ini adalah step simulasi untuk insert new node ke dalam minimum heap:

Heaps

Dibawah ini adalah step simulasi untuk deletion node yang akan kita hapus pada minimum heap: 

Deletion in a Binary Tree - GeeksforGeeks

2. Maximum Heap

Pada dasarnya, bentuk dari maximum heap ini hampir sama dengan minimum heap, namun yang membedakannya terletak pada nilai node root dari treenya. Urutan maximum heap ini yakni nilai node yang paling besar berada di root nya. Sementara susunan node ke bawah nya itu berdasarkan besar-kecil nilai node nya. Node yang memiliki nilai paling kecil/minimum pasti selalu berada di bagian leaf node tree ini. Bisa kita lihat pada gambar di bawah ini:

Max Heap Example

Gambar di atas menunjukkan bahwa nilai node yang menjadi root dari maximum heap ini merupakan node yang memiliki nilai terbesar di antara semua nilai node-node yang lainnya. Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika kita menggunakan array saat meng-implementasikannya, sama seperti minimum heap.

Berikut adalah step simulasi dalam menyusunan maximum heap hingga urutannya benar:

enter image description here


Dibawah ini adalah step simulasi untuk insert new node ke dalam maximum heap:

Heap Sort | All C programming & Algorithm

Dibawah ini adalah step simulasi untuk deletion node yang akan kita hapus pada maximum heap: 

Sort the following data in descending order using Heap sort 20, 14, 50, 3,  5, 7, 11, 8, 12, 15 Show all the steps. Write an algorithm for heap sort.

3. Min-Max Heap

Pada dasarnya, bentuk dari min-max heap ini hampir sama dengan minimum dan maximum heap, namun yang membedakannya terletak pada nilai node root dari treenya. Urutan min-max heap ini yakni nilai node yang paling kecil berada di root nya. Sementara susunan node ke bawah nya itu adalah nilai maximum, minimum, maximum, minimum, dan seterusnya. Nilai node yang akan terletak di paling bawah dari tree ini tidak dapt kita tentukan secara pasti, bisa jadi nilai paling kecil atau nilai paling besar. Hal ini tergantung pada banyaknya data yang kita peroleh. Bisa kita lihat pada gambar di bawah ini:

Delete-max operation in a min-max heap - Stack Overflow
Pada min-max heap ini, nilainya akan terus bersilangan antara maksimum dan minimum nodenya. Secara keseluruhan bentuk insert dan deletion pada heap ini sama saja dengan minimum dan maximum heap. Namun, kita harus benar-benar teliti pada saat menyusun/menyelesaikan heap ini, karena sedikit tricky dan kita terkadang akan tertukar posisinya.

Tries

Apa itu tries? Tries adalah suatu struktur data tree terurut yang digunakan untuk menyimpan array asosiatif. Kalian pasti tahu auto correct dan auto complete yang ada di keypad android kalian kan? Yang pas kita baru ketik beberapa huruf udah muncul kata yang ingin kita ketik ataupun yang bisa membenarkan kata kita apabila ada typo? Nah itu menggunakan tries ini.

Istilah TRIES berasal dari kata RETRIEVAL.

Fakta-Fakta Tentang Tries
  • Tries adalah tree yang setiap simpulnya mewakili satu kata atau awalan dari sebuah kata.
  • Root mewakili karakter kosong(" ") atau NULL.
Untuk lebih lanjut silahkan di lihat dan cermati gambar Tries dibawah....



Secara umum, penyusunan dari tries cukup simple dan mudah, kalian hanya tinggal melihat huruf pertama dari kata yang ingin kalian masukkan, apabila sudah ada huruf dari awalan kata kalian, maka selanjutnya kalian harus memeriksa huruf selanjutnya. Jika tidak ada lagi huruf yang sama, maka kalian tinggal memasukkan sisa huruf dari kata kalian di bawah huruf terakhir. Cukup simple dan mudah bukan?

Sekian...
Terima kasih ^_^



Referensi :

Review Final

Nama : Indah Islamiana Sinurat NIM : 2301906003 Kelas : CB01 Dosen : Ferdinand Ariandy Luwinda (D4522) Henry Chong (D4460) AVL T...