Hashing Table dan Binary Tree
Hashing Table
adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.
Contoh perintah pada Hashing Table
➤ insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
➤ find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
➤ remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
➤ getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu
Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.
Cara untuk mendapatkan field kunci ini sangatlah beragam, namun hasil akhirnya adalah sebuah bilangan hash yang digunakan untuk menentukan lokasi record. Bilangan hash ini dimasukan ke dalam hash function dan menghasilkan indeks lokasi record dalam tabel.
k(x) = fungsi pembangkit field kunci (1)
h(x) = hash function (2)
Fakta hashing table!:
➤Hashing digunakan untuk menyimpan data yang cukup besar pada ADT yang disebut hash table.
➤Ukuran Hash table (H-size), biasanya lebih besar dari jumlah data yang hendak disimpan.
➤load factor() adalah perbandingan antara data yang disimpan dengan ukuran hash table.
➤Fungsi Hash memetakan elemen pada indeks dari hash table.
Contoh Kodingan Hash Table:
int hash(String key, int tableSize) {
int hashVal = 0;
for (int i=0; i < key.length(); i++) {
hashVal = (hashVal * 37
+ key.charAt(i));
}
hashVal %= tableSize;
if (hashVal < 0) {
hashVal += tableSize;
}
return hashVal;
}
Binary Tree
Tree
adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many). Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai percabangan atas dirinya.
Sedangkan Binary Tree adalah tree yang hanya dapat mempunyai maksimal 2 percabangan saja.
Sedangkan Binary Tree adalah tree yang hanya dapat mempunyai maksimal 2 percabangan saja.
Aturan yang ada di binary tree :
- Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
- Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.
Lalu, ada 3 jenis cara untuk melakukan penelusuran data(traversal) pada BST:
- PreOrder : Print data, telusur ke kiri, telusur ke kanan
- InOrder : Telusur ke kiri, print data, telusur ke kanan
- Post Order : Telusur ke kiri, telusur ke kanan, print data
Contoh koding:
#include <stdio.h>
#include <stdlib.h>
//inisialisasi struct
struct data{
int number;
//pointer untuk menampung percabangan kiri dan kanan
data *left, *right;
}*root;
//fungsi push untuk menambah data
void push(data **current, int number){
//jika pointer current kosong maka akan membuat blok data baru
if((*current)==NULL){
(*current) = (struct data *)malloc(sizeof data);
//mengisi data
(*current)->number=number;
(*current)->left = (*current)->right = NULL;
//jika tidak kosong, maka akan dibandingkan apakah angka yang
//ingin dimasukkan lebih kecil dari pada root
//kalau iya, maka belok ke kiri dan lakukan rekursif
//terus menerus hingga kosong
}else if(number < (*current)->number){
push(&(*current)->left, number);
//jika lebih besar, belok ke kanan
}else if(number >= (*current)->number){
push(&(*current)->right, number);
}
}
//preOrder : cetak, kiri, kanan
void preOrder(data **current){
if((*current)!=NULL){
printf("%d -> ", (*current)->number);
preOrder(&(*current)->left);
preOrder(&(*current)->right);
}
}
//inOrder : kiri, cetak, kanan
void inOrder(data **current){
if((*current)!=NULL){
inOrder(&(*current)->left);
printf("%d -> ", (*current)->number);
inOrder(&(*current)->right);
}
}
//postOrder : kiri, kanan, cetak
void postOrder(data **current){
if((*current)!=NULL){
postOrder(&(*current)->left);
postOrder(&(*current)->right);
printf("%d -> ", (*current)->number);
}
}
//searching data
void search(data **current, int number){
//jika pointer current memiliki data
if((*current)!=NULL){
//cek, apakah datanya lebih kecil. Jika iya, belok ke kiri
if(number<(*current)->number){
search(&(*current)->left,number);
//jika lebih besar, maka belok ke kanan
}else if(number>(*current)->number){
search(&(*current)->right,number);
//jika sama dengan, maka angka ketemu
}else{
printf("Found : %d", (*current)->number);
}
//jika tidak ada data lagi (not found)
}else{
printf("Not Found.");
}
}
void main(){
push(&root, 11);
push(&root, 22);
push(&root, 13);
push(&root, 15);
push(&root, 9);
inOrder(&root);
printf("\n");
preOrder(&root);
printf("\n");
postOrder(&root);
printf("\n");
search(&root,91);
getchar();
}
Sekian dari penjelasan saya, terima kasih
Sumber:
Komentar
Posting Komentar