Data Structure

Hashing Table

Pengertian Hashing

Hashing adalah transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau kunci yang mewakili string asli.

Pengertian Hash Table 

Hash Table adalah sebuah struktur data sebagai tempat kita menyimpan data. Hash Table terdiri atas tabel dan fungsi yang bertujuan memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Ukuran tabel hash biasanya terdiri dari beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki hashed key yang sama.

Hash Function

Pada hash function terdapat beberapa cara untuk mengaitkan string menjadi key. Berikut adalah beberapa cara untuk membangun hash function :

a. Mid-square

Kuadratkan string kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key.
Jika key nya adalah string, akan di konversi ke angka

   Langkah langkah:

   1. kuadratkan nilai pada sebuah key.

   2. ekstrak  ambil nilai tengah sejumlah r bits dari hasil kuadrat nilai pada step pertama.

Contoh:
nilai = 3121
hasil kuadrat = 3121 * 3121 = 9740641
nilai tengah = 9740641   

b. Division

Membagi suatu string dengan memakai operator modulus
Ini adalah metode hashing integer x yang paling sederhana

Function: h(z) = z mod M
z  = key

M = nilai yang digunakan untuk membagi key, biasanya menggunakan bilangan prima, ukuran tabel atau ukuran memori yang digunakan.

 

Contoh:

"COBB" akan disimpan di lokasi

(64 + 3 + 64 + 15 + 64 + 2 + 64 + 2)% 97 = 88

 c. Folding

Metode folding berfungsi dalam dua langkah :
1. Bagilah nilai key menjadi sejumlah bagian di mana disetiap bagian memiliki jumlah digit yang      sama kecuali bagian terakhir yang mungkin memiliki angka lebih sedikit daripada bagian lain
2. Tambahkan bagian individual. Yaitu memperoleh jumlah part1 + part2 + ... + bagian n. Nilai hash yang dihasilkan dengan mengabaikan carry terakhir, jika ada.

Contoh:
  Nilai = 34567
  Parts = 34,56, dan 7
  Sum = 34 + 56 + 7 = 97
  Hash value = 97

d. Digit Extraction

Digit extraction adalah digit yang ditentukan sebelumnya dari nomor yang diberikan yang dianggap sebagai hash address

Contoh:
  X = 14.568
  Jika kita mengekstrak digit 1,3, dan 5, kita akan mendapatkan hash code yaitu : 158

e. Rotating Hash

Gunakan metode hash (seperti metode pembagian atau mid-square)

Lakukan rotasi

 

Contoh:

 Diberikan hash address = 20021

 Hasil rotasi = 12002 

 

 

 

 

Binary Tree 

 

 

Pengertian Binary Tree 

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Jenis-jenis Binar Tree :

1. Full Binary Tree

Full binary tree adalah binary tree yang tiap node-nya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

2. Complete Binary Tree 

Complete binary tree adalah binary tree yang mirip dengan full binary tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

3. Skewed Binary Tree

Skewed binary tree adalah binary tree yang semua node nya (kecuali leaf) hanya memiliki satu child.

    

4. Binary search tree (BST) 

Binary search tree (BST) adalah jenis pohon terurut yang digunakan untuk menyimpan data sehingga memudahkan pencarian kembali data tersebut.

 

 

Operasi pada Tree

• Create

Create digunakan untuk membentuk binary tree baru yang masih kosong.

• Clear

Clear digunakan untuk mengosongkan binary tree yang sudah ada.

• Empty

Empty digunakan untuk memeriksa apakah binary tree masih kosong.

• Insert

Insert digunakan untuk memasukkan sebuah node ke dalam tree.

• Find

Find digunakan untuk mencari root, parent, left child , atau right child dari suatu node dengan syarat tree tidak boleh kosong.

•  Update

Update digunakan untuk mengubah isi dari node yang ditunjuk oleh pointer current dengan syarat tree tidak boleh kosong.

• Retrieve

Retrieve digunakan untuk mengetahui isi dari node yang ditunjuk pointer current dengan syarat tree tidak boleh kosong.

• Delete Sub

DeleteSub digunakan untuk menghapus sebuah sub-tree (node beserta seluruh descendant-nya) yang ditunjuk pointer current dengan syarat tree tidak boleh kosong.

• Characteristic

Characteristic digunakan untuk mengetahui karakteristik dari suatu tree, yakni size, height, serta average length-nya.

• Traverse

Traverse digunakan untuk mengunjungi seluruh node-node pada tree, masing-masing sekali.