Binary Tree dan Hash Table


Hash Table

Apa itu hash table?
Hash table adalah suatu tipe data structure yang meliputi:
  • Array
  • Linked List

Bentuk umum hash table dalam bahasa C:
Struct Node{
               int data;
               Node* left;
               Node* right;
}
Struct HashTable{
               Node* head;
               Node* tail;
}
HashTable hash[10]; // Tentukan array sizenya terlebih dahulu
Nah, suatu data ini bisa masuk ke suatu index dalam array dengan menggunakan rumus sebagai berikut:

Size of array: bilangan % arraySize.

Misal angka bilangan di dalam suatu data adalah 10 dan arraySize adalah 13, maka Ia akan diletakkan di index nomor 10.

Tidak harus bilangan saja, anda bisa menggunakan library khusus untuk mengenerate random number agar bisa disimpan di lokasi index tertentu, misalnya rand() % arraySize untuk bahasa C dan C++ atau menghitung masing-masing karakter di dalam string agar nanti dimodulokan dengan arraySize.

Hash table memiliki operasi khusus sebagai berikut:
  • Insertion
  • Delete
  • Search

Contoh implementasi kode dalam bahasa C:
#include <stdio.h>
#include <stdlib.h>
struct Hash{
               struct Node* head;
               struct Node* tail;
};
struct Node{
               int value;
               Node* next;
               Node* prev;
};
Node* curr = NULL;
Hash hashTable[10] = {};
Node* oneNode(int value){
               curr = (Node*) malloc(sizeof(Node));
               curr->value = value;
               curr->next = NULL;
               curr->prev = NULL;
               return curr;
}

void pushHead(Node* newNode, int arraySize){
               int locationData = newNode->value % arraySize;
               if (hashTable[locationData].head == NULL){
                              hashTable[locationData].head = newNode;
                              hashTable[locationData].tail = newNode;
               }
               else{
                              hashTable[locationData].tail->next = newNode;
                              newNode->prev = hashTable[locationData].tail;
                              hashTable[locationData].tail = hashTable[locationData].tail->next;
                              hashTable[locationData].tail->next = NULL;
               }
}
void popMiddle(int value, int maxSize){
               int locationIndex = value % maxSize;
               if (hashTable[locationIndex].head == NULL){
                              printf("No data.\n");
               }
               else if(hashTable[locationIndex].head == hashTable[locationIndex].tail){
                              curr = hashTable[locationIndex].head;
                              hashTable[locationIndex].head = NULL;
                              hashTable[locationIndex].tail = NULL;
                              free(curr);
               }
               else if (hashTable[locationIndex].head->value == value){
                              curr = hashTable[locationIndex].head;
                              hashTable[locationIndex].head = hashTable[locationIndex].head->next;
                              hashTable[locationIndex].head->prev = NULL;
                              free(curr);
               }
               else if (hashTable[locationIndex].tail->value == value){
                              curr = hashTable[locationIndex].tail;
                              hashTable[locationIndex].tail = hashTable[locationIndex].tail->prev;
                              hashTable[locationIndex].tail->next = NULL;
                              free(curr);
               }
               else{
                              curr = hashTable[locationIndex].head;
                              while (curr != NULL && curr->value != value){
                                             curr = curr->next;
                              }
                              if (curr == NULL){
                                             printf("No data!\n");
                              }
                              else{
                                             printf("Reached here!\n");
                                             curr->prev->next = curr->next;
                                             curr->next->prev = curr->prev;
                                             curr->next = NULL;
                                             curr->prev = NULL;
                                             free(curr);
                              }
                             
               }
}
void searchNode(int size){
               for (int i = 0; i < size; i++){
                              curr = hashTable[i].head;
                              printf("%d: ", i+1);
                              while (curr != NULL){
                                             printf("%d ", curr->value);
                                             curr = curr->next;
                              }
                              printf("\n");
               }
}
int main(){
               printf("============A hash table simulator===========\n");
               printf("Please enter how many data to be inserted: ");
               int size = 0;
               scanf("%i", &size);
               int number = 0;
               for (int i = 0; i < size; i++){
                              printf("Please state the number: ");
                              scanf("%i", &number);
                              pushHead(oneNode(number), 10);
               }
               searchNode(10);
               printf("Please enter how many data to be deleted: ");
               scanf("%i", &size);
               for (int i = 0; i < size; i++){
                              printf("Please state the number: ");
                              scanf("%i", &number);
                              popMiddle(number, 10);
               }
               searchNode(10);
printf(“\n”);
               printf(“Thank you for using the app.\n”);
               return 0;

}
Insertion dan deletion di atas hampir mirip dengan linked list biasa, jadi Anda harus memahami Linked List dulu agar bisa memahami operasi-operasi di atas.

