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

Summary

Linked List merupakan sebuah data struktur namun disimpan di memori yang acak. Elemen dari linked list dihubungkan menggunakan pointer.
Keuntungan :
1) Linked list menggunakan ukarn yang dinamis.
2) Linked list mudah untuk dihapus maupun ditambahkan.
3) Penggunaan memor inke list dapat disesaikan secara dinamis.
Kekurangan : 
1)Linked List menggunakan memory lebih besar.
2)Proses mengakses lebih panjang karena tidak bisa langsung mengakses data dengan indeks, hars diakes dari linked list yang paling besar.

Untuk menggunakan linked list diperlukan memory allocation.

Linked List memunyai dua tipe, yaitu:
- Single link list
Single linked list terdiri dari:
1) current data
2) Pointer ke next node.
Dalam bahasa C, node dapat diiplementasikan menggunakan structure. contoh :
- Double link list
Double Linked List mempunyai pointer tambahan,yaitu, prev yang bersatu dengan pointer next dan data yang ada di dalam single linked list.
Dalam linked list, kita mengenal  2 istilah yaitu, push dan pop. push merupakan fungsi untuk memasukan data kedalam linked list. sedangkan pop adalah fungsi untuk menghapus data dalam suatu linked list.
Untuk membuat suatu linked list, kita membutuhkan 3 pointer yaitu :
1. Head : awal dari suatu linked list,
2. Current : data yang sedang/akan kita olah,
3. Tail : akhir dar suatu linked list.

Push 
Push merupakan suatu fungsi untuk menambahkan pumya sata pada linked list yang kita punya. Push dapat dilakukan dari depan (push head), belakang(push tail), atau tengah(push mid). Saat kita menstruct data, kita harus membuat pointer di dalam struct, yaitu 1 pointer untuk single linked list, dan 2 pointer untuk double linked list.

Pop
Pop merupakan fungsi untuk menghapus data dalam suatu linked list. Push dapat dilakukan dari depan (push head), belakang(push tail), atau tengah(push mid). setelah kita melakukan menghapus, kita harus free untuk menghapus malloc yang telah kita lakukan, karena jika kita tidak free data akan terus mengambil tempat tanpa bisa di akses.

contoh coding:

Hashing

Ide utama dari hashing adalah mengubah suatu string menjadi suatu bilangan dengan suatu fungsi.Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai key yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.



Hash Function

Ada banyak cara untuk hash sebuah string menjadi sebuah key. berikut cara penting untuk membuat sebuah hash function:

Mid Square
Kuadratkan string/identifier, lalu kita mengambil angka tengah dari kuadrat identifier sebagai hash key.

Function : h(k) = s

k = key, s = hash key yang didapatkan dari mengambil tengah dari k^2

Division
 String/identifier dibagi dengan menggunakan modulus.

Function : h(z) = z mod M

z = key, M = angka yang digunakan untuk membagi key (biasanya menggunakan angka prima)

Folding
Langkah :

• bagi key value menjadi beberapa bagian
• jumlahkan bagian individal(usually last carry is ignored)

Digit Extraction
Beberapa bagian digit dari angka dijadikan sebagai hash address.
Contoh :
x=14568. Jika kita Mengambil angka ke 1,3, dan 5, kita akan mendapatkan hashcode : 158.

Rotating hash
Gunakan hash mehod apa saja, lalu kita balik(angka perama menjad angka terakhir, dst.


Hashing table didalam block chain digunakan untuk  cryptocurrencies, yaitu sebuah teknologi membuat mata uang digital. Teknologi ini menggunakan kriptografi untuk keamanan yang membuatnya tidak dapat dipalsukan. transaksi dengan panjang bervariasi dijalankan melalui algoritma hashing yang diberikan, dan menghaslkan output dengan panjang yang tetap terlepas dari panjang transaksi input. Output adalah sebuah hash.


Tree dan binary tree

Tree adalah non linear data sructure yang mempunyai tingkatan dari data objek. seperti struktur organisasi, dll. data diubungkan dengan pointer.


Tree concept :

Root : Node di paling atas
Edge: Garis yang menghubungkan parent dengan child
Leaf: node yang tidak mempunyai anak
Siblings: node yang mempnyai parent yang sama
Degree: total subtree dari sebuah node
Height/depth: maksimum degree dari sebuah tree
jika ada garis yang menghubungkan p kepada q, p disebut ancestor dari q dan q adalah descendant dari p.

Binary Tree adalah Tree yang hanya memiliki maksimal 2 anak.
Binary search tree merupakan binary tree yang sudah tersortir. Kebanyakan Binary Search Tree menggunakan konsep untuk angka lebih kecil berada di sebelah kiri dan angka lebih besar berada di sebelah kanan.
Binary Search Tree mempuyai beberapa operasi dasar yaitu :
•>Find : Fungsi untuk mencari angka di dalam sebuah Binary Search Tree. Dilakukan dengan fungsi rekrusif dari root sampai meneukan angka yang kita inginkan. Konsepnya adalah dimulai dari root, jika root merupakan angka yang kita cari, return root. Jika angka yang kita cari lebih kecildaripada root, rekrusive fungsi ke subtree sebelah kiri. Jika angka yang kita cari lebih besar dari root, rekrusive fungsi ke subtree sebelah kanan.

•> Insert : Fungsi untuk menambahkan suatu node dari sebuah Binary Search Tree. Dilakukan dengan fungsi rekursif dari root dan key yang akan dimasukkan. Konsepnya adalah dimulai dari root jika key lebih kecil dari root maka, akan berpindah ke subtree sebelah kiri root dan jika lebih besar dari subtree sebelah kiri root maka, akan berpindah ke subtree sebelah kanan dari subtree sebelah kanan root dan jika lebih kecil dari subtree sebelah kiri root maka, akan berpindah ke subtree sebelah kiri dari subtree sebelah kiri root. Jika berpindah ke elemen yang masih kosong maka akan dipush kedalam tree.

•> Remove : Fungsi untuk menghapus suatu node dari sebuah Binary Search Tree. Dilakukan dengan mencari data yang akan dihapus dalam tree. Jika sudah dihapus maka, yang akan menggantikan data yang dihapus adalah:
1. Jika data yang dihapus adalah parent dengan single children maka, yang akan menggantikannya adalah childrennya.
2. Jika data yang dihapus adalah leaf maka, langsung dihapus saja.
3. Jika data yang dihapus adalah parent dengan 2 children maka, yang akan menggantikannya adalah subtree sebelah kanan nya yang paling kiri atau subtree sebelah kiri yang paling kanan tergantung dengan pembuat treenya.

Tipe Binary tree:
Perfect Binary Tree : Binary tree yang semua level mempunyai depth yang sama.


Complete Binary Tree : binary tree yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja). Dan dalam penempatan simpulnya diutamakan yang sebelah kiri yang terpenuhi.


