Hash Table & Binary Search Tree

Hallo Guys~~
kembali lagi dengan chaca di tugas mata kuliah Data Struct ini.
Kali, aku bakalan bahas tentang Hash Table dan Binary Search Tree.
Q: Apa itu Hash Table?
A: sebuah Table(array) dimana kita menyimpan string. index dari table tersebut adalah tempat terisinya dan berisi value dari string tersebut.

penempatan value dari string yang akan ditempatkan di sebuah index berdasarkan cara berikut:
misalkan:
 h item = item % (size of table)   
mari kita asumsikan ukuran dari table = 11, maka 

54 % 11 = 10   26 % 11 = 4    93 % 11 = 5  
17 % 11 = 6    77 % 11 = 0    31 % 11 = 9    

maka tempat yang akan diisi akan menjadi seperti ini :




Kenapa kita menggunakan Hash Table?

1. jika U (Universe of keys) sangat  besar , meletakkan sebuat table T dari size [U] bisa saja tidak mungkin.
2. Penempatan k dari keys mungkin saja relatif kecil untuk U sehingga ruang untuk menggalokasikan memori untuk T akan terbuang.

Lalu, bagaimana jika dua buat string mempunyai value yang sama sehingga index yang perlu diletakkan juga sama?
itu disebut collisions/tabrakan .
Ada dua cara untuk menangani tabrakan tersebut:

Probing Linier
Cari slot kosong berikutnya dan letakkan talinya di sana.

Chaining
Masukkan string ke dalam slot sebagai daftar rantai (linked list).

berikut contoh source code untuk hash table:



//HASH TABLE
#include<stdio.h>
#include <string.h>
#include <stdlib.h>

struct data{
char name[100];
data *next,*prev;
}*table[100], *tail[100];

data *newData(char name[]){
data *current= (data*)malloc(sizeof(data));

strcpy(current->name,name);
current-> next = current-> prev = NULL;

return current;
}
int hashFunction (char name[]){
int sum=0;
for (int i=0;i<strlen(name);i++){
sum+=name[i];
}

return sum%=100;
}

void insert(data *current){
int index = hashFunction(current->name);

if (table[index]==NULL){
table[index]=tail[index]=current;
}
else {
current->prev=tail[index];
tail[index]->next=current;
tail[index]=current;
}
}
void deleteHash(char name[]){
int idx = hashFunction(name);

//kondisi kalau dia cuman satu
if (table[idx]==tail[idx]){
table[idx] = tail[idx]=NULL;
free(table[idx]);
}else if (strcmp(table[idx]->name,name)==0){
//kalau data name sama data head itu isinya sama dia pop head
data *temp = table[idx];
table[idx]=table[idx]->next;
free(temp);
}else if(strcmp(name,tail[idx])==0){
data *temp =table[idx];
tail[idx]=tail[idx]->prev;
tail[idx]->next=NULL;
free(temp);

}else{
data *temp=table[idx]; //buat tempnya di head

while (temp!=NULL){
if (strcmp(temp->name,name)==0){
break;
}
temp=temp->next;
}
temp->next->prev=temp->prev;
temp->prev->next=temp->next;
temp->next=temp->prev=NULL;
free(temp);
}

}
void printAll(){
for (int i=0;i<100;i++){
printf("%d",i+1);
data *temp=table[i];
while (temp!=NULL){
printf("%s ->",temp->name);
temp=temp->next;
}
puts("");
}
}

int main()
{
insert(newData("Brian"));
insert(newData("Brain"));
insert(newData("Caca"));
printAll();
return 0;

}

2.Binary Search Tree

Binary search tree disebut juga kelas pohon biner, di mana node diatur dalam urutan tertentu.
nilai semua node di sub-pohon kiri kurang dari nilai root dan nilai semua node di sub-pohon kanan lebih besar atau sama dengan nilai root.
Aturan ini akan diterapkan secara rekursif ke semua sub-pohon kiri dan kanan root.



ada beberapa operation yang bisa dilakukan di binary search tree , yaitu :
1 Mencari di BST
Mencari lokasi beberapa elemen tertentu dalam BST.

2.Penyisipan dalam BST 
Menambahkan elemen baru ke BST di lokasi yang sesuai sehingga properti BST tidak melanggar.
3.Penghapusan dalam BST Menghapus beberapa node tertentu dari pohon pencarian biner. Namun, bisa ada berbagai kasus dalam penghapusan tergantung pada jumlah anak, yang dimiliki simpul.


sekian untuk materi kali ini!
sampai jumpa minggu depan~~

source: https://www.javatpoint.com/daa-hash-tables