Selasa, 17 Maret 2020

Binary Search Tree

200px-Binary_search_tree.svg

Apa sih Binary Search Tree itu?

Binary Search Tree atau BST adalah suatu struktur data binary tree (pohon biner) yang berbasis simpul. binary Search Tree memiliki beberapa properti, seperti :

  • Subtree kiri dari suatu node hanya berisi node-node dengan kunci yang lebih rendah daripada kunci node (node key).
  • Subtree kanan dari suatu node hanya berisi node-node dengan kunci yang lebih besar daripada kunci node (node key).
  • Subtree kiri dan kanan masing-masing juga harus berupa sebuah Binary Search Tree.
*dengan asumsi kunci berbeda.

Binary Search Tree (BST) adalah salah satu struktur data yang mendukung pencarian yang lebih cepat, penyortiran yang cepat, dan penyisipan (insertion) dan penghapusan (deletion) yang lebih mudah. Binary Search Tree (BST) juga dikenal sebagai Sorted Version of Binary Tree.

Basic operation yang ada pada Binary Search Tree (BST), yaitu :
  • Search
  • Insert
  • Deletion
  • Pre-Order Traversal
  • In-Order Traversal
  • Post-Order Traversal
Yang akan kita bahas sekarang ada 3, yakni :
  1. Insertion
  2. Searching
  3. Deletion

Searching

Untuk mencari kunci yang diberikan (given key) di Binary Search Tree, pertama kali kita akan membandingkannya dengan akar/root. JIka kunci (key) berada di root, maka kita akan me-return root. Jika kunci (key) lebih besar daripada kunci (key) yang ada di root, kita akan melakukan pengulangan untuk Subtree kanan dari simpul root. JIkalau tidak, maka kita akan melakukan pengulangan untuk Subtree kiri.

Ilustrasi untuk mencari 6 di tree di bawah ini :
  1. Cari di akar
  2. Bandingkan elemen yang di input dengan akar, jika lebih kecil daripada root, kemudian lakukan pencarian berulang pada bagian kiri atau lakukan pencarian berulang pada bagian kanan.
  3. Jika elemen untuk pencarian di temukan di manapun, return true, jikalau tidak, return false.

200px-Binary_search_tree.svg

Contoh codingan :


struct node* search(struct node* root, int key) 
    // Base Cases: root is null or key is present at root 
    if (root == NULL || root->key == key) 
       return root; 
     
    // Key is greater than root's key 
    if (root->key < key) 
       return search(root->right, key); 
  
    // Key is smaller than root's key 
    return search(root->left, key); 
}

Insertion

Kunci (key) baru akan selalu dimasukkan (di insert) di daun. Kita memulai untuk mencari sebuah kunci (key) dari root/akar sampai menyentuh sebuah leaf node. Sekali sebuah leaf node ditemukan, node baru akan ditambahkan sebagai anak dari leaf node.

Ilustrasi untuk menambahkan (insert) 2 di tree di bawah ini :
  1. Dimulai dari root
  2. Bandingkan elemen yang ditambahkan (di insert) dengan root/akar, jika lebih kecil dari root, maka lakukan pengulangan untuk bagian kiri. Selain itu, bisa juga melakukan pengulangan untuk bagian kanan.
  3. Setelah mencapai akhir, cukup masukkan simpul itu di kiri (jika kurang dari current). Jika lebih dari current, masukkan simpul di kanan.
bstsearch

Contoh coding untuk insertion :

/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key) 
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key); 
  
    /* Otherwise, recur down the tree */
    if (key < node->key) 
        node->left  = insert(node->left, key); 
    else if (key > node->key) 
        node->right = insert(node->right, key);    
  
    /* return the (unchanged) node pointer */
    return node; 
}

Deletion

Ada 3 kasus yang harus di pertimbangkan :
  1. Jika kunci (key) berada di leaf, hapus saja node itu.
  2. Jika kunci (key) ada di sebuah node yang tidak memiliki chid, hapus node tersebut dan hubungkan child dengan parent nya.
  3. Jika kunci (key) ada di node yang memiliki 2 children (anak), temukan child yang paling kanan dari sub-tree (simpul P), ganti kuncinya dengan kunci P dan delete P secara rekursif. Atau bisa secara bergantian memilih child paling kiri dari sub-tree kanan.