Nah, berikut ini adalah salah satu aplikasi hash table di dunia nyata:

Blockchain

Hash table memiliki peran penting dalam blockchain. Ia menggunakan distributed hash tables. Hash table ini adalah suatu bentuk distributed database yang bisa menyimpan informasi dalam bentuk key/value pairs. Key/value pairsnya disimpan di dalam Distributed Hash Table, sehingga jika kita ingin mengambil data dengan key spesifik, kita bisa mengambilnya dengan sangat cepat. Keys ini harus unik dan berbeda dengan yang lainnya. Pada akhirnya, Ia bisa menampung node-node di dalam hash table yang sangat besar dan menangani node-node baru dan node-node yang keluar.

Hashing di blockchain menggunakan SHA - 256. Ia mengambil suatu string yang nantinya akan dikonversi menggunakan hashing tersebut.

Distributed Hash Table ini memiliki fungsi untuk membuat service-service yang lebih spesifik untuk operasi web, seperti web caching, distributed file systems, domain name services, instant messaging, multicast, peer-to-peer file sharing, dan sistem distribusi konten.

Binary Tree
Sumber: https://www.geeksforgeeks.org/binary-tree-data-structure/
Apa itu binary tree?
Binary tree adalah suatu salah satu tipe data structure yang menyerupai bentuk binary tree. Binary tree memiliki struktur sebagai berikut:
  • Left Node
  • Right Node
  • Data-data yang ingin dimasukkan, misalnya int, float, char[], dan sebagainya

Binary tree merupakan konsep data structure yang berupa hierarchy, tidak seperti linked list, hash table, stack, queue. Hirearchy ini bisa direpresentasikan dalam bentuk pohon keluarga yang merepresentasikan hubungan antar keuarga.

Binary tree ini juga memiliki suatu ketinggian dimana Ia menunjukkan panjang maksimum dalam binary tree tersebut.

Binary tree memiliki operasi-operasi yang sama seperti linked list, yaitu:
  • Insertion (memasukkan data)
  • Deletion (menghapus data)
  • Searching (mencari data)

Proses-proses ini sedikit berbeda dibandingkan linked list dan hash table, karena tree ini mengusung konsep hierarchy, bukan linear. Proses-proses ini dilakukan dengan menggunakan BFS (Breadth-First-Search) yang umumnya dipakai dalam graph.  

Untuk melakukan BFS, kita membutuhkan satu linked list dalam C atau satu Vector / ArrayList dalam Java. Nah, proses ini dilakukan dengan mengusung konsep queue (FIFO: First in, first out). Oleh karena itu, kita mengusung konsep pushTail dan popHead.

Di bawah adalah implementasi insertion dan searching binary tree dalam bahasa C. Anda bisa lihat bahwa kita sekarang memiliki 2 struct. Satu struct merupakan representasi asli dari binary tree, yang lainnya merupakan linked list agar bisa melakukan queue.

#include <stdio.h>
#include <stdlib.h>
struct LinkedListNode{
               struct TreeNode* refNode;
               struct LinkedListNode* next;
} typedef LinkedListNode;

struct TreeNode{
               int data;
               struct TreeNode* left;
               struct TreeNode* right;
} typedef TreeNode;

LinkedListNode* currLinkedList = NULL;
TreeNode* root;
LinkedListNode* headLinkedList = NULL;
LinkedListNode* tailLinkedList = NULL;
TreeNode* tempTreeNode = NULL;

LinkedListNode* oneNode(TreeNode* newNode){
               currLinkedList = (LinkedListNode*) malloc(sizeof(LinkedListNode));
               currLinkedList->refNode = newNode;
               currLinkedList->next = NULL;
               return currLinkedList;
}

TreeNode* oneTreeNode(int value){
               tempTreeNode = (TreeNode*) malloc(sizeof(TreeNode));
               tempTreeNode->data = value;
               tempTreeNode->left = NULL;
               tempTreeNode->right = NULL;
}

void pushTail(LinkedListNode* newNode){
               if (headLinkedList == NULL){
                              headLinkedList = newNode;
                              tailLinkedList = newNode;
               }
               else{
                              tailLinkedList->next = newNode;
                              tailLinkedList = tailLinkedList->next;
               }
}

TreeNode* popHead(){
               if (headLinkedList != NULL){
                              currLinkedList = headLinkedList;
                              headLinkedList = headLinkedList->next;
                              return currLinkedList->refNode;
               }
               else{
                              return NULL;
               }
}

