Final Summary

Binary Search Tree

Saya telah mempelajari apa itu binary search tree melalui website geeksforgeek. Dalam website itu yang biasa saya simpulkan adalah ; Binary search tree merupakan metode menggunakan binary tree data structure. Binary search tree terdiri dari 

- Cabang kiri merupakan node yang mengandung node yang isinya lebih kecil dari node key

- Cabang kanan merupakan node yang mengandung node yang isinya lebih besar dari node key

- Cabang kanan maupupn kiri harus merupakan binary tree data sturcture

Contoh kodingan insertion :

#include<stdio.h>

#include<stdlib.h>

   

struct node

{

    int key;

    struct node *left, *right;

};

   

struct node *nodes(int item)

{

    struct node *temp =  (struct node *)malloc(sizeof(struct node));

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

   

//fungsi print

void print(struct node *root)

{

    if (root != NULL)

    {

        print(root->left);

        printf("%d \n", root->key);

        print(root->right);

    }

}

  //fungsi untuk memasukkan data

struct node* insert(struct node* node, int key)

{

   


    if (node == NULL) return nodes(key);

  

    if (key < node->key)

        node->left  = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);   

 

    return node;

}

int main()

{

    struct node *root = NULL;

    root = insert(root, 50);

    insert(root, 70);//MASUK KE CABANG KANAN




    insert(root, 10);//MASUK KE CABANG KIRI

  

    print(root);

   

    return 0;

} 

HASHING TABLE AND BINARY TREE

 

Hari ini saya mempelajari dari blog tentang Algoritma dan Data Struktur "Hashing Table". Dari blog ini saya memperoleh berbagai pengertian tentang Hashing Table yaitu sebuah struktur data yang terdiri dari fungsi dan table yang bertujuan untuk mempercepat pencarian kembali dari banyak data yang disimpan. 

Hash table menggunakan sebuah teknik penyimpanan sehingga waktu yang digunakan dalam penambahan data (Insert) penghapusan data (Delete) dan pencarian data (Search) relatif sama dibanding struktur data atau algoritma yang lain

Keuntungannya :

- waktu akses yang relatif cepat 

- kecepatan sama dalam insertion , deletion , searching

Kekurangannya :

- Terkadang sering ditemukan record record yang bertabrakan

Hash table menggunakan memori penyimpanan utama berbentuk array yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut .

Dalam web geeksforgeeks saya juga mempelajari Binary Tree . Binary tree bukanlah data struktur seperti Array, linked list , stack , queue yang merupakan data struktur linear, melainkan data struktur hirarkis. Node bagian atas tree disebut root sedangkan elemen2 lain di bagian bawah tree merupakan anaknya (Children) , sedangkan elemen yang tidak mempunyai anak disebut leaves .

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

struct Node {
    int data;
    char namaBarang[100] ;
    struct Node* maju;
    struct Node* mundur;
};
     
   
void push(struct Node** head, int stok, char namaBrg[])
{
    struct Node* ne = (struct Node*)malloc(sizeof(struct Node));
    ne->data = new_data;
    strcpy(ne->namaBarang,namaBrg);
    ne->maju = (*head);
    ne->mundur = NULL;
   
    if ((*head) != NULL)
          (*head)->mundur = ne;
        (*head) = ne;
}      

void deleteNode(struct Node** head, struct Node* del)
{
    if (*head == NULL || del == NULL)
        return;
 
    if (*head == del)
        *head_ref = del->next;
 
    if (del->maju != NULL)
        del->maju->mundur = del->mundur;
 
    if (del->prev != NULL)
        del->mundur->maju = del->maju;
 
    free(del);
    return;
}

void deleteNodeIndex(struct Node** head, int a)
{
    if (*head == NULL || a <= 0)
        return;
    struct Node* curr = *head;
    int i;
    for (int i = 1; curr != NULL && i < a; i++)
        curr = curr->next;
    if (curr == NULL)
        return;
    deleteNode(head, curr);
}  

void inputData(){
    char nama[100];
    int banyakNya;
    printf("Masukkan Nama : ");
    scanf("%[^\n]",nama);
    getchar();
    printf("Masukkan Stok : ");
    scan("%d",banyakNya);
    push(&head, banyakNya,nama);
}


void deleteData(){
    int input;
    printf("Index yang mau di delete : ");
    scanf("%d",&a);
    deleteNodeIndex(&head,a);
}


int main(){
    struct Node* head = NULL;
    int input=0;
    getchar();
    do{
       
        printf("1. Masukkan data\n");
        printf("2. Hapus data\n");
        printf("3. Exit\n")
        printf("Choose >> ");
        scanf("%d",&input);
       
        switch(input){
            case 1 : inputData();break;
            case 2 : deleteData();break;
        }
       
    }while(input=3);
    printf("Semua Gratis");
}


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

#define SIZE 20

struct DataItem {
   int data;  
   int key;
};

struct DataItem* hashArray[SIZE];
struct DataItem* dummyItem;
struct DataItem* item;