Contoh coding untuk deletion :

/* Given a binary search tree and a key, this function deletes the key 
   and returns the new root */
struct node* deleteNode(struct node* root, int key) 
    // base case 
    if (root == NULL) return root; 
  
    // If the key to be deleted is smaller than the root's key, 
    // then it lies in left subtree 
    if (key < root->key) 
        root->left = deleteNode(root->left, key); 
  
    // If the key to be deleted is greater than the root's key, 
    // then it lies in right subtree 
    else if (key > root->key) 
        root->right = deleteNode(root->right, key); 
  
    // if key is same as root's key, then This is the node 
    // to be deleted 
    else
    { 
        // node with only one child or no child 
        if (root->left == NULL) 
        { 
            struct node *temp = root->right; 
            free(root); 
            return temp; 
        } 
        else if (root->right == NULL) 
        { 
            struct node *temp = root->left; 
            free(root); 
            return temp; 
        } 
  
        // node with two children: Get the inorder successor (smallest 
        // in the right subtree) 
        struct node* temp = minValueNode(root->right); 
  
        // Copy the inorder successor's content to this node 
        root->key = temp->key; 
  
        // Delete the inorder successor 
        root->right = deleteNode(root->right, temp->key); 
    } 
    return root; 
}

Contoh Deklarasi Awal

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Contoh Coding untuk Search Operation

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
   while(current->data != data){
      if(current != NULL) {
         printf("%d ",current->data);
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }
//else go to right tree
         else {                
            current = current->rightChild;
         }
         //not found
         if(current == NULL){
            return NULL;
         }
      }
   }
   
   return current;
}

Contoh Coding untuk Insert Operation

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;  
              
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
//go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}



Terima kasih :)




Referensi : 

Selasa, 10 Maret 2020

Hashing and Hash Table, Trees & Binary Tree

Pada kesempatan kali ini, saya akan membahas tentang Hashing and Hash Table, Trees & Binary Tree.

Hashing and Hash Table

Hashing


Hashing adalah suatu teknik yang di gunakan untuk mengidentifikasi objek tertentu dari sekelompok objek yang serupa dengan cara yang unik. Hashing dapat di gunakan dalam kehidupan kita, sebagai contoh :
  • Di universitas, setiap mahasiswa memiliki NIM yang terdiri dari angka-angka yang berbeda amtar satu mahasiswa dengan mahasiswa yang lain. Saat kita ingin mencari data tentang seorang mahasiswa, kita dapat menggunakan NIM yang dimiliki oleh mahasiswa tersebut.
Hashing merupakan struktur data penting yang dirancang untuk menggunakan suatu fungsi khusus yang di panggil "The Hash Function" yang digunakan untuk memetakan nilai yang telah diberikan dengan kunci tertentu untuk akses ke elemen yang lebih cepat. Efisiensi dari pemetaan ini tergantung dari efisiensi dari "The Hash Function" yang digunakan.


Dalam hashing, string of characters di transformasikan ke dalam panjang nilai yang biasanya lebih pendek atau ke dalam kunci yang merepresentasikan/mewakili string yang asli. 

Hashing digunakan untuk mengindeks dan mengambil item di suatu database karena pencarian item lebih cepat untuk ditemukan dengan menggunakan hashed key yang lebih pendek daripada menemukan item tersebut menggunakan nilai asli.

Hashing juga bisa didefinisikan sebagai konsep mendistribusikan kunci(key) dalam suatu array yang disebut "Hash Table" dengan menggunakan fungsi yang telah ditentukan, yaitu "Hash Function".

Hashing di implementasikan dalam 2 langkah, yaitu:

1. Elemen dikonversikan kedalam suatu integer dengan menggunakan "Hash Function". Elemen ini dapat digunakan sebagai suatu index untuk menyimpan elemen asli yang jatuh ke hash table.

2. Elemen ini disimpan di hash table dimana dia bisa diambil dengan cepat menggunakan hashed key.

hash = hashfunc(key)
index = hash%array_size

Pada metode ini, hash tidak tergantung pada ukuran array dan kemudian dia akan dikecilkan menjadi suatu index (angka antara 0 dan array_size - 1) dengan menggunakan operator modulo (%).

