Hash Table & Binary Tree

Hash Table & Binary Tree


Hash Table

Hash Table adalah struktur data yang mempunyai tabel dan fungsi yang berguna untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Berikut adalah contohnya yang saya ambil dari geeksforgeeks;


Operasi Pada Hash Tabel :
  1. Insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
  2. Find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
  3. Remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
  4. GetIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

Berikut kode yang saya dapatkan dari tutorialspoint.com : 

#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");
   }
}

Binary Tree

Pohon biner atau binary tree adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.

Image result for binary tree



Comments

Post a Comment

Popular posts from this blog

AVL Tree

Image
AVL Tree AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu). Contoh Gambar AVL Tree Node AVL Tree, karena  balance factor tertingginya 2, sedangkan syarat AVL adalah selisihnya maksimal 1 Cara menentukan Height dan Balance Factor :Note : Height : – Jika node (root) tidak memiliki subtree heightnya = 0 – Jika node adalah leaf, height =  1 – Jika internal node, maka height =  height tertinggi dari anak + 1 Balance Factor : -selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0. Penambahan node di AVL Tree      Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan.   Proses penyeimbangan dilakukan dengan:   Single rotation  dan  Double rotation Single Rotation Single rotatio
Read more

Binary Search Tree

Image
Binary Search Tree Apa itu Binary Serach 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 . Ada beberapa cara dalam menggunakan 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. Berikut saya lampirkan gambarnya : Berikut saya lampirkan contoh codingan yang saya ambil dari mahircoding.com : #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
Read more