int hashCode(int key) {
   return key % SIZE;
}

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key); 
   
   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
   
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
           
      //go to next cell
      ++hashIndex;
       
      //wrap around the table
      hashIndex %= SIZE;
   }       
   
   return NULL;       
}

void insert(int key,int data) {

   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data; 
   item->key = key;

   int hashIndex = hashCode(key);

   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
         printf("%d sebelum\n",hashIndex);

      ++hashIndex;
      printf("%d sesudah\n",hashIndex);


      hashIndex %= SIZE;
   }
   
   hashArray[hashIndex] = item;
   printf("%dselesai\n",hashIndex);
}

struct DataItem* deletes(struct DataItem* item) {
   int key = item->key;


   int hashIndex = hashCode(key);


   while(hashArray[hashIndex] != NULL) {
   
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex];
           

         hashArray[hashIndex] = dummyItem;
         return temp;
      }
       

      ++hashIndex;
       

      hashIndex %= SIZE;
   }     
   
   return NULL;       
}

void display() {
   int i = 0;
   
   for(i = 0; i<SIZE; i++) {
   
      if(hashArray[i] != NULL)
         printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data);
      else
         printf(" ~~ ");
   }
   
   printf("\n");
}

int main() {
   dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
   dummyItem->data = -1; 
   dummyItem->key = -1;

   insert(1, 20);
   insert(2, 70);
   insert(42, 80);
   insert(43, 25);
   insert(4, 44);
  

   display();
   item = search(37);

   if(item != NULL) {
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }

   deletes(item);
   item = search(37);

   if(item != NULL) {
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }
}

 source : geeksforgeek.org

AVL TREE

 

AVL tree adalah sebuah binary tree yang dapat menyeimbangkan dirinya sendiri, sehingga tidak terjadi worst case yang tidak diinginkan. AVL tree merupakan data structure yang sejenis dengan binary search tree yang berguna untuk mempercepat pencarian dengan menhindari worst case.


Avl tree hanya boleh maksimal memiliki perbedaan 1 level antara subtree kiri dan subtree kanan. Sehingga dengan avl tree keceptan dan waktu pencarian data dapat dipersingkat.


Terdapat dua cara yang membantu menyederhanakan binary search tree yaitu dengan single rotation dan Double Rotation.


Single rotation yaitu setiap node bergerak ke kanan/kiri dari posisi awal


Double rotation yaitu kombinasi dari single rotation yaitu dengan setiap node bergerak satu posisi ke kanan/kiri lalu ke kanan/kiri lagi dari posisi awal


AVL tree berguna untuk memberikan keuntungan dimana kita membuat database yang data inputan dan data yang kita delete tidak sesering itu tetapi kita harus sering mencari data data yang ada disana.

Heap Tree

 Heap tree merupakan Complete Binary Tree atau merupakan Binary Tree juga  yang biasa juga disebut Complete Binary Search Tree (CBT) dimana harga - harga key pada node node nya sedemikian rupa sehingga harga harga key pada node node anaknya tidak ada yang lebih besar daru harga key pada node orang tuanya.


Pertama kali operasi yang harus dilakukan di Heap tree adalah Heapufy yaitu proses untuk menciptakan data struktur heap dari sebuah binary tree yang digunakan untuk menciptakan heap min dan heap max.


1. Masukkan inputan
2. Mulai dari index pertama dari non leaf node yang indexnya n/2-1;
3. Set current elemen i menjadi yang terbesar
4. Index dari node anak bagian kiri diberikan 2i + 1 dan node anak bagian kanan diberkan 2i+2.
Jika anak bagian kiri lebih besar dari current element/index ke i, maka set index anak bagian kiri menjadi yang terbesar.
Jika anak bagian kanan lebih besar dari element yang terbesar maka set index anak bagian kanan menjadi yang terbesar.
5. Tukar element yang terbesar dengan current element
6. Ulangi step hingga semua subtree terkena heapify.

RBT

RBT / Red Black Tree merupakan self balancing binay tree yang node nya mempunyai warna yaitu merah atau hitam. 

Red Black Tree Properties :

1. Setiap node yang ada di Red Black Tree mempunyai warna yaitu merah atau hitam 

2. Root dari tree tersebur selalu hitam

3. Node yang berwarna merah selalu mempunyai node anak yang berwarna hitam 

4. Setiap path dari node roor ke node NULL(leaf) mempunyai jumlah angka yang sama dari node yang berwarna hitam 

Red Black Tree dengan n keys mempunyai tinggi h <= 2 log(n+1)

Operasi yang terdapat di Red Black Tree yaitu :

1. Rotate semua subtree yang ada di Red Black Tree

Di operasi ini, posisi dari node yang berupa subtree dipertukarkan.

Operasi ini digunakan untuk maintain properti dari red black tree jika mereka melanggar oleh operasi lain seperti Insertion dan deletion.

2. Insertion 

Pada saat insert node baru, node baru selalu diinsert sebagai node yang berwarna merah. Setelah insert node baru, lalu jika tree melanggar properti dari Red Black Tree, maka kita harus melakukan operasi ini yaitu Recolor dan Rotasi

3. Deletion 

Setelah men-delete suatu node maka kita harus maintain kemabali operasi Red Black Tree