Hashing-003

Hashing dan Hash Table

Hashing

Hashing merupakan suatu teknik untuk menyimpan dan mengambil kunci dengan cepat. Dengan Hashing, string diubah menjadi suatu value yang lebih pendek atau kunci untuk menggantikan stirng. Hashing juga dikenal sebagai distributor kunci array Hash Table yang menggunakan function Hash Function.
https://www.tutorialspoint.com/data_structures_
algorithms/images/hash_function.jpg


Hash Table

Hash Table merupakan table / array tempat menyimpan string. Index dari Hash Table merupakan kunci dari Hashing yang sudah mengandung string.

Hash Function

Terdapat banyak cara untuk mengubah string ke kunci. Berikut meupakan cara penting untuk membuat Hash Function.
- Mid - square
- Division
- Folding
- Digit Extraction
- Rotating hash

Collision

Collision merupakan suatu peristiwa di mana kunci baru, menempati tempat yang sudah terisi dengan kunci sebelumnya. Terdapat cara untuk mengatasi Collision, yaitu:
-  Linear probing
- Chaining



Trees dan Binary Tree


Konsep Tree

Di dalam Tree, node teratas diberi nama root, garis yang menghubungkan praent dan child disebut edge, node yang tidak memiliki anak disebut leaf, node - node yang memiliki parent yang sama disebut sibling.

Konsep Binary Tree

Di dalam Binary Tree, setiap node hanya memiliki maksimal 2 anak, di mana anak - anak tersebut disebut left child dan right child. Node yang tidak memiliki anak disebut leaf.
https://www.geeksforgeeks.org/wp-content/
uploads/binary-tree-to-DLL.png

Jenis - Jenis Binary Tree

- Perfect Binary Tree


- Complete Binary Tree

- Skewed Binary Tree

- Balanced Binary Tree

Threaded Binary Tree

Threaded Binary Tree mirip dengan Binary Tree hanya perbedaan nya Threaded Binary Tree mentimpan pointer NULL.


References:

Komentar

Posting Komentar

Postingan populer dari blog ini

Summary

Gambar
Linked List Linked List merupakan data struktur linear, di mana memeory  penyimpanan untuk tiap data tidak berdekatan posisinya.Linked List terdiri dari node - node yang berisi data - data. Di dalam Linked List dapat dilakukan insertion dan deletion di posisi manapun. Linked List sudah sangat membantu menyelesaikan masalah yang pernah terjadi, yaitu kebutuhan penyimpanan data yang tidak dapat diprediksi. Linked List terdapat 2 tipe, yaitu 1. Single Linked List Di dalam Single Linked List hanya dapat satu arah, yaitu dari kiri ke kanan, dengan menggunakan pointer yang umunya diberi nama "next", dan terdapat pointer "head" sebagai penunjuk data pada bagian depan. https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2013/03/Linkedlist.png 2. Double Linked List Di dalam Double Linked List terdapat dua arah, yaitu dari kiri ke kanan dan arah sebaliknya, dengan menggunakan dua pointer yang umumnya diberi nama "next" untuk arah
Baca selengkapnya

AVL-BTREE

Gambar
AVL Tree and B-Tree AVL Tree AVL Tree  merupakan bagian dari Binary Tree Search  ( BST ), di mana AVL Tree memiliki depth untuk subtree sebelah kiri dan kanan memiliki perbedaan depth yaitu lebih kurang sama dengan satu.  Sehingga  AVL Tree  memiliki depth yang lebih stabil dibandingkan  Binary Search Tree. https://media.geeksforgeeks.org/wp-content/cdn-uploads/AVL-Tree1.jpg Untuk mempertahankan keseimbangannya AVL Tree memiliki method untuk menyeimbangkan tree, method ini disebut rotation . Method rotation ini memiliki 4 macam, yaitu 1. Right Rotation                    5                                                          2                   /                                                         /     \                 2                ------------------>              1        5                /                     Right Rotate              1 2. Left Rotation                     5                                             
Baca selengkapnya