1.Mid square
mencari sebuah value dengan cara mengkuadratkan dan kemudian menggunakan jumlah bit yang sesuai dari kotak tengah untuk mendapatkan kunci hash
step :
1.Kuadratkan nilai dari kuncinya (k^2)
2.Meng-extract r bit yang berada di tengah dari hasil yang diperoleh pada langkah pertama
function : h(k) = s
k = key
s = hash key yang diperoleh dengan memilih r bit dari k^2
Contoh mid square
2.Division
Mencari sebuah value menggunakan operator modulus(%). Cara ini adalah cara tersimple untuk menemukan sebuah value dalam hash table.
function : h(z) = z mod M
z = key
m = nilai yang digunakan untuk membagi kunci, biasanya menggunakan bilangan prime, besar dari tabel / besar dari memori yang digunakan.
Contoh division
3.Folding
Metode ini membagi nilai asli ke dalam beberapa bagian, kemudian menambahkan nilai-nilai tersebut, dan mengambil beberapa angka terakhir sebagai nilai hashnya.
step :
1.membagi nilai kunci menjadi beberapa bagian
2.tambahkan bagian-bagiannya
4.Digit Extraction
Metode ini menggunakan cara digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.
contoh : Misal x = 15,980
jika kita mengekstrak digit 1,2,5 maka kita dapat mendapatkan hash code : 150.
5.Rotation hash
Metode ini menggunakan cara merotasi digit
contoh : alamat hash = 25291
hasil rotasi = 19252
Collision
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.
Collision(tabrakan pada hash function) bisa saja terjadi, ada dua cara untuk permasalah tersebut yaitu, Linear Probing dan Chaining
1. Linear Probing
Dengan menambahkan suatu interval pada hasil yang diperoleh dari fungsi hash sampai ditemukan lokasi yang belum terisi. Interval yang biasa digunakan adalah
2.Chaining
Metode rantai bisa juga digunakan untuk menyelesaikan tabrakan pada hash function, setiap data yang di dalam array sebenarnya terhubung secara single linked list yang berpasangan.
Tree
Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lain
Konsep tree
DEGREE of TREE = 3
DEGREE of C = 2
HEIGHT = 3
PARENT of C = A
CHILDREN of A = B, C, D
SIBILING of F = G
ANCESTOR of F = A, C
DESCENDANT of C = F, G
istilah-istilah dalam tree :
a.)Root = node yang berada paling atas
b.)Edge = garis yang menghubungkan node
c.)Leaf = node-node yang tidak memilik daun
d.)Degree of node = degree suatu node adalah total subtree
e.)Sibling = node yang mempunyai parent sama
f.)Ancestor = Seluruh node yang terletak sebelum node tertentu dan
terletak pada jalur yang sama.
g.)Descendant = Seluruh node yang terletak sesudah node tertentu
dan terletak pada jalur yang sama.
Binary Tree
Binary tree adalah suatu tree yang selalu mempunyai 2 anak, biasanya ada di kiri dan kanan.Binary tree mempunyai beberapa tipe yaitu, perfect binary tree, balance binary tree, skewed binary tree, dan balance binary tree.
A. Perfect binary tree
Binary tree yang mempunyai kedalaman sama di bagian kiri dan kanan
B.Complete binary tree
Complete binary tree adalah suatu pohon biner yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja). Dan dalam penempatan simpulnya diutamakan yang sebelah kiri yang terpenuhi.
C.Skewed binary tree
Skewed binary tree adalah binary tree yang mempunyai node paling banyak satu, sehingga membuatnya tidak seimbang
D.Balanced Binary Tree
Balanced binary tree adalah suatu pohon biner yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu
Implementasi hash table dalam bahasa c :
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define size 97
struct data {
int value;
char name[100];
struct data *next;
}*table[97] = {NULL}, *curr, *ptr;
void cls() {
for(int i = 0; i< 50; i++) {
printf("\n");
}
}
void push(int value, char name[]) {
curr = (struct data*)malloc(sizeof(struct data));
curr->value = value;
strcpy(curr->name,name);
int key = value % size;
curr->next = NULL;
if(table[key]==NULL) {
table[key]=curr;
}
else {
ptr = table[key];
while(ptr->next != NULL){
ptr = ptr->next;
}ptr->next = curr;
}
}
void cari() {
int search = 0;
int i = 0;
printf("Input Your KEYDATA : ");
scanf("%d",&search);
getchar();
search = search % 97;
ptr = table[search];
if(ptr != NULL) {
while(ptr !=NULL) {
if(ptr->value == search) {
printf("THE STRING DATA STORED IS %s\n",ptr->name);
break;
}
ptr = ptr->next;
}
}
else {
printf("THERE IS NO DATA REFERENCE TO NUMBER %d\n",search);
system("pause");
}
}
void tampil(){
int i = 0;
do{
ptr = table[i];
if(ptr !=NULL) {
printf("DATA AT INDEX %d:\n",i);
while(ptr != NULL){
printf("(%d \t %s)\n",ptr->value,ptr->name);
ptr = ptr->next;
}
printf("\n");
}
i++;
}while(i < 97);
}
void menu_awal() {
int data;
char string[100];
printf("Input your KEY DATA : ");
scanf("%d",&data);
getchar();
printf("Input your STRING DATA : ");
scanf("%[^\n]",string);
push(data,string);
}
void init() {
for(int i = 0; i< size; i++) {
table[i] = NULL;
}
}
int main() {
int choice;
init();
while(true) {
do{
tampil();
printf("--[PROGRAM MENU]--\n");
printf("1. Input Data\n");
printf("2. Search Data\n");
printf("3. Exit\n");
printf("Input your choice: ");
scanf("%d",&choice);
}while(choice < 1 || choice > 3);
switch(choice) {
case 1 :
menu_awal();
break;
case 2 :
cari();
break;
case 3 :
return 0;
}
}
}
Session 4
Binary Search Tree
Binary Search Tree
Binary search tree mempunyai ciri-ciri :
1.Setiap node mempunyai value dan tidak ada value yang double
2.value yang ada di kiri tree lebih kecil dari rootnya
3.value yang ada di kanan tree lebih besar dari rootnya
4.kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child jadi BST ini memiliki sifat ( rekrusif )
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
Operasi-operasi yang dilakukan pada binary search tree meliputi :
1. Operasi: Insertion BST
Memasukan value (data) baru kedalam BST dengan rekrusif
Bayangkan kita menginsert value x :
Dimulai dari root
jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang ( rekrusif )
jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang ( rekrusif )
Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah biasa di sebut Leaf atau daun )
2. Operasi: Delete ( Remove )
akan ada 3 case yang ditemukan ketika ingin menghapus yang perlu diperhatikan :
Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan) atau dengan cari dari right sub-tree anak kiri paling terakhir(leaf) (kanan,kiri)
3. Operasi: Search BST
dengan adanya ciri” atau syarat di dalam BST , maka untuk finding/searching didalam BST menjadi lebih mudah.
Bayangkan kita akan mencari value X.
Memulai Pencarian Dari Root
Jika Root adalah value yang kita cari , maka berhenti
Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan
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
sumber :
https://abdilahrf.github.io/2015/06/pengenalan-binary-search-tree/
http://www.nblognlife.com/2014/12/binary-search-tree-bst-tree-lanjutan.html
http://lang8088.blogspot.com/2015/06/memahami-pengertian-binary-search-tree.html
contoh implementasi binary search tree dalam bahasa c :
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int x;
struct node *left, *right;
}node;
node *createNewNode(int x) {
node *temp = (node *)malloc(sizeof(node));
temp->x = x;
temp->left = temp->right = NULL;
return temp;
}
node *insertNode(node *root, int x) {
if(root == NULL)
{
return createNewNode(x);
}
else
{
if(x < root->x)
{
root->left = insertNode(root->left,x);
}
else if( x > root->x) {
root->right = insertNode(root->right,x);
}
else {
printf("Same data !!!\n");
}
}
return root;
}
node *findminimum(node *temp) {
// root kiri paling kanan || ambil root kanan paling kiri
if(temp->right == NULL)
return temp;
return findminimum(temp->right);
}
int search(node *root, int x) { // x yang dicari
if(root == NULL)
return -1;
if(root->x == x) // target kita
return 1;
else {
if(x < root->x)
{
return search(root->left,x);
}
else if( x > root->x) {
return search(root->right,x);
}
}
return -1;// gak dapaet
}
node *deleteNode(node *root,int x)
{
if(root == NULL) // gadapet.
{
printf("Gaada\n");
return root;
}
else if(x < root->x)
root->left = deleteNode(root->left,x);
else if(x > root->x)
root->right = deleteNode(root->right,x);
else
{
//3 case
//1.leaf
if(root->right == NULL && root->left == NULL)
{
free(root);
root = NULL;
}
else if(root->left == NULL)
{
node *temp = root;
root = root->right;
free(temp);
}
else if(root->right == NULL)
{
node *temp = root;
root = root->left;
free(temp);
}
else //case 3.
{
node *temp = findminimum(root->left);
root->x = temp->x;
root->left = deleteNode(root->left,temp->x);
}
}
return root;
}
void printInorder(node *root) {
if(root == NULL) {
return;
}
printf("%d ",root->x);
printInorder(root->left);
printInorder(root->right);
}
int main() {
node *root = NULL;
root = insertNode(root,16);
root = insertNode(root,25);
root = insertNode(root,14);
root = insertNode(root,17);
root = insertNode(root,18);
printInorder(root);
printf("\n");
root = deleteNode(root,17);
printInorder(root);
}
– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