Hash Table

Hash table adalah suatu struktur data yang digunakan untuk menyimpan keys/value pairs. Hash table menggunakan suatu hash function (fungsi hash) untuk menghitung suatu index ke dalam suatu array dimana suatu elemennya akan dimasukkan atau dicari. Dengan menggunakan suatu hash function yang baik, hashing dapat bekerja dengan baik pula.

Hash table adalah sebuah tabel yang berbetuk array dimana di dalamnya kita menyimpan string asli. Indeks dari tabelnya adalah hashed key sementara nilainya adalah nilai dari string asli. 

Ukuran dari hash table biasanya beberapa urutan yang besarannya lebih rendah daripada jumlah total dari string yang memungkinkan. Jadi, beberapa string mungkin akan memiliki kunci hash (hashed key) yang sama.

Operasi dasar yang ada dalam hash table :
  • Search
  • Insert
  • Delete
Data item yang digunakan dalam hash table

struct DataItem {
   int data;
   int key;
};

Search Operation

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;     

}

Insert Operation

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;     

}

Delete Operation

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;     

}

Hash Function

Hash function adalah suatu fungsi yang mengubah nomor telepon yang besar menjadi nilai integer praktis yang kecil. Nilai integer yang dipetakan digunakan sebagai suatu index di dalam hash table. Sederhananya, suatu hash function memetakan sejumlah angka atau string yang besar kedalam suatu integer yang kecil yang dapat digunakan sebagai index di dalam hash table.

Hash function yang baik harus memiliki properti sebagai berikut :

  1. Dihitung secara efisien
  2. Harus mendistribusikan kunci(keys) secara seragam (setiap posisi tabel memiliki kemungkinan yang sama untuk setiap kunci)
Ada banyak cara untuk meng-hash suatu string ke dalam suatu key. Berikut ini adalah beberapa method-method penting untuk membangun fungsi hash :
  • Mid-square
  • Division (paling umum)
  • Folding
  • Digit Extraction
  • Rotating Hash
1. Mid-square

Dalam mid-square, kita akan mempangkatkan semua nilainya. Singkatnya, semua nilai yang diberikan kepada kita akan kita pangkat 2 kan. 

Function : h(k) = s
keterangan :
k = key
s = hash key yang diperolah dengan memilih r bits dari k pangkat 2

Dalam teknik ini, semua nilai dari kunci(key) akan kita ambil dan kuadratkan. Kemudian, beberapa digit angka dari tengah akan kita ekstraksi. Angka-angka yang sudah diekstrak akan membentuk angka yang dapat kita ambil sebagai nilai kunci(key) baru. Teknik ini dapat menghasilkan key(kunci) dengan tingkat ke acakan yang tinggi jika nilai yang cukup besar yang kita ambil. Namun, hal ini tentunya memiliki batasan. Saat nilai dari kunci(key) kita kuadratkan, jika angka 6-digit diambil, maka hasil kuadrat dari angka tersebut akan memiliki angka sebanyak 12-digit. Ini akan melebihi kisaran tipe data integer. Jadi, jika terjadi overflow, gunakan tipe data integer yang panjang atau gunakan string sebagai perkalian jika luapan masih terjadi.

Contoh :

Misalkan diambil 4 digit benih.
Benih = 4765
Hasil kuadrat dari benih = 22705225
Dari angka yang berjumlah 8-digit ini, kita akan melakukan ekstraksi (Katakan, 4 tengah)
Jadi, nilai benih baru = 7052
Lalu, kuadratkan nilai dari benih baru (7052)
Hasil kuadrat nilai dari benih baru = 49730704
.
.
.
Proses seperti ini akan berlangsung sebanyak yang diperlukan dari suatu kunci.

2. Division

Pada teknik division, kita akan menggunakan operator modulus (%), dimana string/value yang diberikan akan kita moduluskan dengan sejumlah memori.

Function : h(z) = z % M
keterangan :
z = key
M = nilai yang digunakan untuk membagi kunci, biasanya menggunakan angka prima, ukuran tabel, atau ukuran dari memori yang digunakan.

Contoh :
z = 1276
M = 10
h(1276) = 1276 % 10
h(1276) = 6

nilai hash yang diperoleh adalah 6

