Hashing & Binary Tree

Hashing & Hash Tables

Hashing

Hashing adalah teeknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Tujuan hashing adalah sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan datam dan penghapusan data dapat dilakukan dengan cepat.

Hash Table

Hash table adalah salah satu struktur data yang digunakan dalam penyimpanan data sementara. Hash table menggunakan memori penyimpanan utama berbentyj array dengan tambahan algoritma untuk mempercepat pemrosesan data.

Hash Function

Hash Function adalah suatu fungsi sederhana untuk mendaoatkan nilai hash dari nilai kunci(key value) suatu data.

Ada beberapa hal dalam membuat hash function antara lain :

·        Ukuran array/ table size (m)

·        Key value/ nilai yang di dapat dari data (k)

·        Hash value/ hash index/index yang dituju (h)

Beberapa metode pentuk untuk membangun hash functions antara lain:

• Mid – square
• Division (most common)
• Folding
• Digit Extraction
• Rotating Hash

Mid – square

Mid-Square hashing adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai benih yang cukup besar diambil. Namun, itu memiliki batasan. Saat bijinya dikuadratkan, jika angka 6-digit diambil, maka persegi akan memiliki 12-digit. Ini melebihi kisaran tipe data int. Jadi, overflow harus diurus. Jika terjadi overflow, gunakan tipe data int panjang atau gunakan string sebagai perkalian jika luapan masih terjadi. Kemungkinan tabrakan di tengah-tengah hashing rendah, tidak usang. Jadi, dalam peluang, jika tabrakan terjadi, itu ditangani menggunakan beberapa peta hash.

Contoh:

Nilai	Di kuadratkan	Nilai di ekstraksi
4765	22705225	7052
3725	13875625	8756

Algoritma dalam mid – square

• Pilih nilai seed. Ini adalah langkah penting karena untuk nilai seed yang sama, urutan nomor acak yang sama dihasilkan.
• Ambil kuadrat dari nilai seed dan perbarui seed dengan jumlah digit tertentu yang terjadi di square. Catatan: Semakin besar jumlah digit, semakin besar keacakannya.
• Kembalikan kuncinya.

Division

Jumlah lokasi memori tersedia dihitung , kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa(nilai hashnya).

Secara umum rumus division sebagai berikut :

h(z) = z mod M

Keterangan:

z          = key/ suatu lokasi  memori yang beralamat h(z)

M        = jumlah lokasi memori yang tersedia pada array

Contoh:

Ukuran table = 97

COBB

Abjad	Nilai ASCII
C	67
O	79
B	66
B	66
total	278

H(z) = 278 mod 97 = 84

HIKE

Abjad	Nilai ASCII
H	72
I	73
K	75
E	69
total	289

H(z) = 289 mod 97 = 95

ABCD

Abjad	Nilai ASCII
A	65
B	66
C	67
D	68
total	266

H(z) = 278 mod 97 = 72

Folding

Metode lipat berfungsi dalam 2 langkah :

• Bagi nilai kunci menjadi beberapa bagian dimana setiap bagian memiliki jumlah digit yang sama kecuali bagian terakhir yang mungkin memiliki angka lebih sedikit daripada bagian lainnya.
• Tambahan bagi individu. Yaitu memperoleh jumlah part 1 + part  + .. + part n. Nilai hash yang dihasilkan dengan mengabaikan carry terakhir, jika ada.

  Contoh:

Key = 6632

Parts = 66 dan 32

Jumlah = 98

Hash value = 98

Digit Extraction

Mendapatkan hash key dengan cara mengambil digit – digit tertentu dari sebuah string

untuk dijadikan hash keynya.

Contoh: terdapat string yaitu 14568, jika kita mengambil digit 1, digit 3, dan digit 5 maka

hash keynya adalah 158.

Rotating Hash

Mendapatkan hash key maka di lakukan rotasi untuk menggeser digit sehingga

menemukan alamat hash key baru.

Contoh :

Hash key = 3456

Hasil rotasi = 6543

Collision

Ada 2 cara untuk menangani collision :

·        Linear Probing

Mencari slot kosong berikutnya dan letakkan string disana.

