HASHING TABLE
Hashing adalah metode yang efisien untuk menyimpan dan mengambil elemen. Persis sama dengan halaman indeks buku. Di halaman indeks, setiap topik dikaitkan dengan nomor halaman. Jika kita ingin melihat beberapa topik, kita bisa langsung mendapatkan nomor halaman dari indeks.
Demikian juga, dalam hashing setiap nilai akan dikaitkan dengan kunci. Dengan menggunakan kunci ini, kita dapat menunjukkan elemen secara langsung.
Hash Table adalah struktur data yang menyimpan data secara asosiatif. Dalam tabel hash, data disimpan dalam format array di mana setiap nilai data memiliki nilai indeks uniknya sendiri. Akses data menjadi sangat cepat, jika kita mengetahui indeks dari data yang diinginkan.
Hash 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.
Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).
Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.
Operasi Pada Hash Tabel
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 lalu hapus nilainya
getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu.
Implementasi Program C Hash Table :
#include<stdio.h>
#define size 7
int arr[size];
void init()
{
int i;
for(i = 0; i < size; i++)
arr[i] = -1;
}
void insert(int value)
{
int key = value % size;
if(arr[key] == -1)
{
arr[key] = value;
printf("%d inserted at arr[%d]\n", value,key);
}
else
{
printf("Collision : arr[%d] has element %d already!\n",key,arr[key]);
printf("Unable to insert %d\n",value);
}
}
void del(int value)
{
int key = value % size;
if(arr[key] == value)
arr[key] = -1;
else
printf("%d not present in the hash table\n",value);
}
void search(int value)
{
int key = value % size;
if(arr[key] == value)
printf("Search Found\n");
else
printf("Search Not Found\n");
}
void print()
{
int i;
for(i = 0; i < size; i++)
printf("arr[%d] = %d\n",i,arr[i]);
}
int main()
{
init();
insert(10); //key = 10 % 7 ==> 3
insert(4); //key = 4 % 7 ==> 4
insert(2); //key = 2 % 7 ==> 2
insert(3); //key = 3 % 7 ==> 3 (collision)
printf("Hash table\n");
print();
printf("\n");
printf("Deleting value 10..\n");
del(10);
printf("After the deletion hash table\n");
print();
printf("\n");
printf("Deleting value 5..\n");
del(5);
printf("After the deletion hash table\n");
print();
printf("\n");
printf("Searching value 4..\n");
search(4);
printf("Searching value 10..\n");
search(10);
return 0;
}
BINARY TREE
Binary Tree
adalah jenis struktur data di mana setiap node memiliki paling banyak dua anak
(anak kiri dan anak kanan). Pohon biner digunakan untuk mengimplementasikan
pohon pencarian biner dan tumpukan biner, dan digunakan untuk pencarian dan
penyortiran yang efisien. Pohon biner adalah kasus khusus dari pohon K-ary, di
mana k adalah 2. Operasi umum untuk pohon biner termasuk penyisipan,
penghapusan, dan traversal. Kesulitan melakukan operasi ini bervariasi jika
pohon seimbang dan juga apakah simpulnya adalah simpul daun atau simpul cabang.
Untuk pohon seimbang, kedalaman sub pohon kiri dan kanan setiap node berbeda 1
atau kurang. Ini memungkinkan kedalaman yang dapat diprediksi juga dikenal
sebagai ketinggian. Ini adalah ukuran dari simpul dari akar ke daun, di mana
akar adalah 0 dan simpul berikutnya adalah (1,2..n). Ini dapat diekspresikan
oleh bagian integer dari log2 (n) di mana n adalah jumlah node di pohon.
g s 9
/ \ / \ / \
b m f u 5 13
/ \ / \ / \
c d t y 11 15
Operasi yang dilakukan pada pohon memerlukan pencarian di salah satu dari dua cara utama: Pencarian Kedalaman Pertama dan pencarian Breadth-first. Depth-first search(DFS) adalah algoritma untuk melintasi atau mencari struktur data pohon atau grafik. Satu dimulai pada root dan mengeksplorasi sejauh mungkin sepanjang masing-masing cabang sebelum mundur. Ada tiga jenis penelusuran penelusuran kedalaman pertama: kunjungan sebelum pemesanan, kiri, kanan, kiri berurutan, kunjungan, kanan, kiri pasca pesanan, kanan, kunjungan.
Breadth-first search (BFS) adalah algoritma untuk melintasi atau mencari struktur pohon atau grafik. Dalam level-order, tempat kami mengunjungi setiap node pada level sebelum pergi ke level yang lebih rendah.
Conton Program C Yang Umum Pada Binary Tree
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* createNode(value){
struct node* newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct node* insert(struct node* root, int data)
{
if (root == NULL) return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
return root;
}
void inorder(struct node* root){
if(root == NULL) return;
inorder(root->left);
printf("%d ->", root->data);
inorder(root->right);
}
int main(){
struct node *root = NULL;
root = insert(root, 8);
insert(root, 3);
insert(root, 1);
insert(root, 6);
insert(root, 7);
insert(root, 10);
insert(root, 14);
insert(root, 4);
inorder(root);
}
No comments:
Post a Comment