TreeNode* insertNode(TreeNode* newNode, TreeNode* currentNode){
               if (root == NULL){
                              return newNode;
               }
               if (currentNode->left != NULL && currentNode->right != NULL){
                              pushTail(oneNode(currentNode->left));
                              pushTail(oneNode(currentNode->right));
               }
               printf("Checking... %i\n", currentNode->data);
               if (currentNode->left == NULL){
                              currentNode->left = newNode;
                              return;
               }
               else if (currentNode->right == NULL){
                              currentNode->right = newNode;
                              return;
               }
               else{
                              TreeNode* checkNode = popHead();
                              return insertNode(newNode, checkNode);
               }
}

void eraseDataLinkedList(){
               while (headLinkedList != NULL){
                              currLinkedList = headLinkedList;
                              headLinkedList = headLinkedList->next;
                              free(currLinkedList);
               }
               headLinkedList = NULL;
               currLinkedList = NULL;
}

void searchUsingBFS(){
               pushTail(oneNode(root));
               tempTreeNode = popHead();
               while (tempTreeNode != NULL){
                              printf("%i ", currLinkedList->refNode->data);
                              if (tempTreeNode->left != NULL){
                                             pushTail(oneNode(tempTreeNode->left));
                              }
                              if (tempTreeNode->right != NULL){
                                             pushTail(oneNode(tempTreeNode->right));
                              }
                              tempTreeNode = popHead();
               }
}


int main(){
               printf("=============A binary tree simulator=============\n");
               printf("How many data to be inserted?");
               int numberOfData = 0;
               scanf("%i", &numberOfData);
               int data = 0;
               int i = 0;
               for (i = 0; i < numberOfData; i++){
                              printf("Please insert the data (%i): ", i+1);
                              tempTreeNode = root;
                              scanf("%i", &data);
                              if (root == NULL){
                                             root = insertNode(oneTreeNode(data), tempTreeNode);
                              }
                              else{
                                             insertNode(oneTreeNode(data), tempTreeNode);
                              }
                              eraseDataLinkedList();
               }
               printf("Searching using breadth first traversal: ");
               searchUsingBFS();
               eraseDataLinkedList();
               return 0;
}
Untuk deletion, prosesnya tinggal mencari node yang paling kanan berdasarkan prosedut BFS (Breadth-First-Search) yang dimulai dari root.

Salah satu implementasi dari binary tree adalah dalam file processing. Anda bisa lihat sendiri di program Windows Explorer dan setiap folder memiliki isi filenya masing-masing. Tujuan folder tersebut adalah mengrup suatu file-file menjadi satu dan proses groupingnya dilakukan berdasarkan konsep binary tree.

Comments

Post a Comment

Popular posts from this blog

Heap

Image
Halo semuanya, setelah kita belajar macam-macam balancing tree (AVL Tree, Red Black Tree, dan B-Tree), maka sekarang kita akan belajar tree yang direpresentasikan dalam bentuk array, yaitu heap. Apa itu heap? Heap adalah salah satu varian dari binary tree, namun Ia memiliki prinsip dan aturan sebagai berikut: Heap adalah binary tree yang direpresentasikan dalam bentuk array. Untuk melakukan traverse node dari heap, kita tidak menggunakan cara recursive, namun menggunakan proses iteratif. Berikut ini adalah contoh gambar dari heap: Sumber:   https://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Max-Heap.svg/1200px-Max-Heap.svg.png Jika direpresentasikan dalam bentuk array, maka terlihat sebagai berikut: Index 0 1 2 3 4 5 6 7 8 Value 100 19 36 17 3 25 1 2 7 Catatan: Heap selalu berupa balanced binary tree. Heap ini memiliki 3 varian, yaitu...
Read more

AVL Tree

Image
AVL Tree AVL Tree secara dasarnya sama seperti Binary Search Tree yang umumnya, namun tree ini memiliki perbedaan-perbedaan yang mendasar: Bisa dibilang bahwa tree ini hampir selalu berupa perfect binary tree. Hal ini terjadi karena AVL Tree mengoptimasi cabang-cabang anakannya sehingga cabangnya tidak terlalu ke kiri atau ke kanan Akibatnya, perbedaan ketinggian pada setiap cabang yang terdapat di tree ini tidak boleh lebih dari 1. Inilah yang kita sebut sebagai Balanced Binary Tree. Berikut ini adalah contoh perbandingan gambar AVL Tree dan yang bukan: Kiri – Bukan AVL Tree karena perbedaan ketinggian di node 8 dan 18 lebih dari 1, namun gambar kanan memenuhi persyaratan AVL Tree Sumber: https://www.geeksforgeeks.org/avl-tree-set-1-insertion/ Mengapa AVL Tree perlu dipakai? Bayangkan jika kita menggunakan binary search tree. Jika kita lihat, anakan yang lebih besar dari parentnya, maka nodenya ditaruh di kanan dan sebaliknya. Bagaimana jika data ya...
Read more