Hashing dan Binary Tree

Hashing

Hashing adalah bentuk data struktur yang menggunakan Hash Function yang digunakan untuk memetakan sebuah value dengan kunci tertentu supaya dapat di akses lebih cepat.

Dalam arti Hashing adalah cara untuk menrubah nilai kunci menjadi range index di array. Hashing juga merupakan cara untuk melakukan program search lebih efektif dibandingkan binary search dan linear search

Hashing bisa melakukan update dan pengambilan data tanpa menggunakan ukuran data. Secara umum hashing digunakan untuk enkripsi dan dekripsi data.

Hash Function

Hash function adalah proses yang merubah kunci  dan memetakannya menjadi panjang tertentu menjadi hash value, maka menjadi hash key. 

Hash value adalah versi kecil pada string karakter awal. Dengan digital signature dan hash value dikirim ke receiver. Receiver lalu menggunakan hash function yang sama dan dibanding dengan pesan yant tadi. Jika hash valuesnya sama maka akan menampilkan error.

Hash Function terdiri dari

1.      Mid Square

Dengan mengkuadratkan value seed awal menjadi kunci unik, lalu digit yang ada ditengah nilai yang sudah dikuadratkan diambil dan digunakan sebagai kunci baru

Contoh nilai seed pertamanya adalah 4765

4765 kuadrat= 22705225

Ambil bagian tengahnya 22 7052 25 dan dikuadratkan lagi

7052 kuadrat= 49730704

Ambil bagian tengahnya 49 7307 04

Ulangi sampai puas.

Contoh Kodenya dari geeksforgeeks

// C++ program to illustrate the

// mid-square hashing technique

#include <ctime>

#include <iostream>

  

using namespace std;

  

// Returns a seed value based on current system time.

long long int newTime()

{

  

    // Acquiring number of seconds

    // passed from Jan 1, 1970.

    time_t t = time(NULL);

  

    // Converting the time to year, month,

    // day, hour, minute, and second.

    struct tm* tm = localtime(&t);

    long long int x;

  

    // Applying a certain logic to get

    // required number of digits. It may vary.

    x = (tm->tm_hour) * 10000000 + (tm->tm_min) * 100000

        + (tm->tm_sec) * 1000 + (tm->tm_mday) * 10 + (tm->tm_year);

  

    // Return the calculated number.

    return x;

}

  

// Returns a random 8-digit key.

long int getKey()

{

  

    // Taking the key from system time. 

    // returns a  8-digit seed value.

    static long long int key = newTime();

  

    // Squaring the key.

    key = key * key;

  

    // Extracting required number of digits ( here, 8 ).

    if (key < 1000000000000000) {

        key = key / 10000;

        key = key % 100000000;

    }

    else {

        key = key / 10000;

        key = key % 100000000;

    }

  

    // Returning the key value.

    return key;

}

  

// Driver Code

int main()

{

    // get the first key

    std::cout << getKey() << endl;

  

    // get the second key

    std::cout << getKey() << endl;

    return 0;

}

2.      Division

Cara division adalah cara hashing termudah dengan rumus h(k) = k mod n atau menggunakan hasil pembagian

Contoh nilai seed awalnya adalah 3562 dan n=10

3562 mod 10= 2

Maka Hash valuenya =2

3.      Folding

Dengan menggunakan partitisi string/identifier menjadi beberapa bagian dan di jumlahkan menjadi satu hash key

Contoh ada key 678 dan 12345

678 menjadi 67 dan 8 dan 12345 menjadi 12 34 5

67+8=75, 12+34+5= 51

Maka keynya dalah 75 dan 51

4.      Digit Extraxtion

DE method mengambil beberapa nomor ke @ pada sebuah value

Contohnya 34593 ada 5 digit

Jadi kalau kita ambil digit ke 1, 3, dan 5, maka kita hanya punya hash value 353

5.      Rotating Hash

Cara rotation merupakan gabungan dari 2 metode diatas dan ditukar-menukar. Contohnya kita memakai cara digit extraction dan folding, kita ada nilai 489012 dengan n=10.

DE=489012 ambil (digit1,2,4,6)=4802

Folding=48 02->48+2=50, maka hash valuenya 50

Hash Table

Hash tables atau hash map adalah data struktur ynag menyetor kunci sama valuenya. Ini digunakan untuk memudahkan untuk mencari kunci yang akan digunakan nanti.

Hash Map menggunakan hash function untuk memuat index ke dalam slot pada array yang menyimpan value yang dicari. 

Pada gambar diatas menunjukan hash table dengan ukuran n=10. Tiap kotak di tablenya adalah Slot. Jadi nomor diatasnya (0-9) merupakan Slotsnya dan tiap slot tidak ada isinya.

Contoh Kasus:

Misalkan kita ada integer {30, 56, 77, 39, 4} dan ukuran n=10, kita menggunakan rumus iM%n (iM=Merupakan nilai integer di array ke berapa)  untuk menentukan hash value.

Dengan menggunakan kalkulator programming

