Heap & Tries Martin Leonardo Hermawan 2301873043

Heap

Heap adalah struktur data berbasis tree dimana tree itu adalah complete binary tree. Secara umum, ada 2 jenis heap yaitu:

1. Max Heap : kunci yang ada di simpul akar harus paling besar diantara kunci yang ada d semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua subtree di binary tree tersebut.
   
2. Min Heap : kunci yang ada di simpul akar harus minimum diantara kunci yang ada di semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua subtree di binary tree tersebut.
   

Selain 2 heap diatas ada juga max-min heap yaitu complete binary tree yang berisi level min (atau genap) dan maks (atau ganjul) secara bergantian. Level genap dilambangkan seperti 0, 2, 4, dll, dan level ganjil dilambangkan dengan 1, 3, 5, dll. Berikut ini contohnya

Insertion

Pertama, meningkatkan ukuran heap oleh 1, sehingga dapat menyimpan elemen baru. Masukkan elemen baru di akhir heap. Elemen yang baru diinsert ini dapat merusak heap. Jadi, untuk menjaga heap, dilakukan heapify elemen yang baru diinsert dengan cara bottom-up.

Illustration:

Suppose the Heap is a Max-Heap as:
      10
    /    \
   5      3
  / \
 2   4

The new element to be inserted is 15.

Process:
Step 1: Insert the new element at the end.
      10
    /    \
   5      3
  / \    /
 2   4  15

Step 2: Heapify the new element following bottom-up 
        approach.
-> 15 is more than its parent 3, swap them.
       10
    /    \
   5      15
  / \    /
 2   4  3

-> 15 is again more than its parent 10, swap them.
       15
    /    \
   5      10
  / \    /
 2   4  3

Therefore, the final heap after insertion is:
       15
    /    \
   5      10
  / \    /
 2   4  3

Deletion

Ganti root atau elemen yang akan dihapus oleh elemen terakhir. Hapus elemen terakhir dari heap. Karena, elemen terakhir sekarang ditempatkan pada posisi node root. Jadi, mungkin tidak mengikuti properti heap. Oleh karena itu, heapify simpul terakhir yang ditempatkan di posisi root.

Illustration:

Suppose the Heap is a Max-Heap as:
      10
    /    \
   5      3
  / \
 2   4

The element to be deleted is root, i.e. 10.

Process:
The last element is 4.

Step 1: Replace the last element with root, and delete it.
      4
    /    \
   5      3
  / 
 2   

Step 2: Heapify root.
Final Heap:
      5
    /    \
   4      3
  / 
 2   

Tries

Trie adalah struktur data pencarian yang efisien. Kompleksitas pencarian dapat dilakukan dengan bata optimal (panjang key). Jika kita menyimpan kunci dalam binary search tree, binary seach tree yang seimbang akan membutuhkan waktu yang sama dengan  M * log N, dimana M adalah panjang string maksimum dan N adalah jumlah key dalam tree. Dengan menggunakan trie, kita dapat mencari key dalam waktu O(M). Namun, ada persyaratan penyimpanan trie. Setiap simpul trie terdiri dari banyak cabang. Setiap cabang mewakili karakter key yang memungkinkan. Kita perlu menandai simpul terakhir dari setiap key sebagai simpul kata terakhir. Bidang simpul isEndOfWord digunakan untuk membedakan simpul tersebut sebagai simpul akhir kata.

AVL Tree Martin Leonardo Hermawan 2301873043

AVL Tree

AVL Tree adalah sebuah BST (Binary Search Tree) yang memiliki maksimal perbedaan tinggi level 1 antara subtree kiri dan subtree kanan. AVL Tree berguna untuk menyeimbangkan BST. Waktu pencarian yang dibutuhkan lebih sedikit dan bentuk tree akan terlihat lebih sederhana.

Contoh AVL Tree

Contoh yang bukan AVL Tree

Dapat dilihat subtree kiri dari node 76 ada 3 tetapi subtree kanannya 0 jadi perbedaan tinggi nya 3.

Insertion

Ada 4 kasus dalm insertion, yaitu :

• Jika ada ketidakseimbangan pada anak kiri subtree kanan, maka dilakukan rotasi kiri-kanan.
• Jika ada ketidakseimbangan pada anak kiri subtree kiri, maka dilakukan rotasi kanan.
• Jika ada ketidakseimbangan pada anak kanan subtree kanan, maka dilakukan rotasi kiri.
• Jika ada ketidakseimbangan pada anak kanan subtree kiri, maka dilakukan rotasi kanan-kiri.

Untuk menjaga tree tetap seimbang, setelah penambahan sebuah node, dilakukan pemeriksaan dari node baru ke root. Node pertama yang memiiki balance factor > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan 2 cara yaitu single rotation dan double rotation.

Single Rotation

Double Rotation

Deletion

Proses menghapus sebuah node AVL Tree hampir sama dengan BST. Penghapusan sebuah node dapat membuat sebuah tree menyadi tidak seimbang. Setelah menghapus sebuah node, lakukan pengecekan dari node yang dihapus ke root. Gunakan single rotation atau double rotation untuk menyeimbangkan node yang tidak imbang.

Summary Martin Leonardo Hermawan 2301873043

