Tuesday, March 17, 2020

Hashing Table and Binary Search Tree

Pada konten blog saya kai ini, saya akan memaparkan tentang Hashing Table and BInary Tree. yoo lets goo...!


A. Hashing Table
Apa si Hashing Table? Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara, tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan.
Kelebihan Hashing Table ialah
1. Lebih Cepat mengakses Data.
2. Kecepatan dalam insertions, deletions, maupun searching relatif samaKecepatan dalam insertions, deletions, maupun searching relatif sama.
Yang perlu diperhatikan untuk membuat hash function adalah:
  1. ukuran array/table size(m),
  2. key value/nilai yang didapat dari data(k),
  3. hash value/hash index/indeks yang dituju(h).
contoh penggunaan hash table dengan hash function sederhana yaitu memodulus key value dengan ukuran array : h = k (mod m). Misal kita memiliki array dengan ukuran 13, maka hash function : h = k (mod 13).
Dengan hash function tersebut didapat :
Perhatikan range dari h untuk sembarang nilai k.
Maka data 7 akan disimpan pada index 7, data 13 akan disimpan pada index 0, dst..
Untuk mencari kembali suatu data, maka kita hanya perlu menggunakan hash function yang sama sehingga mendapatkan hash index yang sama pula.
Misal : mencari data 25 → h = 25 (mod 13) = 12
Namun pada penerapannya, seperti contoh di atas terdapat tabrakan (collision) pada k = 13 dan k = 39. Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.
Cara mengatasi Collision Sebagai berikut:
1.   Closed hashing (Open Addressing).
Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. 3 cara untuk mencari alamat lain tersebut 
   - Linear Probing
Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus (h+1) mod m.
   - Quadratic Probing
Quadratic Probing mencari alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih kompleks. Tidak ada formula baku pada quadratic probing ini,anda dapat menentukan sendiri formula yang akan digunakan. Contoh formula quadratic probing untuk mencari alamat baru: h,(h+i2)mod m,(h-i2)mod m, … ,(h+((m-1)/2)2)mod m, (h-((m-1)/2)2)mod m, dengan i = 1,2,3,4, … , ((m-1)/2). Maksud formula di atas adalah jika alamat h telah terisi, maka alamat lain yang digunakan adalah (h+1)mod m, jika telah terisi gunakan alamat (h-1)mod m,  jika telah terisi gunakan alamat (h+4)mod m, jika telah terisi gunakan alamat (h-4)mod m, dan seterusnya. Jadi jika m=23,maka nilai maksimal i adalah : ((23-1)/2)=11.
    - Double hashing
Sesuai dengan namanya, alamat baru untuk menyimpan data yang belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function lagi. Hash function kedua yang digunakan setelah alamat yang dihasilkan oleh hash function awal telah terisi tentu saja berbeda dengan hash function awal itu sendiri. Kelemahan dari closed hashing adalah ukuran array yang disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori yang lebih besar untuk meminimalkan collision.
2.   Open hashing (Separate Chaining)
Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.
Penggunaan Hashing pun terdapat di sistem blockhain, hashing menggunakan sistem cryptocurrency.
B. Binary Search Tree
Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.

Aturan main Binary Search 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 Sistem dalam Binary Search Tree, yaitu: 
- 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

//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);
 }
}

Sumber : 
Posted by at No comments:

Sunday, March 1, 2020

PENGERTIAN LINKED LIST BESERTA JENIS DAN CONTOHNYA

PENGERTIAN LINKED LIST BESERTA JENIS DAN CONTOHNYA

Pengertian Linked list :

  1. •  Linked list adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis sehingga isi dari daftar dapat dimanipulasi.
  2. •  struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori.


Single Linked List

Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul. Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List (NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL).

Pembuatan Single Linked List dapat menggunakan 2 metode:
  1. •     LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
  2. •     FIFO (First In First Out), aplikasinya : Queue (Antrean)


Double Linked List

Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List.

Circular Double Linked List

Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.
Operasi-Operasi yang ada pada Linked List

Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.

IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.

Find First
Fungsi ini mencari elemen pertama dari linked list

Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now

Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.

Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu

Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.

Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.

Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.


Skenario

1.   Dasar Linked List

Sebelum masuk dalam pembuatan program Linked List, kita akan melihat terlebih dahulu sebagaian dari cara kerja linked list. Yaitu adalah cara masing-masing element terhubung.

Langkah-langkah :
- Bukalah C++ IDE yang ada pada komputer anda atau notepad.
- Salinlah kode berikut

#include<iostream>
using namespace std;

struct node {
int data;
node* next;
};

node *head = NULL;

int main(){
node *satu; satu = new node; 
node *dua; dua = new node; 
node *tiga; tiga = new node;

satu->data = 3; 
dua->data = 5; 
tiga->data = 7; 
satu->next = dua; 
dua->next = tiga;
tiga->next = NULL;
head = satu;

node *temp = head;
while( temp!=NULL ){
cout<< temp->data<<" ";
temp = temp->next;
} 
cout<<"\n"; 
return 0;
}
- berikutnya compile dan jalankan program tersebut. Jika program anda benar maka akan memunculkan keluaran seperti gambar dibawah ini.




2.   Program Linked List dalam C++

Pada skenario 1 kita sudah melihat bagaimana linked list dapat terhubung satu dengan yang lainnya. Sekarang kita akan mengimplmentasi Linked secara penuh.

Langkah pertama bukalah IDE yang ada pada komputer anda atau notepad. Kemudian salinlah kode berikut ini.

#include<iostream> 
using namespace std; 

struct node {
int data;
node* next;
};

node *head = NULL;
node *tail = NULL;

int Length(struct node* head) {
int count = 0;
struct node* current = head; 
while (current != NULL) {
 count++;
current = current->next;
}

return(count); 
}

void add(int data){
node *temp;
temp = new node;
temp->data = data;
if(head == NULL){ 
head = temp; 
tail = temp;
head->next = NULL;
tail->next = NULL;
}else{
tail->next = temp; 
temp->next = NULL; 
tail = temp;
}
}

void printNode(){
node *temp = head;
while( temp!=NULL ){
cout<< temp->data<<" ";
temp = temp->next;
}
cout<<"\n";
}

int main(){
add(18); 
add(17);
add(20);
printNode();
cout<<Length(head);
node *temp;
temp = new node;
temp->data = data;
if(head == NULL){ 
head = temp; 
tail = temp;
head->next = NULL;
tail->next = NULL;
}else{
tail->next = temp; 
temp->next = NULL; 
tail = temp;
}
}

void printNode(){
node *temp = head;
while( temp!=NULL ){
cout<< temp->data<<" ";
temp = temp->next;
}
cout<<"\n";
}

int main(){
add(18); 
add(17);
add(20);
printNode();
cout<<Length(head);
return 0;
}

Thank You for visit my blog 



Posted by at No comments:
Subscribe to: Comments (Atom)