Kekurangan dari method division ini adalah kunci yang berturut-turut akan memetakan ke nilai hash yang berturut-turut di dalam tabel hash. Ini akan menyebabkan kinerja yang kurang baik.

3. Folding

Folding akan memecahkan string/identifier menjadi beberapa bagian, lalu ditambahkan bagian yang bersama-sama untuk mendapatkan hash key.

Step-step yang akan dilakukan :
  • Membagi nilai key kedalam beberapa bagian
  • Tambahkan bagian individual (biasanya carry terakhir diabaikan)
Contoh :

Diberikan sebuah hash table dari 100 lokasi, hitung nilai hash dari 5678, 321, 34567. Dikarenakan terdapat 100 alamat lokasi, jadi kita akan bagi key kedalam beberaoa bagian dimana setiap bagian akan mengandung 2 digit.


4. Digit Extraction

Sebuah digit yang telah di tentukan sebelumnya yang berasal dari nomor yang diberikan, dianggap sebagai alamat dari hash.

Contoh :

Misal :
x = 14,568
Jika kita mengekstrak digit 1, 3, dan 5, kita akan mendapatkan kode hash 158.

5. Rotating Hash

Menggunakan method hash apa saja(seperti division atau mid-square method). Setelah mendapatkan kode/alamat hash dari metode hash, lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash yang baru.

Contoh :

Misal :
Alamat hash yang diberikan = 20021
Hasil rotasi = 12002 (Folding pada digit)

Collision

Dalam bahasa indonesia, collision dikenal sebagai tabrakan.

Dikarenakan fungsi hash memberikan kita sebuah angka kecil untuk sebuah kunci(key) yang merupakan bilangan integer besar atau string. Ada kemungkinan bahwa dua kunci(key) menghasilkan nilai yang sama. Situasi dimana sebuah peta kunci (key map) yang baru, dimasukkan ke dalam sebuah slot yang sudah ditempati pada tabel hash disebut collision(Tabrakan) dan harus ditangani menggunakan beberapa teknik penanganan collision(collision handling technique).

Ada 2 cara untuk menangani Collision(tabrakan), yaitu :
  1. Linear Probing
  2. Chaining

Linear Probing

Dilakukan dengan mencari slot yang kosong yang terletak setelah slot yang terisi dan menaruh string nya disana. Dia akan mencari terus hingga mendapatkan slot yang kosong.

Contoh program Linear Probing :

struct { ... } node;

node Table[M]; int Free;
/* insert K */
addr = Hash(K);

if (IsEmpty(addr)) Insert(K,addr);
else {
/* see if already stored */

test:
if (Table[addr].key == K) return;
else {
addr = Table[addr].link; goto test;}
/* find free cell */
Free = addr;

do { Free--; if (Free<0) Free=M-1; }
while (!IsEmpty(Free) && Free!=addr);

if (!IsEmpty(Free)) abort;
else {
Insert(K,Free); Table[addr].link = Free;
}

}

Chaining

Dilakukan dengan menaruh string di dalam sebuat slot sebagai sebuah chained list(linked list).


Hash dan Perannya pada Sistem Keamanan Blockchain

Peran penting kriptografu dalam jaringan blockchain terus berkembang tiada henti. Salah satunya adalah proses perhitungan sebuah data secara konkret dan unik. Metode ini dikenal dengan Hash, kode unik yang banyak ditemukan di Blockchain adalah salah satu contoh Hash. Untuk menghindari sebuah data dibobol atau diketahui oleh orang lain adalah dengan pemberian kode unik. Dengan demikan, data tersebut akan aman dan pastinya menjadi orisinalitas data dari orang lain. Saat ini, beragam proses pengamanan data, mulai dari sidik jari dan sidik mata. Pada blockchain, digunakanlah kode unik(Hash).

Password atau kode unik di blockchain memiliki nilai karakter yang lebih panjang dan menggunakan kode yang unik sehingga proses peretasan dengan aplikasi tebak akan berlangsung sangat lama bahkan mustahil. Itulah yang menjadi alasan bahwa Hash sangat penting dan dinilai sangat aman.

