STRUKTUR DATA - Leftist, Tries and Hashing

Leftist

Leftist tree adalah variasi dari heap dimana fungsinya mencari nilai terbesar dan terkecil dari suatu tree. Dalam implementasinya, leftist lebih mudah menggunakan linked list karena leftist tree bukan termasuk ke dalam complete binary tree. Leftist tree sangat menguntungkan karena kita dapat menyatukan 2 heap menjadi satu dengan cepat.

Extended Binary Tree

Extended binary tree adalah suatu binary tree yang dilengkapi dengan external node. pada EBT, terdapat S(x) atau S value yang merupakan sebuah nilai yang menunjukan jarak terpendek dari x ke external node. Jika x adalah external node maka S(x) = 0.

suatu binary tree dikatakan leftist tree jika pada internal node s(x) anak sebelah kiri >= dari\anak sebelah kanannya.

Ada 2 jenis leftist tree, yaitu:

• Min leftist tree, setiap node lebih kecil daripada anaknya (min tree). Seperti min heap
• Max leftist tree, setiap node lebih besar dari anaknya (max tree). Seperti max heap

berikut gambarannya

s(x) anak kiri selalu lebih besar dari anak kanannya

Operasi : Combine

operasi combine adalah suatu operasi yang menyatukan 2 leftist tree menjadi 1 leftist tree

• misalkan kita akan menggabungkan 2 min leftist tree, yaitu a dan b
• compare root a dan root b, root yang memiliki nilai terendah akan menjadi root baru
• jika a < b, satukan subtree kanan a dengan tree lain secara rekursif. 
• update s(x) setiap kali menyatukan node
• ubah tree yang sudah disatukan menjadi leftist tree dengan menukar posisi node yang memiliki s(x) lebih besar ke sebelah kiri

contoh :

ada 2 leftist a dan b, kita akan menyatukannya
root a < root b, sehingga root a akan menjadi root baru

satukan subtree kanan a (anggap tree c) dengan leftist b
lalu lakukan step 2 kembali, karena root c > root b, maka satukan subtree kanan b(anggap d) dengan tree c

root d < root c, maka root d akan menjadi root baru dari gabungan c dan d
karena root d tidak memiliki anak kanan maka kita langung satukan c dan d

sehingga terbentuklah demikian, kemudian satukan b dengan tree cd
lakukan step ke 2 lagi, karena root b < root cd maka root b menjadi root baru
karena b tidak memiliki anak kanan lagi maka satukan b dan cd

jadilah demikian, kemudian kita satukan tree a dan tree bcd
karena root a < root bcd, maka root a menjadi root baru
karena a tidak memiliki anak kanan lagi, maka satukan a dan bcd

jadilah demikian

kemudian update s(x), yang berubah hanyalah 8, s(x)nya menjadi 2
kemudian tukar node dengan s(x) anak kanan >= s(x) anak kirinya, pada gambar diatas adalah node 2, 5, dan 8.
mengapa node 12 tidak ?? karena ia sudah menjadi anak kiri dan tidak memiliki sibling kanan sehingga tidak perlu dipindahkan

tukar node 8 dan 9 beserta subtreenya. jadilah demikian

tukar 5 dan 7 beserta subtreenya, jadilah demikian

jadilah min leftist tree

Operasi : Insert and Delete

proses insert dan delete dapat dilakukan dengan menggunakan kombinasi

• Insert

• membuat leftist tree baru b dengan single node, yaitu node yang baru di insert
• kombinasikan leftist tree a (leftist yang akan di insert data baru b) dan b

• Delete
• delete root
• gabungkan subtree kiri dan kanan root yang terpisah dengan operasi kombinasi menjadi suatu leftist tree yang baru

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 sudah diterapkan ke banyak hal dalam kehidupan sehari-hari, contohnya pada web browser. suatu web browser dapat mengira atau mensugestikan kata-kata yang mungkin kita maksud saat kita mengetik huruf pertamanya saja. (autocomplete)

kemudian selain itu juga pada spell checker, spell checker dapat mengetahui spelling kata yang tepat saat kita melakukan kesalahan dalam pengetikan. (autocorrect)

Tries adalah suatu tree dimana setiap vertex/pathnya menggambarkan suatu kata, rootnya kosong

gambarannya :

gambar tersebut menunjukan kata : ALGO, API, BOM, BOS, BOSAN, BOR

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.

contoh :

index dari setiap string adalah hash keynya
value adalah string aslinya
a diletakan pada 0, c pada 2, d pada 3, dst sesuai urutan abjad

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.berikut gambarannya :

• Chaining, adalah dengan memasukan string ke dalam slot yang sama dan kemudian string tersebut membentuk rantai (linked list). berikut gambarannya :