Skip to main content
Hash Table & Binary Tree

Hai lagi semuanya saya Viriyaputra Lawijaya, kembali lagi dengan blog saya yang membahas data structure. Sekarang saya mau membahas data structure lanjutan yaitu Hash Table dan Binary Tree, semoga blog ini dapat membantu kalian mempermudah mempelajari dan memahami hash table dan binary tree.

I. Hash Table
Jadi hash table itu adalah cara untuk memasukan data data ke sebuah tempat yang sudah ditentukan dengan lebih cepat dari biasanya. Di dalam hash table biasanya menggunakan fungsi hashing untuk menentukan data data yang dimasukan.
Berikut saya akan berikan contoh kode yang saya dapat dari tutorialspoint.com, terima kasih kepada tutorialspoint.com karena telah memberikan kode yang jelas dan mudah dipahami.

Contoh kode : 

#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;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
      //wrap around the table
      hashIndex %= SIZE;
   }
   hashArray[hashIndex] = item;
}

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

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      }
      //go to next cell
      ++hashIndex;
      //wrap around the table
      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(4, 25);
   insert(12, 44);
   insert(14, 32);
   insert(17, 11);
   insert(13, 78);
   insert(37, 97);

   display();
   item = search(37);

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

   delete(item);
   item = search(37);

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



II. Binary Tree
Binary Tree adalah sebuah tree yang setidaknya setiap node nya mempunyai dua anakan.
Sebelum itu saya akan menjelaskan sedikit mengenai apa itu tree yang dimaksud, kalau di blog ini kalian sudah mempelajari tentang stack dan queue itu merupakan linear linked list sedangkan tree itu non-linear linked list. Bayangkan ada sebuah angka dan dia bercabang ke bawah seperti akar akar. nah akar akar itu merupakan anakan dari node node tersebut. Sebuah tree dikatakan tree apabila ia saling terhubung tetapi tidak membentuk sebuah siklus.

Untuk mempermudah pemahaman kita langsung saja ke kode nya lagi, kali ini saya mendapatkan contoh kode dari codesdope.com, terima kasih lagi terhadap codesdope..com karena telah menyediakan contoh kode untuk dipelajari.

Contoh kode Binary Tree:

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

typedef struct tree_node {
  char data;
  struct tree_node *right;
  struct tree_node *left;
  struct tree_node *parent;
}tree_node;

tree_node* new_tree_node(char data) {
  tree_node *n = malloc(sizeof(tree_node));
  n->data = data;
  n->right = NULL;
  n->left = NULL;
  n->parent = NULL;

  return n;
}

typedef struct tree {
  tree_node *root;
}tree;

tree* new_tree(tree_node *n) {
  tree *t = malloc(sizeof(tree));
  t->root = n;

  return t;
}

int main() {
  /*

           D
          / \
         /   \
        /     \
       A       F
      / \     / \
     /   \   /   \
    E     B R     T
   / \     /     / \
  G   Q   V     J   L
*/

  tree_node *d, *a, *f, *e, *b, *r, *t1, *g, *q, *v, *j, *l;
  d = new_tree_node('D');
  a = new_tree_node('A');
  f = new_tree_node('F');
  e = new_tree_node('E');
  b = new_tree_node('B');
  r = new_tree_node('R');
  t1 = new_tree_node('T');
  g = new_tree_node('G');
  q = new_tree_node('Q');
  v = new_tree_node('V');
  j = new_tree_node('J');
  l = new_tree_node('L');

  tree *t = new_tree(d);

  t->root->right = f;
  t->root->left = a;

  /*

         D
        / \
       /   \
      /     \
     A       F
  */

  a->right = b;
  a->left = e;

  f->right = t1;
  f->left = r;

  e->right = q;
  e->left = g;

  r->left = v;

  t1->right = l;
  t1->left = j;

  return 0;
}


Sekian untuk blog saya kali ini, apabila ada kesalahan kata mohon dimaafkan. Terima kasih banyak dan sampai jumpa lagi di blog selanjutnya.

Nama : Viriyaputra Lawijaya
NIM : 2301866845

Comments

Post a Comment