Hash mampu mengubah setiap data yang mengalami perubahan dengan nilai unik sendiri. Ini yang tidak didapatkan pada jaringan biasa. Selain itu, setiap data dokumen dengan panjang berapa pun akan menghasilkan nilai hash yang punya nilai panjang yang berbeda, tergantung spesifikasi Hash yang digunakan.

1. SHA256

Merupakan Hash yang pertama sekali muncul dan digunakan di jaringan blockchain publik. Hash ini digunakan pada Bitcoin khusus proses transaksi dan perhitungan nilai Hash. Penggunaan SHA256 sudah mulai dicetus sejak tahun 2001 oleh NIST (NAstional Institute of Standard and Technology).


2. RIPEMD160

Merupakan singkatan dari Race Integrity Primitive Evaluation Message Digest. Konsepnya dikembangkan oleh MD4. Jumlah data transaksi yang dihasilkan lebih kecil dibandingkan SHA256 yaitu hanya 160 bit.


3. Beragam Hash pada Monero

Penerapan pada keamanan data menggunakan sejumlah Hash, mulai dari Keccak, Black, Grostl, JH, dan Skein pada CryptoNote. Kondep Monero yang sangat kompleks seakan membuatnya dijuluki sebagai fully anonymous. Monero menilai bahwa perlu adanya keamanan khusus dan beragam pada Hash menjadi dasar lahirnya konsep CryptoNote.


Tree and Binary Tree

Tree

Tree merupakan struktur data yang tidak linear yang digunakan untuk merepresentasikan data yang bersifat hirarki antara elemen-elemennya. Definisi tree yaitu kumpulan elemen yang salah satu elemennya disebut root(akar) dan elemen yang lain disebut simpul(node) yang terpecah menjadi sejumlah kumpulan yang tidak saling berhubungan satu dengan yang lain yang disebut sub-tree atau cabang.


Image result for istilah dalam tree

Binary Tree

Tree yang unsurnya paling banyak 2 anak disebut Binary Tree. Karena setiap elemen dalam pohon biner hanya dapat emiliki 2 anak, biasanya anak tersebut akan dinamakan left dan right child.


Node dari Binary Tree berisi bagian-bagian, yaitu :

  1. Data
  2. Pointer to left child
  3. Pointer to right child
Node yang tidak memiliki anak disebut leaf.

Jenis - Jenis Binary Tree

  • Full Binary Tree
Binary tree yang tiap node-nya(kecuali leaf) memiliki 2 anak dan tiap sub-tree harus mempunyai panjang path yang sama.



  • Complete Binary Tree
Mirip dengan Full Binary Tree, namun setiap sub-tree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.


  • Skewed Binary Tree
Binary tree yang semua nodenya (kecuali leaf) memiliki 1 child.


  • Binary Search Tree(BST)
Jenis pohon terurut yang digunakan unruk menyimpan data sehingga memudahkan pencarian kembali data tersebut.



Operasi Pada Tree

  • Create
DIgunakan untuk membentuk binary tree baru yang masih kosong.

  • Clear
Digunakan untuk mengosongkan binary tree yang sudah ada.

  • Empty
Diguakan untuk memeriksa apakah binary tree masih kosong.

  • Insert
Digunakan untuk memasukkan sebuah node ke dalam tree.

  • Find
Digunakan untuk mencari root, parent, left child, atau right child dari suatu node dengan syarat tree tidak boleh kosong.

  • Update
Digunakan untuk mengubah isi dari node yang ditunjuk oleh pointer cureent dengan syarat tree tidak boleh kosong.

  • Retrieve
Digunakan untuk mengetahui isi dari node yang ditunjuk pointer current dengan syarat tree tidak boleh kosong.

  • Delete Sub
Digunakan untuk menghapus sebuah sub-tree (node beserta seluruh descendant-nya) yang ditunjuk pointer current dengan syarat tree tidak oleh kosong.

  • Characteristic
Digunakan untuk mengetahui karakteristik dari suatu tree (size, height, serta everage length-nya).

  • Traverse
Digunakan untuk mengunjungi seluruh node-node pada tree, masing-masing sekali.

Representation of Binary Tree

Implementation using linked list

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

Expression Tree Concept

Prefix  : *+ab/-cde

Postfix : ab+cd-e*

Infix  : (a+b)*((c-d)/e)


Kita juga akan menggunakan struktur ini untuk setiap node didalam tree :