Summary

Linked List

Linked list atau senarai berantai adalah sebuah struktur data yang digunakan untuk meyimpan sejumlah objek data biasanya secara terurut sehingga operasi penambahan, pengurangan, dan pencari data yang tersimpan dapat dilakukan dengan lebih mudah tentunya lebih cepat. Dalam suatu linked list, pasti ada yang namanya head dan tail. Head adalah elemen yang berada pada posisi pertama suat linked, sedangkan tail adalah elemen yang berada pada posisi terakhir suatu linked list. Dalam linked list, selalu ada function push dan pop.
- Push
Push sendiri dibagi menjadi 3, yaitu :
Push head : untuk menginput data dari depan
Push tail : untuk menginput data dari belakang
Push mid : untuk menginput data ke tengah dan biasanya sudah sorted

- Pop
Pop juga dibagi 3, yaitu :
Pop head : untuk mendelete data paling depan
Pop tail : untuk mendelete data paling belakang
Pop : untuk mendelete data sesuai inputan user

Linked list sendiri memiliki 3 jenis yaitu single linked list, double linked list, dan circular linked list.

1. Single Linked List

Single linked list adalah sebuah linked list yang hanya memiliki satu buah pointer dan pointer tersebut hanya menunjuk ke node berikutnya. Oleh karena itu, biasanya tail menunjuk NULL.

Contoh :

2. Double Linked List

Double linked list adalah sebuah linked list yang memiliki 2 buah pointer. Pointer pertama menunjuk ke node berikutnya, sedangkan pointer kedua menunjuk ke node sebelumnya. Selain itu, setiap head dan tail juga menunjuk ke NULL.
Contoh :

3. Circular Linked List

Circular linked list adalah suatu single atau double linked list yang node terakhirnya menunjukk ke node awal, node awal menunjuk ke node terakhir. Oleh karena itu, linked list ini disebut circular karena seperti terus mengular atau berputar. Ada 2 jjenis circular linked list, yaitu single linked list dan double linked list
- Circular Single Linked List
   Contoh :

- Circular Double Linked List

   Contoh :

Stack and Queue

Stack

Stack adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linear. Kumpulan elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi atas. Konsep utama yang digunakan adalah LIFO.

Queue

Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan stack perbedaannya adalah operasi penambahan dan penghapusan apda ujung yang berbeda. Penghapusan dilakukan pada bagian depan dan penambahan berlaku pada bagian belakang.

Hashing

Hashing berasal dari kata hash yaitu suatu kode hasil enkripsi yang biasanya terdiri atas huruf ataupun angka yang acak. Hash berfungsi untuk mempercepat pencarian data misalnya dalam sebuah tabel data. Oleh karena itu, hashing digunakan untuk menyimpan data dalam sebuah array sehingga proses prnyimpanan, pencarian, penambahan, dan penghapusan data dapat dilakukan dengan cepat. Hashing juga dapat dikatakan transformasi aritmatik sebuah string karakter menjadi nilai yang merepresentasikan string aslinya. Ide dasar hashing adalah menghitung posisi record yang dicari dalam array. Fungsi yang digunakan adalah fungsi hash atau biasa disebut hash function. Array yang digunakan dalam hasing disebut hash table yang menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut.

Fungsi hash menyimpan nilai asli atau kunci pada alamat yang sama dengan nilai hashnya. Pertama, akan dilakukan penghitungan nilai hash dari kuncinya. Lalu, kunci dibandingkan dengan isi pada memori yang beralamatkan nomor hashnya. Oleh karena itu, fungsi ini dapat berjalan dengan cepat.

Hashing sangat berguna dalam blockchain, hash sangat berguna dalam memecahkan data yang terenkripsu untuk menyelesaikan perhitungan blockchain. Hash memiliki panjang yang tetap karena tidak mungkin seseorang menebak panjang hash untuk memecahkan blockchain.

Ada beberapa cara untuk mengubah string menjadi key dalam fungsi hash. Cara-cara tersebut adalah
1. Division
2. Multiplication
3. Mid Square
4. Folding
5. Digit Extraction
6. Rotating hash

Dalam hashing ada yang disebut collision, yaitu adanya tabrakan antara kunci hash dikarenakan adanya record yang memiliki key yang sama. Ada 2 cara untuk menyelesaikan collision, yaitu :
1. Linear Probing
2. Chaining

Binary Tree

Binary tree adalah sebuah pohon struktur data dimana setiap node memilki paling banyak dua cabang. Biasanya cabang-cabangnya disebut kiri dan kanan.

Ada 4 jenis binary tree, yaitu :

1. Perfect binary tree : binary tree dimana tiap level berada pada kedalaman yang sama

2. Complete binary tree : binary tree dimana tiap level semuanya terisi kecuali biasanya yang terakhir dan biasanya semua node berada di kiri.

3. Skewed binary tree : binary tree dimana setiap node paling banyak memiliki 1 cabang/anak

4. Balanced binary tree : binary tree dimana tidak ada daun yang lebih jauh dari akar daripada daun lainnya.

Binary tree selalu memiliki data, pointer untuk cabang kiri/anak kiri, dan pointer untuk cabang kanan/anak kanan.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};