Hashing dan Hash Tables, Trees, dan Binary Trees (Week 4)

-
Pada pertemuan sebelumnya, saya telah mempelajari Linked List, yang dimana merupakan kumpulan data dinamis yang saling terhubung antar satu sama lain. Terdapat single linked list, double linked list, circular single linked list, dan circular double linked list. Untuk materi kali ini, linked list juga akan terpakai dalam hashing dan binary trees.

HASHING DAN HASH TABLE

Hashing merupakan teknik mengubah setiap record menjadi angka (hash). Kumpulan dari karakter dalam sebuah record diubah dalam bentuk yang lebih pendek (kata kunci) yang merepresentasikan kumpulan karakter itu sendiri. Keunggulan hashing ini adalah waktu aksesnya yang cukup cepat sehingga waktu yang dibutuhkan dalam penambahan, penghapusan, dan pencarian lebih singkat. Jadi, hashing ini mendistribusikan kunci-kunci dalam sebuah array yang disebut hash table, dengan menggunakan fungsi-fungsi yang disebut hash function.

Contoh hash table:

Misalkan kita ingin menyimpan nama mahasiswa berupa: Doni, Andi, Budi, Fanny, Yadi. Maka, kita dapat mengubah karakter pertama dari setiap string menjadi angka, contohnya a itu 0, b itu 1, c itu 2, sehingga:



HASH FUNCTION

Beberapa cara untuk mengubah string menjadi key:

Mid-square

Mengkuadratkan string/identifier, kemudian mengambil beberapa angka dari hasil kuadrat (dari tengah) untuk dijadikan hash key.
Contoh:

Division

Membagi string/identifier dengan menggunakan operator modulus. Biasanya modulo nya berupa ukuran dari table/array atau menggunakan bilangan prima terdekat diatas banyaknya data.

Contoh:
Diberikan table (array) berukuran 85. Maka kita bisa gunakan 89 sebagai modulo agar setiap hash key itu unik.
Data: ABCD, QWER, ZXCV, ASDF
Gunakan ASCII
ABCD: ((64+1) + (64+2) + (64+3) + (64+4)) % 89 = 88
QWER: ((64+17) + (64+23) + (64+5) + (64+18)) = 52
ZXCV: ((64+26) + (64+24) + (64+3) + (64+22)) = 64
ASDF: ((64+1) + (64+19) + (64+4) + (64+6)) = 19

Folding

Membagi string/identifier menjadi beberapa bagian, kemudian jumlahkan bagian-bagian tersebut untuk mendapatkan hash key.


Digit Extraction

Mengambil bagian dari string/identifier yang diberikan.
Contoh: x = 54321, jika kita mengambil angka ke 2 dan 4, kita akan mendapatkan hash key 24.

Rotating Hash

Biasanya dikombinasikan dengan hash function yang lain (misalnya mid-square atau division). Setelah itu membalikkan urutan angka dari belakang ke depan.

Contoh : Hash key: 24689, Hasil rotasi: 98642


COLLISION

Collision merupakan bentrokan/tabrakan antar hash key, dimana terdapat record yang mempunyai hash key yang sama.

Cara mengatasi collision:

Linear Probing >> Mencari tempat kosong di tempat berikutnya dan letakkan string disana.
Contoh:
Data: Andi, Anton, Caca, Daniel, Ester, Hani, Conan


Cara ini dapat meningkatkan kompleksitas ketika melakukan pencarian.

Chaining >> Meletakkan string dalam slot yang sama menggunakan linked list.



TREES DAN BINARY TREES

Tree merupakan struktur data non linear yang menjelaskan hubugan antar data. 

Tree merupakan kumpulan satu node atau lebih.


- Node paling atas disebut "root"
- Node yang tidak memiliki  "child" disebut "leaf"
- Node yang memiliki "parent" yang sama disebut "sibling"
- Jika terdapat garis yang menghubungkan node a dan b, maka a merupakan "ancestor" dari b, dan b merupakan "descendant" dari a.

