Hashing and Binary Tree
A. Hashing
Hashing adalah metode yang digunakan untuk mempermudah
penyimpanan dengan cara melakukan ekripsi nilai tertentu dengan kaidah yang
telah ditentukan sebagai “key” dari suatu data.
Hash Table
Adalah table ( dalam bentuk array ) dimana kita menyetor
suatu data, dimana indexnya adalah key dan nilainya (value) adalah data
sebenarnya.
Sebagai contoh, kita akan menyetor beberapa nilai integer
kedalam array yang memiliki index sebanyak 20. Karena index hanya 20, maka key
yang kita buat harus 0 – 20. Nilai key akan ditentukan dengan modulus 20;
Contoh :
Input:
- Value = 20, key =
20 % 20 = 0;
- Value = 5, key =
5%20 = 5;
Hasil
|
index array
|
Key
|
value
|
|
0
|
20
|
20
|
|
1..4
|
|
|
|
5
|
5
|
5
|
|
6…19
|
|
|
Tetapi ada beberapa kondisi yang dapat muncul dalam
melakukan Hashing ini
Contoh :
Input :
- value = 20, key = 0
- value = 1, key = 1;
- value = 21, key = 21 % 20 = 1;
Value 1 dan 21 memiliki key yang sama, kalua dibiarkan maka
value 1 akan di override / ditimpa nilainya oleh 21. Hal ini disebut collision
Untuk menangani collision, ada 2 cara yang dapat diterapkan
yaitu probing dan chaining
1. probing
Berarti jika tempat key sudah diisi, maka data akan diisi
ditempat yang kosong selanjutnya. Hal ini akan memperlambat pencarian jika
sudah banyak tempat yang terisi.
void
insert(int key,int value){
int hash_index = hashCode(key);
// untuk dapatin key yang udah di hash
struct Data *item=
(Data*)malloc(sizeof(Data)); //setor nilai dalam node item
item->key = key;
item->value = value;
while(tabel[hash_index]!=NULL){
//selama tempat itu ga kosong
hash_index++; //
digeser trus sampai t4 kosong
}
hash_index %= size;
tabel[hash_index] = item; //
sampai t4 kosong baru bisa masukin
}
Data*
search(int keyz){
int hash_index = hashCode(keyz);
//mencari nilai key
while(tabel[hash_index]!=NULL){
//masih harus cari karena bisa aja datanya ud tergeser dari
index yang seharusnya
if(tabel[hash_index]->key==keyz){
//klu misalnya ktemu kosong, nanti stop
return
tabel[hash_index];
}
hash_index++; //menambah nilai key sampai ketemu tempat
kosong
hash_index %=
size;
}
// warning : klu semua kotak
terisi dan tidak ada yang dicari, bisa looping forever -> crash
return NULL;
}
void
deletion(int key){
Data *del = search(key); //cari
datanya pkai function search
if(del==NULL){
printf("No
data to be deleted\n");
return;
}
else{
int code =
hashCode(del->key);
while(tabel[code]!=NULL){
if(tabel[code]->key
== key){
printf("(%d,%d) has been
deleted\n",tabel[code]->key,tabel[code]->value);
tabel[code]
= NULL;
}
code++;
code
%= size;
}
// warning : klu
semua kotak terisi dan dkd yang dicari, bisa looping forever -> crash
}
return;
}
Kelemahan
probingakan terlihat dari contoh berikut
Insert(1,20)
, insert(21,21), insert (41,22), insert(2,50)
Maka akan
menghasilkan
|
idx array
|
Key
|
value
|
|
0
|
|
|
|
1
|
1
|
20
|
|
2
|
21
|
21
|
|
3
|
41
|
22
|
|
4
|
2
|
50
|
|
5..19
|
|
|
Bila kita menghapus key 1, maka array index 1 akan memiliki
value null. Lalu Ketika kita ingin menghapus key 21 ataupun 22, maka akan dicek
index 1, yaitu null. Karena null tersebut, maka deletion akan berhenti sehingga
key 21 dan 41 tidak bisa dihapus.
2. Chaining
Bila ada key yang sama, maka akan ditempatkan di next. Cara
kerjanya sama seperti linked list.
void
insert(int key,int value){
int hash_idx = hashCode(key);
Data *item =
(Data*)malloc(sizeof(Data));
item->key = key;
item->value = value;
item->next = NULL;
if(kotak[hash_idx]==NULL){
kotak[hash_idx] =
item;
}
else{
Data *temp =
kotak[hash_idx];
while(temp->next){ //kalau setelah head(index 1) ada
sesuatu, dia looping sampai ga
ada
lagi (ujung)
temp
= temp->next;
}
temp->next =
item; //baru ujungnya ditempelin item
}
}
Data*
search(int key){
int hash_idx = hashCode(key);
while(kotak[hash_idx]!=NULL){
if(kotak[hash_idx]->key==key){
return
kotak[hash_idx];
}
kotak[hash_idx] =
kotak[hash_idx]->next;
}
return NULL;
}
void
deletion(int key){ //deletion v2
int hash_idx = hashCode(key);
if(!kotak[hash_idx]) return;
Data *temp = kotak[hash_idx];
Data *stab;
if(temp->key==key){ // jika
yang mau dihapus data pertama / head
kotak[hash_idx] =
temp->next; //headnya digeser
temp = NULL;
free(temp);
return;
}
while(temp->next!=NULL){
if(temp->next->key==key){
stab
= temp->next;
temp->next
= stab->next;
stab
= NULL;
free(stab);
return;
}
temp =
temp->next;
}
printf("no data to be
deleted\n");
return;
}
Contoh:
Insert(1,20) , insert(21,21), insert (41,22), insert(2,50)
|
Index array
|
key
|
value
|
|
0
|
|
|
|
1
|
1, 21, 41
|
20 -> 21 -> 22
|
|
2
|
2
|
5
|
|
3..19
|
|
|
Jadi cara
terbaik dalam hash table adalah chaining karena lebih efektif, efisien dan aman
dalam insertion, searching, dan deletion.
B. Binary
Search Table
Adalah
struktur data yang setiap nodenya memiliki cabang dua yaitu left dan right, dan
diawali oleh root. Node yang tidak ada cabang disebut leaf.
Metode dalam
bst ada 3 yaitu insert, search, and delete.
struct Node{
int value;
Node *left,*right;
}*curr;
Node
*create(int nilai){
curr =
(Node*)malloc(sizeof(Node));
curr->value = nilai;
curr->left = curr->right =
NULL;
return curr;
}
Node
*insert(Node *root, int nilai){
if(root==NULL) return
create(nilai);
else if(nilai >
root->value){
root->right =
insert(root->right,nilai);
}
else if(nilai <
root->value){
root->left =
insert(root->left,nilai);
}
return root;
}
Kita mengoper
root, dan nilai baru untuk node yang kita acari. Ketika root nya tidak ada atau
null, maka nilai itu akan menjadi root. Jika tidak, maka akan dilakukan
pengecekan nilai itu lebih besar atau lebih kecil dari root.
Jika lebih
besar dari root, maka akan diinsert ke root right. Sebaliknya jika lebih kecil
maka akan diinsert ke left, hingga ketemu NULL dan di create
Node *del(Node
*root, int nilai){
if(root==NULL) return NULL;
else{
if(nilai ==
root->value){
if(root->left==NULL
&& root->right==NULL){ //ga ada left right
free(root);
root
= NULL;
}
else
if(root->left==NULL){ //ada right
curr
= root;
root
= root->right;
free(curr);
curr
= NULL;
}
else
if(root->right==NULL){ /ada left
curr
= root;
root
= root->left;
free(curr);
curr
= NULL;
}
else{
//kalau 2 anak,
curr
= root->left; //dalam hal ini, dicari anak terkanan dari left root
while(curr->right){
curr
= curr->right;
}
root->value
= curr->value; //dilakukan penukaran nilai
root->left
= del(root->left,curr->value);
}
}
else if(nilai >
root->value){
root->right
= del(root->right,nilai);
}
else if(nilai <
root->value){
root->left
= del(root->left,nilai);
}
}
return root;
}
Deletion memiliki
3 kondisi
11. Node merupakan leaf / tidak ada left dan right
Dalam hal ini, node tinggal di free dan dijadikan
NULL
22. Node punya 1 anak , left atau right
Maka node digeser , dihubungkan dengan anak dan
node yang lama di free
33. Node punya dua anak, left dan right
Biasanya, ada kesepakatan mengenai
pengganti dari node, yaitu node paling kanan dari left atau node paling kiri
dari right, tergantung kesepakatan.