struct tnode {

  char chr;

  struct tnode *left;

  struct tnode *right;
};

Threaded Binary Tree Example

Image result for threaded binary tree example

Keuntungan

  • Memungkinkan lintasan linear elemen di tree
  • Tranversal linear menghilangkan penggunaan tumpukan yang pada gilirannya akan mengkonsumsi banyak ruang memori dan waktu komputer
  • Memungkinkan untuk menemukan induk dari elemen yang diberikan tanpa menggunakan pointer parent secara eksplisit
  • Karena node berisi pointer ke pendahulu dan penerus di in-order, tree berulir memungkinkan traversal maju dan mundur dari node seperti yang diberikan oleh mode in-order.

Contoh Coding Binary Tree

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






Referensi :
https://www.geeksforgeeks.org/hashing-data-structure/
https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.html
https://www.geeksforgeeks.org/what-are-hash-functions-and-how-to-choose-a-good-hash-function/
https://arisistemberkas.blogspot.com/2018/10/teknik-hashing.html
https://www.geeksforgeeks.org/mid-square-hashing/
https://www.tutorialspoint.com/Hash-Functions-and-Hash-Tables
https://greatnusa.com/course/view.php?id=178
https://www.geeksforgeeks.org/hashing-set-2-separate-chaining/
http://muqoddasrengmadureh.blogspot.com/2013/01/algoritma-dan-struktur-data-hashing.html
https://steemit.com/indonesia/@iqbalsweden/hash-dan-perannya-pada-sistem-keamanan-blockchain
https://slideplayer.info/slide/12575320/
https://www.geeksforgeeks.org/binary-tree-data-structure/
http://bocahngoding.blogspot.com/2018/01/pengertian-tree-pada-struktur-data.html
https://www.slideshare.net/SsankettNegi/threaded-binarytreeheapsort
https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/
Binus Maya Slides

Selasa, 03 Maret 2020

Stack and Queue

Apa sih Stack dan Queue itu?

Stack
Stack dapat diartikan sebagai tumpukan. Stack merupakan sebuah koleksi objek yang menggunakan LIFO (Last In Last Out). Apa sih maksud LIFO itu? Pada saat kita menambahkan/memasukkan elemen/data, maka data tersebut (yang terakhir ditambahkan) akan menjadi data yang pertama kali keluar dari tumpukan tersebut. Secara sederhana, data yang terakhir kali masuk adalah data yang pertama kali/terlebih dahulu keluar. Stack merupakan struktur data linier di mana elemen dapat dimasukkan dan dihapus hanya dari satu sisi daftar yang biasa disebut sebagai TOP. Penyisipan elemen ke dalam sebuah stack disebut PUSH. Penghapusan elemen dari stack disebut POP. Dalam stack, kita selalu melacak elemen terakhir yang ada dalam daftar dengan suatu pointer yang disebut TOP.

Representasi diagram stack dapat kita lihat dari gambar di bawah ini :

Stacks

Berikut ini adalah istilah-istilah yang ada dalam program stack :

  1. Push : berfungsi untuk menambah elemen pada suatu stack
  2. Pop : berfungsi untuk mengambil/menghapus elemen pada suatu stack
  3. Clear : berfungsi untuk mengosongkan stack
  4. IsEmpty : berfungsi untuk mengecek apakah stack sudah kosong atau belum
  5. IsFull : berfungsi untuk mengecek apakah stack sudah penuh

Berikut adalah contoh coding push dalam bahasa C

struct Data
{
    int value;
    struct Data *next,*prev;
}*head,*curr,*tail;

void push(int a)
{
    curr = (struct Data*)malloc(sizeof(struct Data));
    curr->value = a;
    
    if(head==NULL){
        head = tail = curr;
    }
    else{
        tail->next = curr;
        curr->prev = tail;
        tail = curr;
    }
    head->prev = tail->next = NULL;
}


void cetak()
{
    curr = head;
    while(curr!=NULL){
        printf("%d\n",curr->value);
        curr = curr->next;
    }
}

int main()
{
    push(10);
    push(20);
    push(30);
    push(40);
   
    cetak();
   
    return 0;
}

