Tries & Hashing

Tries
Tries atau prefix tree adalah suatu pohon struktur data yang terurut yang menyimpan data array, biasanya string.
Kata tries diambil dari kata retrieval, karena tries dapat menemukan kata tunggal dalam kamus dengan hanya awalan katanya saja.
Tries adalah suatu tree dimana setiap subtreeny menggambarkan suatu kata, rootnya kosong

Hashing
Hashing adalah transformasi dari string of character menjadi nilai yang lebih pendek atau key yang merepresentasikan suatu string aslinya.Hashing digunakan untuk mengindex dan retrieve item dalam database, karena akan lebih mudah menggunakan kata kunci yang lebih singkat dibandingkan string aslinya.

Hash Table
Hash table adalah tabel (array) yang menyimpan string aslinya.

Collision
Collision adalah suatu kondisi dimana beberapa value memiliki hash key yang sama.

Cara mengatasi collision ada 2 cara yaitu :
Linear Pobing, adalah dengan memasukan string ke slot lain yang masih kosong.
Chaining, adalah dengan memasukan string ke dalam slot yang sama dan kemudian string tersebut membentuk rantai (linked list).

Leftist Tree

Leftist Tree adalah varian dari heap yang dapat menemukan elemen terkecil atau terbesar pada tree.
Dalam sebuah leftist tree dapat dikatakan jika nilai node internal di sebelah kiri lebih besar atau sama dengan internal node di sebelah kanan.

Leftist tree terbagi menjadi 2 yaitu:
-terdiri dari min tree atau max tree

Keuntungan menggunakan leftist tree
-leftist tree dapat menggabungkan 2 tree
-leftist tree lebih mudah diimplementasikan dengan link list

Sifat-sifat dari leftist tree

1. s value pada leftist tree selalu lebih besar pada node bagian kiri.
2. pada leftist max tree node teratas bernilai paling besar
3. pada leftist min tree node teratas bernilai paling kecil

Extended tree adalah metode untuk menghitung s(x) dari leftist tree.Dalam extended tree terdapat yang disebut external node. External node adalah node bernailai NULL yang ditambahkan dalam setiap node yang tidak memiliki anak atau anak yang complit.

S(x) atau s value adalah nilai s dari tiap node yang dihitung berdasarkan external node terdekat.

Insertion
Buatlah leftist tree baru yang mengandung node tunggal, masukkan node baru, lalu gabungkan dengan leftist tree yang sudah ada.

Node baru yang baru masuk di tempatkan di sebelah kanan. Setelah dimasukkan node baru, bandingkan setiap s(x) value dari setiap node. Jika s(x) value node yang kiri lebih kecil daripada s(x) value yag kanan, maka lakukan swap pada node tersebut beserta anak-anaknya.

Combine
Operasi utama leftist tree adalah menggabungkan 2 pohon(tree) menjadi satu pohon(tree).

Kedua root dari pohon(tree) tersebut dibandingkan terlebih dahulu. Jika ini leftist mix tree,
root dari pohon yang baru haruslah nilai terkecil dari kedua root yang harus digabungkan.
Jika ini leftist max tree,root dari pohon yang baru haruslah nilai terbesar dari kedua root yang harus digabungkan.



Deletion
Delete pada leftist tree hanya dapat dilakukan pada root. Seletah melakukan melakuka delete pada root, gabunglah kedua roots anak sub tree kiri dengan roots anak sub-pohon kanan dan mendapatkan leftist free baru.

Deap

Deap adalah gabungan dari min heap dan max heap, namun berbeda dengan min-max heap, karena pada deap, rootnya tidak ada, atau kosong/NULL dan subtree kirinya adalah min heap dan subtree kanannya adalah max heap.

Insertion
- Masukkan node baru pada index selanjutnya (setelah index terakhir)
- Jika key terletak pada min heap

• Bandingkan dengan max partner
• Jika max partnernya < key, swap
• Lakukan min upheap, yaitu up heap di min subtree

- Jika key terletak pada max heap

• Bandingkan dengan min partner
• Jika min partnernya > key, swap
• Lakukan max upheap, yaitu up heap di max subtree

Deletion
Ada 2 jenis delete, delete min dan delete max.

• Jika delete min

Gantikan node yang dihapus dengan node index terakhir,kemudian lakukan downheap min,dan compare dengan partnernya, jika partner < node tersebut,tinggal di tukar saja

• Jika delete max