Skewed Binary Tree : binary tree yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan binary tree yang seimbang.

Balanced Binary tree : bianry tree yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan binary tree yang seimbang.







Binary tree dapat diterapkan menggunaakan array maupun linked list
Array :
Index on array represents node number
Index 0 is Root node
Index Left Child is 2p + 1, where p is parent index
Index Right Child is 2p + 2
Index Parent is (p-1)/2





Linked List :


Expression Tree Concept




Menggunakan konsep matematika dalam penggunaan nya. Antara lain dalam penggunaan prefix, postfix dan infix.

Prefix : *+ab/-cde
Postfix : ab+cd-e/*
Infix : (a+b)*((c-d)/e)

Threaded binary tree adalah binary tree yang memiliki cara menunjuk pointer NULL yang berbeda dengan binary tree.


Binary tree tanpa threading:

Binary tree dengan menggunakan threading:

Terlihat perbedaan pointer NULL yang ada.


Ada 2 tipe threading:
1. Yang menggunakan threading 1 arah yang berarti masing masing pointer hanya menunjuk satu arah
2. Yang menggunakan threading 2 arah yang berarti masing masing pointer bisa menunjuk arah

Binary SearchTree

Binary Tree adalah Tree yang hanya memiliki maksimal 2 anak.
Binary search tree merupakan binary tree yang sudah tersortir. Kebanyakan Binary Search Tree menggunakan konsep untuk angka lebih kecil berada di sebelah kiri dan angka lebih besar berada di sebelah kanan.
Binary Search Tree mempuyai beberapa operasi dasar yaitu :
•>Find : Fungsi untuk mencari angka di dalam sebuah Binary Search Tree. Dilakukan dengan fungsi rekrusif dari root sampai meneukan angka yang kita inginkan. Konsepnya adalah dimulai dari root, jika root merupakan angka yang kita cari, return root. Jika angka yang kita cari lebih kecildaripada root, rekrusive fungsi ke subtree sebelah kiri. Jika angka yang kita cari lebih besar dari root, rekrusive fungsi ke subtree sebelah kanan.

•> Insert : Fungsi untuk menambahkan suatu node dari sebuah Binary Search Tree. Dilakukan dengan fungsi rekursif dari root dan key yang akan dimasukkan. Konsepnya adalah dimulai dari root jika key lebih kecil dari root maka, akan berpindah ke subtree sebelah kiri root dan jika lebih besar dari subtree sebelah kiri root maka, akan berpindah ke subtree sebelah kanan dari subtree sebelah kanan root dan jika lebih kecil dari subtree sebelah kiri root maka, akan berpindah ke subtree sebelah kiri dari subtree sebelah kiri root. Jika berpindah ke elemen yang masih kosong maka akan dipush kedalam tree.

•> Remove : Fungsi untuk menghapus suatu node dari sebuah Binary Search Tree. Dilakukan dengan mencari data yang akan dihapus dalam tree. Jika sudah dihapus maka, yang akan menggantikan data yang dihapus adalah:
1. Jika data yang dihapus adalah parent dengan single children maka, yang akan menggantikannya adalah childrennya.
2. Jika data yang dihapus adalah leaf maka, langsung dihapus saja.
3. Jika data yang dihapus adalah parent dengan 2 children maka, yang akan menggantikannya adalah subtree sebelah kanan nya yang paling kiri atau subtree sebelah kiri yang paling kanan tergantung dengan pembuat treenya.

Hash Table & Tree

Hashing

Ide utama dari hashing adalah mengubah suatu string menjadi suatu bilangan dengan suatu fungsi.Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai key yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.



Hash Function

Ada banyak cara untuk hash sebuah string menjadi sebuah key. berikut cara penting untuk membuat sebuah hash function:

Mid Square
Kuadratkan string/identifier, lalu kita mengambil angka tengah dari kuadrat identifier sebagai hash key.

Function : h(k) = s

k = key, s = hash key yang didapatkan dari mengambil tengah dari k^2

Division
 String/identifier dibagi dengan menggunakan modulus.

Function : h(z) = z mod M

z = key, M = angka yang digunakan untuk membagi key (biasanya menggunakan angka prima)

Folding
Langkah :

• bagi key value menjadi beberapa bagian
• jumlahkan bagian individal(usually last carry is ignored)

Digit Extraction
Beberapa bagian digit dari angka dijadikan sebagai hash address.
Contoh :
x=14568. Jika kita Mengambil angka ke 1,3, dan 5, kita akan mendapatkan hashcode : 158.

Rotating hash
Gunakan hash mehod apa saja, lalu kita balik(angka perama menjad angka terakhir, dst.


Hashing table didalam block chain digunakan untuk  cryptocurrencies, yaitu sebuah teknologi membuat mata uang digital. Teknologi ini menggunakan kriptografi untuk keamanan yang membuatnya tidak dapat dipalsukan. transaksi dengan panjang bervariasi dijalankan melalui algoritma hashing yang diberikan, dan menghaslkan output dengan panjang yang tetap terlepas dari panjang transaksi input. Output adalah sebuah hash.


Tree dan binary tree

Tree adalah non linear data sructure yang mempunyai tingkatan dari data objek. seperti struktur organisasi, dll. data diubungkan dengan pointer.


Tree concept :

Root : Node di paling atas
Edge: Garis yang menghubungkan parent dengan child
Leaf: node yang tidak mempunyai anak
Siblings: node yang mempnyai parent yang sama
Degree: total subtree dari sebuah node
Height/depth: maksimum degree dari sebuah tree
jika ada garis yang menghubungkan p kepada q, p disebut ancestor dari q dan q adalah descendant dari p.

Binary tree adalah sebuah tree yang setiap node mepunyai 2 anak. Anaknya dibedakan menjadi left chld dan right child.






Tipe Binary tree:
Perfect Binary Tree : Binary tree yang semua level mempunyai depth yang sama.


Complete Binary Tree : binary tree yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja). Dan dalam penempatan simpulnya diutamakan yang sebelah kiri yang terpenuhi.


Skewed Binary Tree : binary tree yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan binary tree yang seimbang.

Balanced Binary tree : bianry tree yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan binary tree yang seimbang.







Binary tree dapat diterapkan menggunaakan array maupun linked list
Array :
Index on array represents node number
Index 0 is Root node
Index Left Child is 2p + 1, where p is parent index
Index Right Child is 2p + 2
Index Parent is (p-1)/2





Linked List :


Expression Tree Concept




Menggunakan konsep matematika dalam penggunaan nya. Antara lain dalam penggunaan prefix, postfix dan infix.

Prefix : *+ab/-cde
Postfix : ab+cd-e/*
Infix : (a+b)*((c-d)/e)



Threaded binary tree adalah binary tree yang memiliki cara menunjuk pointer NULL yang berbeda dengan binary tree.


Binary tree tanpa threading:

Binary tree dengan menggunakan threading:

Terlihat perbedaan pointer NULL yang ada.


Ada 2 tipe threading:
1. Yang menggunakan threading 1 arah yang berarti masing masing pointer hanya menunjuk satu arah
2. Yang menggunakan threading 2 arah yang berarti masing masing pointer bisa menunjuk arah

Push dan Pop

Dalam linked list, kita mengenal  2 istilah yaitu, push dan pop. push merupakan fungsi untuk memasukan data kedalam linked list. sedangkan pop adalah fungsi untuk menghapus data dalam suatu linked list.
Untuk membuat suatu linked list, kita membutuhkan 3 pointer yaitu :
1. Head : awal dari suatu linked list,
2. Current : data yang sedang/akan kita olah,
3. Tail : akhir dar suatu linked list.

Push 
Push merupakan suatu fungsi untuk menambahkan pumya sata pada linked list yang kita punya. Push dapat dilakukan dari depan (push head), belakang(push tail), atau tengah(push mid). Saat kita menstruct data, kita harus membuat pointer di dalam struct, yaitu 1 pointer untuk single linked list, dan 2 pointer untuk double linked list.

Pop
Pop merupakan fungsi untuk menghapus data dalam suatu linked list. Push dapat dilakukan dari depan (push head), belakang(push tail), atau tengah(push mid). setelah kita melakukan menghapus, kita harus free untuk menghapus malloc yang telah kita lakukan, karena jika kita tidak free data akan terus mengambil tempat tanpa bisa di akses.

contoh coding: