Rabu, 06 Mei 2020

AVL TREE

Rabu, 6 Mei 2020

Kevin
2301880231

AVL TREE
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

A. Insert dalam AVL Tree
Untuk menjaga agar tree tetap seimbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan tersebut dapat  dilakukan dengan dua metode yaitu : Single rotation dan Double rotation. 

1. Single Rotation
Single Rotation terjadi bila kondisi tree dinsert dan terjadi ketidakseimbangan balance factor > 1 dan node yang mengalami ketidakseimbangan tersebut searah atau disebut Left Left (LL) atau sebaliknya yaitu Right Right (RR).

2. Double Rotation
Sebaliknya, Double Rotation terjadi bila tree diinsert dan jika terjadi ketidakseimbangan balance factor > 1 dan node yang mengalami ketidakseimbangan tersebut berlawanan arah yaitu Left Right (LR) atau Right Left (RL).

Berikut contoh gambar dari insert AVL Tree :
B. Delete node dalam AVL Tree
Terdapat 2 kasus yang biasanya terjadi dalam operasi delete yaitu kurang lebih mirip dengan 
Binary Search Tree (BST) akan tetapi bedanya harus menyeimbangkan balance factor, yaitu :
 - Jika node yang ingin dihapus terletak pada posisi leaf atau node yang tidak memiliki anak kiri maupun kanan, maka dapat langsung dihapus.
- Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
            - Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
            - Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
            - Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

           Berikut contoh dari delete AVL Tree :


Berikut contoh dari coding-an AVL Tree Insert dan Delete :
#include<stdio.h>
#include<stdlib.h>

struct node{
int key;
int height;
struct node *left;
struct node *right;
};

int max(int a, int b){
if(a < b) return b;
else return a;
}

int getHeight(struct node *root){
if(root == NULL) return 0;
return root->height;
}

// Get Balance Factor
int getBF(struct node *root){
if(root == NULL) return 0;
return getHeight(root->left) - getHeight(root->right);
}

struct node *rightRotate(struct node *y){
struct node *x = y->left;
struct node *B = x->right;

//rotate
x->right = y;
y->left = B;

y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

return x;
}

struct node *leftRotate(struct node *x){
struct node *y = x->right;
struct node *B = y->left;

//rotate
y->left = x;
x->right = B;

x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

return y;
}


// di subtree kanan , ambil nilai terkecil
struct node *successor(struct node *root){
struct node *cur = root->right;
while(cur->left != NULL){
cur = cur->left;
}
return cur;
}

// di subtree kiri, ambil nilai terbesar
struct node *predecessor(struct node *root){
struct node *cur = root->left;
while(cur->right != NULL){
cur = cur->right;
}
return cur;
}

struct node *newNode(int x){
struct node *currNewNode =
(struct node*)malloc(sizeof(struct node));

currNewNode->key = x;
currNewNode->height = 1;
currNewNode->left = NULL;
currNewNode->right = NULL;

return currNewNode;
}

struct node *insert(struct node *root, int value){
if(root == NULL) return newNode(value);
else if(value < root->key){
root->left = insert(root->left, value);
}else{
root->right = insert(root->right, value);
}

// calculate balance factor for each node
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
int bfactor = getBF(root);

// if violation , then rotate
if(bfactor > 1 && value < root->left->key){
return rightRotate(root); //LL bf = 2
}
if(bfactor <-1 && value > root->right->key){
return leftRotate(root); //RR bf = -2
}
if(bfactor > 1 && value > root->left->key){
root->left = leftRotate(root->left);
return rightRotate(root); //LR bf = 2
}
if(bfactor < -1 && value < root->right->key){
root->right = rightRotate(root->right);
return leftRotate(root); //RL bf = -2
}
return root;
}

struct node *deleteValue(struct node *root, int value){
if(root == NULL) return NULL; // tidak ketemu...
if(value < root->key){
root->left = deleteValue(root->left, value);
}else if(value > root->key){
root->right = deleteValue(root->right, value);
}else{

// ketemu mari kita mulai delete...

// case 1 : tidak punya anak
// case 2 : hanya punya anak kiri
// case 3 : hanya punya anak kanan
if((root->left == NULL) || (root->right == NULL)){

struct node *temp = NULL;
if(root->left != NULL) temp = root->left;
else temp = root->right;

if(temp == NULL){
// pasti tidak punya anak
// ini adalah case 1
temp = root;
root = NULL;
}else{
// ini adalah case 2 dan case 3
*root = *temp;
}
free(temp);

}else{
// ini adalah case 4
// ada 2 anak, maka kita ambil suksesor / predesesor
// terserah

struct node *temp = predecessor(root);
root->key = temp->key;

// delete
root->left = deleteValue(root->left, temp->key);
}
}

if(root == NULL) return root;

// kita perlu fix height dlsbnya
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
int bfactor = getBF(root);

if(bfactor > 1 && getBF(root->left) >= 0){
return rightRotate(root);
}
if(bfactor > 1 && getBF(root->left) < 0){
root->left = leftRotate(root->left);
return rightRotate(root);
}
if(bfactor < -1 && getBF(root->right) <= 0){
return leftRotate(root);
}
if(bfactor < -1 && getBF(root->right) > 0){
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}


void printAll(struct node *root){
if(root == NULL) return;
printAll(root->left);
printf(" %d ", root->key);
printAll(root->right);
}

struct node *freeAll(struct node *root){
if(root == NULL) return NULL;
root->left = freeAll(root->left);
root->right = freeAll(root->right);
free(root);
return NULL;
}

int main(){
struct node *root = NULL;

root = insert(root, 10);
root = insert(root, 5);
root = insert(root, 7);
root = insert(root, 15);
root = insert(root, 20);
root = insert(root, 17);

printAll(root);
puts("");

root = deleteValue(root, 10);

printAll(root);
puts("");

root = deleteValue(root, 15);

printAll(root);
puts("");

root = freeAll(root);

return 0;

}

Diposting oleh di 1 komentar:

Selasa, 07 April 2020

TUGAS DATA STUCTURE SEBELUM UTS

Sabtu, 4 April 2020
Rangkuman Mid Semester dan soal Coding

A. Linked list
Apa itu Linked List? 
- Linked list adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer. - Rangkaian single linked list tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan di akhiri dengan node yang mengarah pointer ke null. 
Ada beberapa macam dari single linked list yaitu : 
1. Single Link List 
Single Linked List merupakan suatu linked list yang hanya memiliki satu varuabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya.Biasanya field pada tail menunjuk ke NULL.

Berikut contoh source code utk singled link list :

#include<stdio.h>
#include<stdlib.h>
struct data
{
int value;
struct data *next;
}tdata, *h, *t;

void pushBelakang(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
t->next = curr;
t = curr;
}
}

void pushDepan(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
curr->next = h;
h = curr;
}
}

void pushTengah(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
struct data *temp = h;
while (temp->next->value < v)
{
temp = temp->next;
}
curr->next = temp->next;
temp->next = curr;
}
}

void push(int v)
{
if (h == NULL) //List Kosong
{
pushDepan(v);
}
else
{
if (v <= h->value)
{
pushDepan(v);
}
else if (v >= t->value)
{
pushBelakang(v);
}
else
{
pushTengah(v);
}
}
}
void popDepan()
{
if (h == NULL)
return;
struct data *c = h;
if (h == t)
h = t = NULL;
else
h = h->next;
free(c);
}

void popBelakang()
{
if (h == NULL)
return;
struct data *c = h;
if (h == t)
h = t = NULL;
else
{
while (c->next != t)
{
c = c->next;
}
free(t);
t = c;
t->next = NULL;
}
}

void pop(int v)
{
if (h == NULL)
return;
struct data *temp = h;
while (temp->value != v)
{
temp = temp->next;
if (temp == NULL)
return;
}
if (temp == h)
{
popDepan();
}
else if (temp == t)
{
popBelakang();
}
else
{
struct data *t = h;
while (t->next != temp)
{
t = t->next;
}
t->next = temp->next;
free(temp);
}
}
void popAll()
{
while (h != NULL)
{
popDepan();
}
}
void printAll()
{
struct data *c = h;
while (c != NULL)
{
printf(" %d ", c->value);
c = c->next;
}
}
int main()
{
h = t = NULL;
push(25);
push(30);
push(5);
push(15);
push(20);
push(50);
push(40);
push(70);
push(0);
printAll();
printf("\n");
pop(0);
pop(70);
pop(40);
pop(100);
printAll();
printf("\n");
popAll();
return 0;
}
2. Double Linked List
Double Linked List adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. 
Contoh dari double linked list :
Struktur Data – Double Linked List dengan Bahasa C | Mahir Koding
Contoh code dari double linked list :
#include<stdio.h>
#include<stdlib.h>
struct data
{
int value;
struct data *next;
struct data *prev;
}tdata, *h, *t;
void pushBelakang(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
curr->prev = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
t->next = curr;
curr->prev = t;
t = curr;
}
}
void pushDepan(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
curr->prev = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
curr->next = h;
h->prev = curr;
h = curr;
}
}
void pushTengah(int v)
{
struct data *curr;
curr = (struct data *) malloc(sizeof(struct data) );
curr->value = v;
curr->next = NULL;
curr->prev = NULL;
if (h == NULL){ //List Kosong
h = t = curr;
}
else{
struct data *temp = h;
while (temp->next->value < v)
{
temp = temp->next;
}
curr->next = temp->next;
curr->prev = temp;
temp->next->prev = curr;
temp->next = curr;
}
}
void push(int v)
{
if (h == NULL) //List Kosong
{
pushDepan(v);
}
else
{
if (v <= h->value)
{
pushDepan(v);
}
else if (v >= t->value)
{
pushBelakang(v);
}
else
{
pushTengah(v);
}
}
}
void popDepan()
{
if (h == NULL)
return;
struct data *c = h;
if (h == t)
h = t = NULL;
else
{
h = h->next;
h->prev = NULL;
}
free(c);
}
void popBelakang()
{
if (h == NULL)
return;
struct data *c = t;
if (h == t)
h = t = NULL;
else
{
t = t->prev;
t->next = NULL;
free(c);
}
}
void pop(int v)
{
if (h == NULL)
return;
struct data *temp = h;
while (temp->value != v)
{
temp = temp->next;
if (temp == NULL)
return;
}
if (temp == h)
{
popDepan();
}
else if (temp == t)
{
popBelakang();
}
else
{
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
}
}
void popAll()
{
while (h != NULL)
{
popDepan();
}
}
void printAll()
{
struct data *c = h;
while (c != NULL)
{
printf(" %d ", c->value);
c = c->next;
}
}
int main()
{
h = t = NULL;
//struct data tdata2;
push(25);
push(30);
push(5);
push(15);
push(20);
push(50);
push(40);
push(70);
push(0);
printAll();
printf("\n");
pop(0);
pop(70);
pop(40);
pop(100);
printAll();
printf("\n");
popAll();
        return 0;
}
3. Circular Linked List
Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :
- Circular Single Linked List
- Circular Double Linked List

B. Hashing and Hashing Tables
- Hasing adalah Transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. 

- Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan  data dan penghapusan data dapat dilakukan dengan cepat. Ide dasarnya adalah menghitung posisi record yang dicari dalam array, bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hash function) dan array yang digunakan disebut tabel hash (hash table). Hash table menggunakan  struktur  data  array  asosiatif  yang  mengasosiasikan  record   dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut.

- Fungsi hash menyimpan nilai asli atau kunci pada alamat yang sama dengan nilai hash-nya. Pada pencarian suatu nilai pada tabel hash, yang pertama dilakukan adalah menghitung nilai hash dari kunci atau nilai aslinya, kemudian membandingkan kunci atau nilai asli dengan isi pada memori yang beralamat nomor hash-nya. Dengan cara ini, pencarian suatu nilai dapat dilakukan dengan cepat tanpa harus memeriksa seluruh isi tabel satu per satu.

- Hashing adalah cara untuk menyimpan data yang akan kita buat lebih singkat dengan menggunakan key. Dan data tersebut akan disimpan dalam bentuk array. Berikut beberapa jenis hash function yaitu :
1. Mid-Square
2. Fold
3. Rotasi Hash
4. Ekstrasi Digit
5. Divisi ( Paling Umum )

- Selain itu, ada yang disebut dengan collision, collision adalah cara handle ketika hash key yang telah ada sama / sejenis/ tidak unik , maka kita butuh dalam penanganan case ini : 
Ada 2 jenis dalam Collision :
1. Chaining
Teknik Chaining merupakan suatu teknik untuk mengatasi collision (bentrokan) dengan cara menggunakan daerah di luar tabel Hash dalam bentuk linier. Bentuk linier ini bisa berupa linked-list atau array. Urutan data pada daerah overflow bisa terurut atau random, tergantung cara penyisipan yang dilakukan.
2. Linear Probing 
Pada saat terjadi collision, maka akan mencari posisi yang kosong di bawah tempat terjadinya collision, jika masih penuh terus ke bawah, hingga ketemu tempat yang kosong. Jika tidak ada tempat yang kosong berarti HashTable sudah penuh

C. 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.

Ada 3 jenis dalam melakukan cara untuk penulusuran data 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

Berikut Source Code utk BST :
#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();
}

D. JAWABAN SOAL DATA STRUCTURE MEMBUAT MENU 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>

struct Market{
char name[100];
int quantity;
int price;
struct Market *next,*prev;
}*head,*tail,*curr,*temp;

void pushItem(char name[], int quantity, int price){
curr = (struct Market*)malloc(sizeof(Market));
strcpy(curr->name,name);
curr->quantity = quantity;
curr->price = price;

curr->next = NULL;
curr->prev = NULL;

if(head == NULL){
head = tail = curr;
}
else{
tail->next = curr;
curr->prev = tail;
tail = curr;
}
}

void deleteItem(char name[]){
    if(head == NULL){
        printf("Your Menu is empty\n");
        getchar();
        return;
    }
    curr = head;
    while(curr!=NULL){
        if(strcmp(curr->name,name)==0)
            break;
        if(strcmp(curr->name,name)>0){
            printf("Your Input not found\n");
            getchar();
            return;
        }
        curr = curr->next;
    }
    if(curr == NULL)
        printf("Not Found");
    else if(curr == head && !curr->next)
        head = NULL;
    else if(curr == head){
        head->next->prev = NULL;
        head = curr->next;
    }
    else if(curr == tail){
        curr->prev->next = NULL;
        tail = curr->prev;
    }
    else{
        curr->next->prev = curr->prev;
        curr->prev->next = curr->next;
    }
    free(curr);
}

void deleteMenu(){
    char name[50];
    int quantity;
    int len;
    do{
        printf("Input item name you want to delete>> ");
        scanf("%[^\n]", name);getchar();
        len = strlen(name);
    }while(len < 1);

    curr = head;
    while(curr!= NULL){
        if(strcmp(curr->name,name)==0)
            break;
        curr = curr->next;
    }
    if(curr = NULL){
        printf("Not Found");
        getchar();
        return;
    }
    deleteItem(name);
    printf("Succesfully deleted");
    getchar();
}

void edit(char name[],int quantity,int price,int upqty){
curr = head;

while(strcmp(curr->name,name) != 0){
curr = curr->next;
if(curr == NULL){
printf("There's no word exist'");getchar();
return;
}
}
strcpy(curr->name,name);
curr->quantity = upqty;
curr->price = price;
}

void CheckOut(){
    if(head == NULL){
        printf("Your Menu is empty");
        getchar();
        return;
    }
    curr = head;
    int index = 0;
    int total = 0;
    printf("-------------------------------------------------------------------------------------\n");
    printf("|                               List Menu                                  |\n");
    printf("|-----------------------------------------------------------------------------------|\n");
    printf("| No  |             Item Name               |  Qty   |   Price    |       Total     |\n");
    printf("-------------------------------------------------------------------------------------\n");
    while(curr != NULL){
        printf("= %3d = %-35s = %6d = Rp.%7d = Rp. %11d =\n",++index,curr->name,curr->quantity,curr->price, curr->quantity*curr->price);
        total += curr->quantity*curr->price;
        curr = curr->next;
    }
    printf("------------------------------------------------------------------------------------");
    printf("|-----------------------------Discount---------------------------|= Rp. %11d =\n", total);
    puts("--------------------------------------------------------------------------------------");
    printf("=------------------------------Total------------------------------=       Free      =\n");
    printf("-----------------------Kindness is Free!!-------------------------------------------");
  getchar();
}

void printList(){
    if(head==NULL){
        printf("Your menu is empty\n");
getchar();
        return;
    }
    curr = head;
    int index = 0;
    printf("-------------------------------------------------------------------\n");
    printf("|                           List Menu                             |\n");
    printf("|-----------------------------------------------------------------|\n");
    printf("| No  |             Item Name               =  Qty   =   Price    |\n");
    printf("-------------------------------------------------------------------\n");
    while(curr!= NULL){
        printf("| %3d | %-35s | %6d | Rp.%7d |\n",++index,curr->name,curr->quantity,curr->price);
        curr = curr->next;
    }
    printf("|-----------------------------------------------------------------|");
}

void popHead(){
curr = head;
head = curr->next;
free(curr);
}

void popAll(){
curr = head;
while(head != NULL){
popHead();
}
}