Code :

void linear_probing(item, h[]) {

hash_key = hash(item);

i = has_key;

while ( strlen(h[i] != 0 ) {

         if ( strcmp(h[i], item) == 0 ) {

              // DUPLICATE ENTRY
         }

         i = (i + 1) % TABLE_SIZE;

         if ( i == hash_key ) {

              // TABLE IS FULL
         }
}

h[i] = item;
}

·        Chaining

Masukkan string ke dalam slot sebagai chained list(linked list).

Code:

void chaining(item, h[]) {

     hash_key = hash(item);

     trail = NULL, lead = h[hash_key];

     while ( lead ) {

     if ( strcmp(lead->item, item) == 0 ) { // DUPLICATE ENTRY }

     trail = lead; lead = lead->next;
     }

     p = malloc new node;

     p->item = item;

     p->next = NULL;

     if ( trail == 0 ) h[hash_key] = p; else trail->next = p;

}

Trees  & Binary Tree

Tree adalah salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree).

Istilah – istilah umum dalam tree :

·        Prodecessor : node yang berada diatas node tertentu.

·        Successor : node yang berada di bawah node tertentu.

·        Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

·        Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.

·        Parent : predecssor satu level di atas suatu node.

·        Child : successor satu level di bawah suatu node.

·        Sibling : node-node yang memiliki parent yang sama dengan suatu node.

·        Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

·        Size : banyaknya node dalam suatu tree.

·        Height : banyaknya tingkatan/level dalam suatu tree.

·        Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

·        Leaf : node-node dalam tree yang tak memiliki seccessor.

·        Degree : banyaknya child yang dimiliki suatu node.

Jenis – jenis binary tree:

·        Perfect binary tree

Adalah binary tree yang setiap level berada pada kedalaman/ depth yang sama.

·        Complete binary tree

Adalah binary tree yang setiap levelnya kecuali yang terakhir semua telah terisi penuh dan setiap nodesnya paling panjang ke kiri.

·        Skewed binary tree

Adalah binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

·        Balanced binary tree

Adalah binary tree yang dimana yang setiap leafnya sama jauhnya dari root

Representation of Binary Tree

• Implementation using array

        Index on array represents node number

        Index 0 is Root node

        Index Left Child is 2p + 1, where p is parent index

        Index Right Child is 2p + 2

        Index Parent is (p-1)/2

• Implementation using linked list

         struct node {

int data;

struct node *left;

struct node *right;

struct node *parent;

          };

          struct node *root = NULL;

structure binary tree

struct tnode {

char chr;

struct tnode *left;

struct tnode *right;

};

Insert di binary tree mengunakan C

// C++ program to insert element in binary tree

#include <iostream>

#include <queue>

using namespace std;

  

/* A binary tree node has key, pointer to left child

and a pointer to right child */

struct Node {

    int key;

    struct Node* left, *right;

};

  

/* function to create a new node of tree and r

   eturns pointer */

struct Node* newNode(int key)

{

    struct Node* temp = new Node;

    temp->key = key;

    temp->left = temp->right = NULL;

    return temp;

};

  

/* Inorder traversal of a binary tree*/

void inorder(struct Node* temp)

{

    if (!temp)

        return;

  

    inorder(temp->left);

    cout << temp->key << " ";

    inorder(temp->right);

}

  

/*function to insert element in binary tree */

void insert(struct Node* temp, int key)

{

    queue<struct Node*> q;

    q.push(temp);

  

    // Do level order traversal until we find

    // an empty place. 

    while (!q.empty()) {

        struct Node* temp = q.front();

        q.pop();

  

        if (!temp->left) {

            temp->left = newNode(key);

            break;

        } else

            q.push(temp->left);

  

        if (!temp->right) {

            temp->right = newNode(key);

            break;

        } else

            q.push(temp->right);

    }

}

  

// Driver code

int main()

{

    struct Node* root = newNode(10);

    root->left = newNode(11);

    root->left->left = newNode(7);

    root->right = newNode(9);

    root->right->left = newNode(15);

    root->right->right = newNode(8);

  

    cout << "Inorder traversal before insertion:";

    inorder(root);

  

    int key = 12;

    insert(root, key);

  

    cout << endl;

    cout << "Inorder traversal after insertion:";

    inorder(root);

  

    return 0;

}

Deletion in a Binary Tree

Given a binary tree, delete a node from it by making sure that tree shrinks from the bottom (i.e. the deleted node is replaced by bottom most and rightmost node). This different from BST deletion. Here we do not have any order among elements, so we replace with last element.

Contoh:

Delete 10 in below tree

       10

     /    \        

    20     30

Output :   

       30

     /            

    20    

Delete 20 in below tree

       10

     /    \        

    20     30

            \

            40

Output :   

       10

     /   \            

    40    30  

Algorithm

·        Starting at root, find the deepest and rightmost node in binary tree and node which we want to delete.

·        Replace the deepest rightmost node’s data with node to be deleted.

·        Then delete the deepest rightmost node.

Source code in C/C++

// C++ program to delete element in binary tree

#include <bits/stdc++.h>

using namespace std;

  

/* A binary tree node has key, pointer to left 

child and a pointer to right child */

struct Node {

    int key;

    struct Node *left, *right;

};

  

/* function to create a new node of tree and 

return pointer */

struct Node* newNode(int key)

{

    struct Node* temp = new Node;

    temp->key = key;

    temp->left = temp->right = NULL;

    return temp;

};

  

/* Inorder traversal of a binary tree*/

void inorder(struct Node* temp)

{

    if (!temp)

        return;

    inorder(temp->left);

    cout << temp->key << " ";

    inorder(temp->right);

}

  

/* function to delete the given deepest node 

(d_node) in binary tree */

void deletDeepest(struct Node* root,

                  struct Node* d_node)

{

    queue<struct Node*> q;

    q.push(root);

  

    // Do level order traversal until last node

    struct Node* temp;

    while (!q.empty()) {

        temp = q.front();

        q.pop();

        if (temp == d_node) {

            temp = NULL;

            delete (d_node);

            return;

        }

        if (temp->right) {

            if (temp->right == d_node) {

                temp->right = NULL;

                delete (d_node);

                return;

            }

            else

                q.push(temp->right);

        }

  

        if (temp->left) {

            if (temp->left == d_node) {

                temp->left = NULL;

                delete (d_node);

                return;

            }

            else

                q.push(temp->left);

        }

    }

}

  

/* function to delete element in binary tree */

Node* deletion(struct Node* root, int key)

{

    if (root == NULL)

        return NULL;

  

    if (root->left == NULL && root->right == NULL) {

        if (root->key == key)

            return NULL;

        else

            return root;

    }

  

    queue<struct Node*> q;

    q.push(root);

  

    struct Node* temp;

    struct Node* key_node = NULL;

  

    // Do level order traversal to find deepest

    // node(temp) and node to be deleted (key_node)

    while (!q.empty()) {

        temp = q.front();

        q.pop();

  

        if (temp->key == key)

            key_node = temp;

  

        if (temp->left)

            q.push(temp->left);

  

        if (temp->right)

            q.push(temp->right);

    }

  

    if (key_node != NULL) {

        int x = temp->key;

        deletDeepest(root, temp);

        key_node->key = x;

    }

    return root;

}

  

// Driver code

int main()

{

    struct Node* root = newNode(10);

    root->left = newNode(11);

    root->left->left = newNode(7);

    root->left->right = newNode(12);

    root->right = newNode(9);

    root->right->left = newNode(15);

    root->right->right = newNode(8);

  

    cout << "Inorder traversal before deletion : ";

    inorder(root);

  

    int key = 11;

    root = deletion(root, key);

  

    cout << endl;

    cout << "Inorder traversal after deletion : ";

    inorder(root);

  

    return 0;

}

Sumber : 
materi binus
https://www.geeksforgeeks.org/mid-square-hashing/
https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/
https://www.geeksforgeeks.org/deletion-binary-tree/
http://new-funday.blogspot.com/2012/12/struktur-data-tree-dan-penjelasaanya.html
https://zoneblog123.blogspot.com/2018/04/pengertian-tree-binary-tree-beserta.html