Data Item	Value % N	Hash Value
30	30%10=0	0
56	56%10=6	6
77	77%10=7	7
39	39%10=9	9
4	4%10=4	4

Setelah menentukan hash value kita masukan ke dalam hash tablenya

0	1	2	3	4	5	6	7	8	9
30			4			56	77		39

Setelah dilihat 5 dari 10 slots yang ada dipakai, dan menggunakan simbol λ sebagai load factor. Untuk  tabel yang ini maka digunakan λ =5/10. 

Trees and Binary Tree

Sebuah tree adalah data struktur non-linear yang mempunyai relasi hierarki pada data objek.

Contoh Tree

Node 1=root atau awal

Garis yang menghubungi ken node lainnya adalah edge

Node akhir yang gak hubungi lagi (8, 9, 10, 11, 13, 14) adalah leaf

Height atau depth adalah degree maximum node pada suatu tree

Tipe Binary Tree

·        Perfect Binary Tree= Mempunyai depth yang sama di tiap level

·        Complete Binary Tree= Setiap level kecuali pada akhir, terisi node dan sejauh kiri mungkin

·        Skewed Binary Tree= Binary Tree di mana setiap node mempunyai 1 anak

·        Balanced Binary Tree= Binary Tree yang tidak ada leaf yang tidak jauh dari root dibanding leaf yang lain

Isi Binary Tree

^·             Max Node=2^k

^·             Maximum Node pada tinggi adalah 2^h+1 – 1

·        Minimum tinggi pada binary tree pada n nodes adalah 2log(n).

·        Maximum height pada binary tree adalah n nodes adalah n - 1.

Contoh Kode 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();

}

Expression Tree

Expression Tree menggunakan notasi aritmetika untuk menjelaskan suatu equation

Contoh:

Prefix : *+ab/-cde

Postfix : ab+cd-e/*

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

Untuk menggunakan ini kita butuh Binary Tree dan menggunakan Infix, Prefix, Postfix

struct tnode {

               char chr;

               struct tnode *left;

               struct tnode *right;
};

Infix, Prefix, Postfix

Dalam Tree kita ada 3 notasi operasi, yaitu Infix, Prefix, Postfix. Ketiga notasi ini terbentuk dari operand dan operator.

Contohnya

A+B*C
2 + 5 * 3
Keterangan: A ,B ,C ,2 ,3 ,5 adalah Operand.
+,*  adalah Operator.

·        Prefix: Notasi terbentuk atas operator dan operand, dimana operator didepan operand.

Contoh: A+B*C=infix, maka +A*BC adalah prefix

Dalam prefix kita hanya memundurkan operator pada sebuah string menurut hierarki. Kita menggeser * dari B*C menjadi *BC, dan ini berlaku pada + di A juga

Kode Prefix:

void prefix(struct tnode *curr) {

               printf( “%c “, curr->chr );

               if ( curr->left  != 0 ) prefix(curr->left);

               if ( curr->right != 0 ) prefix(curr->right);
}

·        Infix: Notasi yang membentuk atas operator dengan operator, dimana operator ada di antara operand

Contoh: A+B*C -> (A+B)*C -> A-(B+C)*D^E

Contoh Kode Infix

                              if ( is_operator(curr->chr) ) putchar( '(' );

                              if ( curr->left != 0 ) infix(curr->left);

                              printf( "%c", curr->chr );

                              if ( curr->right != 0 ) infix(curr->right);

                              if ( is_operator(curr->chr) ) putchar( ')' );

               }

·        Postfix: Notasi terdiri dari operator dan operand, dimana operator berada dibelakan operand

Contoh: A+B*C-> ABC*+, hampir sama seperti Prefix tetapi urutan operatornya terbalik dan berada di kanan operand

Contoh kode konversi dari prefix ke postfix menuruts geeksforgeeks.org

// CPP Program to convert prefix to postfix

#include <iostream>

#include <stack>

using namespace std;

  

// funtion to check if character is operator or not

bool isOperator(char x) {

  switch (x) {

  case '+':

  case '-':

  case '/':

  case '*':

    return true;

  }

  return false;

}

  

// Convert prefix to Postfix expression

string preToPost(string pre_exp) {

  

  stack<string> s;

  

  // length of expression

  int length = pre_exp.size();

  

  // reading from right to left

  for (int i = length - 1; i >= 0; i--) {

  

    // check if symbol is operator

    if (isOperator(pre_exp[i])) {

  

      // pop two operands from stack

      string op1 = s.top(); s.pop();

      string op2 = s.top(); s.pop();

  

      // concat the operands and operator

      string temp = op1 + op2 + pre_exp[i];

  

      // Push string temp back to stack

      s.push(temp);

    }

  

    // if symbol is an operand

    else {

  

      // push the operand to the stack

      s.push(string(1, pre_exp[i]));

    }

  }

  

  // stack contains only the Postfix expression

  return s.top();

}

  

// Driver Code

int main() {

  string pre_exp = "*-A/BC-/AKL";

  cout << "Postfix : " << preToPost(pre_exp);

  return 0;

}

www.Sejarah Blogspot.co.idwww.google.com