int main(){
int choice;
char name[100];
int quantity;
int price;
int len;
int upqty;
do{
system("cls");
printf("Market Menu!!\n\n");
printf("1. View List\n");
printf("2. Add New Item on List\n");
printf("3. Edit Quantity Item on List\n");
printf("4. Delete Item on List");
printf("5. Checkout Item\n");
printf("6. Exit\n");
printf("Choose >> ");
scanf("%d",&choice);getchar();
printf("\n\n");

if(choice == 1){
printList();
getchar();
}
else if(choice == 2)
{
do{
printf("Input Item Name[1..100]: ");
scanf("%[^\n]",name);getchar();
len = strlen(name);
}while(len < 1 || len > 100);

do{
printf("Input %s quantity >> ",name);
scanf("%d", &quantity);getchar();
}while(quantity < 1);
printf("\n");
price = rand() % 79999 + 15000;
pushItem(name,quantity,price);
printf("Add Item Successful!\n");
printf("Press Enter to continue...");
getchar();
}
else if(choice == 3)
{
printf("Input Item Name you want to edit: ");
scanf("%[^\n]",name);getchar();
printf("Input Update Quantity: ");
scanf("%d",&upqty);getchar();
edit(name,quantity,price,upqty);
}
else if(choice == 4)
{
deleteMenu();
}
else if(choice == 5){
CheckOut();
}
else if(choice == 6){
popAll();
system("cls");
printf("List Menu successfully deleted!");
getchar();
}

}while(choice!=6);
}




Diposting oleh di Tidak ada komentar:

Senin, 16 Maret 2020

Hashing Table & Binary Tree

Senin, 16 Maret 2020

Kevin
2301880231

1. Hashing & hash 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.




  • Pengertian Hash Table


          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.


Contoh Hash Table :
5 string yang sudah dihashing akan disimpan sesuai nilai key yang didapatkan. Kita cuma memakai karakter pertama dari string.
-        atan disimpan di h[0] karna a = 0  
-        char disimpan di h[2] karna c = 2  
-        define disimpan di h[3] karna d = 3  
-        exp disimpan di h[4] karna e = 4  
-        float disimpan di h[5] karna f = 5  

Berikut adalah contoh dari operasi hashing sebagai berikut :
  1. Insert : pada insert akan diberikan sebuah key dan nilai, insert nilai dalam sebuah table
  2. Search : pada search akan diberikan sebuah key, temukan nilai yang berhubungan dengan key tersebut
  3. Delete : pada delete akan diberikan sebuah key, kemudian temukan key tersebut dan hapus nilainya
  • Menghitung Fungsi Hash
    •               Fungsi Hash adalah suatu fungsi yang mengubah key menjadi alamat dalam tabel. Fungsi Hash memetakan sebuah key ke suatu alamat dalam tabel. Idealnya, key-key yang berbeda seharusnya dipetakan ke alamat-alamat yang berbeda juga. Pada kenyataannya, tidak ada fungsi Hash yang sempurna. Kemungkinan besar yang terjadi adalah dua atau lebih key yang berbeda dipetakan ke alamat yang sama dalam tabel. Peristiwa ini disebut dengan collision (tabrakan). Karena itulah diperlukan langkah berikutnya, yaitu collision resolution (pemecahan tabrakan).

    Collision Resolution

    Collision resolution merupakan proses untuk menangani kejadian dua atau lebih key di-hash ke alamat yang sama. Cara yang dilakukan jika terjadi collision adalah mencari lokasi yang kosong dalam tabel Hash secara terurut. Cara lainnya adalah dengan menggunakan fungsi Hash yang lain untuk mencari lokasi kosong tersebut.
2. Binary Tree
binary tree
         Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.
            Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.
            Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong).

Binary Search Tree
binary search tree

                  Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut.                            Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam struktur data BST juga dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk seperti linked list.
                     



  
Diposting oleh di Tidak ada komentar:

Selasa, 25 Februari 2020

Kevin
2301880231
Data Structure
Linked List
Single Linked List adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer.

rangkaian single linked list tersebut diawali dengan sebuah head untuk menyimpan alamat awal dan di akhiri dengan node yang mengarah pointer ke null.



Single Linked List hanya memiliki satu arah dan tidak memiliki dua arah atau bulak balik, dua arah tersebut disebut dengan double linked list.



Pada Implementasinya, Single Linked List terdapat dua variasi yaitu circular dan non-circular.

Pada Implementasinya, Single Linked List terdapat dua variasi yaitu circular dan non-circular. Berikut adalah ilustrasi single linked list Non-Circular



Single Linked List Non-Circular

sedangkan untuk single linked list Circular nya adalah sebagai berikut.





Diposting oleh di Tidak ada komentar:
Langganan: Komentar (Atom)