Queue
Queue dapat diartikan sebagai antrian. Queue merupakan sekumpulan data dimana penambahan elemennya hanya bisa dilakukan pada suatu ujung yang disebut sebagai sisi belakang (Rear) dan penghapusan/pengambilan elemennya dilakukan melewati ujung yang lain/pada sisi depan (Front). Prinsip yang digunakan pada queue adalah FIFO (First In First Out). Apa si FIFO itu? Elemen yang pertama kali dimasukkan ke dalam daftar adalah elemen yang pertama kali akan di hapus dari daftar/keluar dari daftar. Proses penghapusan elemen dalam queue disebut sebagai operasi dequeue. Dalam keseharian kita, kita menjumpai prinsip FIFO dalam hal antrian pada saat ingin membayar belanjaan di kasir. Siapa yang duluan datang, maka dia yang akan duluan dilayani dan dia yang akan duluan keluar dari supermarket/toko yang di datanginya dibandingkan dengan orang yang baru saja datang untuk mengantri membayar barangnya. Pada queue terdapat satu buah pintu masuk di ujung dan satu buah pintu keluar di ujung yang lain. Oleh sebab itu, queue membutuhkan variabel Head dan Tail.

Representasi diagram queue dapat kita lihat dari gambar di bawah ini :

Queue
Berikut ini adalah operasi yang dapat kita gunakan pada queue :

  1. push() : menambahkan suatu item/elemen pada bagian belakang queue
  2. pop() : menghapus suatu item/elemen pada bagian depan queue
  3. front() : mengungkapkan/mengembalikan item paling depan dari queue
Berikut adalah beberapa aplikasi yang menggunakan queue :
  1. Deques
  2. Priority Queues
  3. Breadth First Search


Berikut adalah contoh coding queue dalam bahasa C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6

int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;

int peek() {
   return intArray[front];
}

bool isEmpty() {
   return itemCount == 0;
}

bool isFull() {
   return itemCount == MAX;
}

int size() {
   return itemCount;


void insert(int data) {

   if(!isFull()) {

      if(rear == MAX-1) {
         rear = -1;           
      }     

      intArray[++rear] = data;
      itemCount++;
   }
}

int removeData() {
   int data = intArray[front++];

   if(front == MAX) {
      front = 0;
   }

   itemCount--;
   return data; 
}

int main() {
   /* insert 5 items */
   insert(3);
   insert(5);
   insert(9);
   insert(1);
   insert(12);

   // front : 0
   // rear  : 4
   // ------------------
   // index : 0 1 2 3 4
   // ------------------
   // queue : 3 5 9 1 12
   insert(15);

   // front : 0
   // rear  : 5
   // ---------------------
   // index : 0 1 2 3 4  5
   // ---------------------
   // queue : 3 5 9 1 12 15

   if(isFull()) {
      printf("Queue is full!\n"); 
   }

   // remove one item
   int num = removeData();

   printf("Element removed: %d\n",num);
   // front : 1
   // rear  : 5
   // -------------------
   // index : 1 2 3 4  5
   // -------------------
   // queue : 5 9 1 12 15

   // insert more items
   insert(16);

   // front : 1
   // rear  : -1
   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15

   // As queue is full, elements will not be inserted.
   insert(17);
   insert(18);

   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15
   printf("Element at front: %d\n",peek());

   printf("----------------------\n");
   printf("index : 5 4 3 2  1  0\n");
   printf("----------------------\n");
   printf("Queue:  ");

   while(!isEmpty()) {
      int n = removeData();         
      printf("%d ",n);
   } 
 
   return 0;
}




Referensi :

  1. https://id.wikipedia.org/wiki/Stack_(struktur_data)
  2. https://medium.com/easyread/memahami-konsep-stack-secara-sederhana-bd4409ec560c
  3. https://samuraibali.blogspot.com/2016/11/pengertian-stackproses-dan-contoh.html
  4. http://rizkialdadilly.blogspot.com/2016/01/pengertian-queue.html
  5. https://www.tutorialspoint.com/data_structures_algorithms/queue_program_in_c.htm
  6. https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/
  7. Binus Maya Stack&Queue Slides



Review Final

Nama : Indah Islamiana Sinurat NIM : 2301906003 Kelas : CB01 Dosen : Ferdinand Ariandy Luwinda (D4522) Henry Chong (D4460) AVL T...