Review Final

Nama : Indah Islamiana Sinurat
NIM : 2301906003
Kelas : CB01
Dosen :

• Ferdinand Ariandy Luwinda (D4522)
• Henry Chong (D4460)

AVL Tree

Apa itu AVL Tree? AVL Tree adalah sebuah tree yang sejenis dengan BST. AVL Tree memiliki perbedaan level antara node yang berada di atas ataupun di bawahnya dengan perbedaan minimum -1 dan perbedaan maksimum 1. Perbedaan ini berlaku untuk subtree node yang berada di kanan ataupun di kiri AVL Tree.

Apa sih guna AVL Tree? AVL Tree muncul untuk menyeimbangkan Binary Search Tree (BST), dengan adanya AVL Tree, proses pencarian yang akan kita lakukan (dalam bentuk tree) akan berlangsung/terproses lebih cepat dibandingkan dengan menggunakan BST.

AVL Tree terdiri atas deletion dan insertion.

Insertion

Kasus - kasus dimana harus dilakukan rotation pada saat ingin menambahkan suatu node baru/insert new node, yaitu:

Keterangan:

1. Pada kasus 1 dan kasus 2 akan dilakukan single rotation untuk menyeimbangkan node-node yang berada di dalam tree nya.
2. Pada kasus 3 dan kasus 4 akan dilakukan double rotation untuk menyeimbangkan node-node yang berada di dalam tree nya.

Single Rotation

Double Rotation

Deletion

Kasus dan cara pada saat ingin melakukan deletion:

1. Node yang ingin dihapus berada di leaf/berada di node paling bawah tree. Jika kasus ini terjadi pada saat kita ingin melakukan deletion, berarti kita hanya tinggal langsung menghapus node yang ingin kita hapus/delete tanpa melakukan pengecekan dan pembetulan letak agar node tersebut seimbang.
2. Node yang ingin dihapus berada di bagian tengah/bagian awal tree. Jika kasus ini terjadi pada saat kita ingin melakukan deletion, berarti kita harus menghapus node yang telah dipilih (yang ingin dihapus). Lalu apabila dia memiliki anak, kita harus mengganti node yang telah kita hapus dengan node yang berada di bawahnya.

Agar tidak bingung, mari kita lihat contoh deletion yang berada di bagian tengah tree...

Yang diinginkan adalah untuk menghapus node 60

(keadaan tree dimana node 60 sudah dihapus dan tree sudah seimbang)

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:



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:



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



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

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:

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:




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



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

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:

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 ^_^
Sampai ketemu di semester selanjutnya :)

Referensi :

1. http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html?m=1
2. https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/
3. https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/
4. Binus Maya Power Point
5. https://www.hackerearth.com/practice/data-structures/trees/heapspriority-queues/tutorial/
6. https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm
7. https://www.geeksforgeeks.org/deletion-binary-tree/
8. https://www.geeksforgeeks.org/insertion-and-deletion-in-heaps/
9. https://www.slideshare.net/HoangNguyen446/heaps-61679009
10. https://www.geeksforgeeks.org/trie-insert-and-search/
11. https://allcprogrammingandalgorithm.wordpress.com/heap-sort/
12. https://www.ques10.com/p/4168/sort-the-following-data-in-descending-order-usin-1/
13. https://stackoverflow.com/questions/14332279/delete-max-operation-in-a-min-max-heap