Gantikan node yang dihapus dengan node index terakhir,kemudian lakukan downheap max,dan compare dengan partnernya, jika partner > node tersebut,tinggal di tukar saja

Heap

Heap adalah complete binary tree yang berbasis struktur data dan memenuhi aturan heap. Tree pada heap and deap tidak memenuhi aturan BST yang harus terurut secara inorder, yang penting tree tersebut mengikuti aturan heap.

Jenis - jenis heap :
Min Heap : node paling kecil adalah root dan semakin kebawah levelnya semakin besar
Max Heap : node paling besar adalah root dan semakin kebawah levelnya semakin kecil
Min-Max Heap : min-heap dan max-heap levelnya saling bergantian pada tree

Min Heap

Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Lakukan upheap, yaitu compare key dengan parentya, jika node parent > key, maka swap. Jika tidak maka biarkan saja
- Lakukan point ke-2 berulang kali jika setelah diswap masih parent > key. namun stop jika key sudah berada pada posisi root.

Deletion
- Operasi delete hanya terjadi pada rootnya saja.
- Gantikan elemen yang didelete dengan node yang berada pada index terakhir
- Lakukan downheap, yaitu compare dengan salah satu childnya yang terkecil. jika node tersebut > child terkecil, maka swap
- Lakukan point ke-3 jika setelah diswap node tersebut masih memiliki anak. Namun stop jika node sudah dalam posisi leaf atau node tersebut < child terkecilnya

Max Heap

Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Lakukan uphead, yaitu compare key dengan parentnya, jika node parent < key maka swap. Jika tidak maka biarkan saja
- Lakukan point ke-2 berulang kali jika setelah diswap masih parent < key. namun stop jika key sudah berada pada posisi root.

Deletion

-Operasi delete hanya terjadi pada rootnya saja.
- Gantikan elemen yang didelete dengan node yang berada pada index terakhir
- Lakukan downheap, yaitu compare dengan salah satu childnya yang terbesar. jika node tersebut < child terbesar, maka swap
- Lakukan point ke-3 jika setelah diswap node tersebut masih memiliki anak. Namun stop jika node sudah dalam posisi leaf atau node tersebut > child terbesarnya


Min-Max Heap

Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Jika key terletak pada level min : bandingkan dengan parentnya

• Jika parent < key maka swap dan upheapmax dari parentnya (dibandingkan dengan grandparentnya dari posisi key setelah swap)
• Jika parent > key, upheapmin dari posisi key (dibandingkan dengan grandparentnya dari posisi key).

- Jika key terletak pada level max :

• Jika parent > key maka swap dan upheapmin dari parentnya (dibandingkan dengan grandparentnya dari posisi keysetelah swap)
• Jika parent < key, upheapmax dari posisi key(dibandingkan dengan grandparentnya dari posisi key).

Deletion
- Delete Min, menghapus node terkecil, yaitu root
- Delete Max, menghapus node terbesar, yaitu salah satu dari anak root
Konsep deletenya sama :
- Node yang dihapus digantikan oleh node index terakhir
- Lakukan downheapmin jika delete min, atau downheapmax jika delete max

B-Tree

Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree.

Aturan pada B-Tree : m = order
Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
Root memiliki anak minimal 2, selama root bukan leaf
Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
Data yang tersimpan pada node harus terurut secara inorder
Semua leaf berada pada level yang sama, level terbawah

Insertion

Anggap data yang mau di insert adalah key
Posisikan key pada node yang sesuai, seperti pada BST dan 2-3 Tree, anggap node tersebut A
Jika A adalah node dengan jumlah data kurang dari m-1, maka langsung masukan saja
Jika A adalah node dengan jumlah data m-1, maka masukan nilai tengah kemudian masukan ke parentnya. Kemudian anggaplah parent tersebut A. Kemudian periksa kembali sesuai aturan point ke 3 dan 4.

Deletion

Anggap node yang mau di delete adalah key
Delete dilakukan pada leaf. Meskipun pada saat menghapus node parent, kita tetap menganggapnya menghapus leaf, karena ketika parent dihapus lalu digantikan oleh anak terbesar subtree kiri atau anak terkecil subtree kanan sama saja kita seolah-olah menghapus anak yang menggantikannya. dimana anak tersebut selalu berada pada posisi leaf. Maka leaf tersebut dianggap P.
Jika ukuran P > m/2 maka langsung delete saja data yang ingin dihapus
Jika ukuran P = m/2 maka : perhatikan siblingnya (anggap sibling adalah Q)
Q > m/2, maka rotasi pada P
Q = m/2, satukan P dan Q