Binary Tree merupakan tree yang dimana setiap node memiliki paling banyak dua "child".


Keterangan (Parent dan Child):
B merupakan "parent" dari D dan E.
D dan E merupakan "child" dari B.


CIRI-CIRI BINARY TREE

Jumlah maksimum node pada setiap level k adalah 2^k.


Jumlah maksimum node dalam sebuah binary tree yang memiliki tinggi h adalah 2^(h+1) - 1
Contoh: h = 4, jumlah maks = 2^4 - 1 = 15.

Tinggi minimum binary tree yang memiliki n nodes adalah 2 log(n).
Tinggi maksimum binary tree yang memiliki n nodes adalah n-1.


PENGAPLIKASIAN BINARY TREE

Implementasi Menggunakan Array


Index 0 adalah node "root".
Index "child" kiri adalah 2p+1, p adalah index "parent"
Index "child" kanan adalah 2p+2, p adalah index "parent"
Index "parent" adalah (p-1)/2

Implementasi Menggunakan Linked List
struct node {
  int data;
  struct node *left;
  struct node *right;
  struct node *parent;
};
struct node *root = NULL;

KONSEP EXPRESSION TREE

Prefix: *+/ab-cde
Postfix: ab+cd-e/*
Infix: (a+b) * ((c-d)/e)

Membuat Expression Tree dari Prefix


Prefix Traversal


Postfix Traversal


Infix Traversal


THREADED BINARY TREE



Binary Tree with One Way Threading


Binary Tree with Two Way Threading


Komentar

Posting Komentar

Postingan populer dari blog ini

AVL Tree

-
Gambar
AVL Tree merupakan pengembangan dari Binary Search Tree. AVL Tree memberikan kompleksitas yang lebih rendah, khususnya dalam worst case, karena AVL Tree menyeimbangkan root-root dari Binary Search Tree. Dalam melakukan insertion, deletion dan searching, kompleksitasnya sangat dipengaruhi oleh tinggi dari pohon tersebut. Apabila Binary Search Tree memiliki cabang yang cenderung timpang, misal kebanyakan data berada di sisi kiri sementara sisi kanan kosong, itu berpengaruh terhadap kompleksitasnya sendiri. Dan AVL Tree menyelesaikan masalah ini dengan menyeimbangkan cabang-cabangnya sehingga tidak terlalu timpang. Ini yang disebut dengan Balanced Binary Search Tree dan AVL Tree ini merupakan salah satu dari bentuk Balanced Binary Search Tree. Tinggi sebuah node: - Tinggi dari sebuah subtree kosong adalah 0 - Tinggi leaf adalah 1 Balance Factor: Perbedaan tinggi antara subtree kiri dan subtree kanan dari sebuah node *Balance factor sebuah node hanya boleh paling besar 1
Baca selengkapnya

Review

-
Gambar
Nama: Ariantoly NIM: 2301877230 Kelas: CB-01 Nama Dosen: - Henry Chong (D4460) - Ferdinand Ariandy Luwinda (D4522) Linked List Pada pertemuan sebelumnya, saya telah mempelajari Single Linked List. Linked List merupakan struktur data yang memanfaatkan dynamic memory allocation dalam membuat sebuah kumpulan data, dan data-data tersebut dihubungkan oleh pointer. Data-data pada Linked List dapat kita manipulasi dengan insertion (push) dan deletion (pop). Setiap Linked List harus diawali oleh head dan diakhiri oleh tail. Contoh : Single Linked List Single Linked List merupakan Linked List yang hanya terhubung ke data berikutnya. Codingan dasar dalam membuat Linked List: struct node { int nilaiData;     struct node *next; }; struct node *head = NULL; struct node *tail = NULL; Circular Single Linked List Circular Single Linked List memiliki bentuk yang sedikit berbeda dengan Single Linked List. Tail->next pada Single Linked List men
Baca selengkapnya