Binary Search Tree

Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

To search a given key in Binary Search Tree, we first compare it with root, if the key is present at root, we return root. If key is greater than root’s key, we recur for right subtree of root node. Otherwise we recur for left subtree.

Illustration to search 6 in below tree:
1. Start from root.
2. Compare the inserting element with root, if less than root, then recurse for left, else recurse for right.
3. If element to search is found anywhere, return true, else return false.

Insertion of a key
A new key is always inserted at leaf. We start searching a key from root till we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.

Illustration to insert 2 in below tree:
1. Start from root.
2. Compare the inserting element with root, if less than root, then recurse for left, else recurse for right.
3. After reaching end,just insert that node at left(if less than current) else right.

Sumber:https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

Read More

GSLC

Hash Table & Tree

Hashing
Hashing adalah transformasi aritmatik sebuah string atau karakter
menjadi nilai yang merepresentasikan string aslinya.

Hashing digunakan sebagai metode untuk menyimpan data di dalam
sebuah array agar penyimpanan, penambahan, dan pencarian data
dapat dilakukan dengan benar.

Hash Table
Hash table adalah table (array) dimana kita menyimpan suatu string asli,
dimana index dari array adalah suatu kunci yang dienkripsi (hashed key
), namun nilainya adalah string yang asli.

Hash table biasanya terdiri dari berbagai macam urutan,
namun biasanya lebih sedikit dari berbagai kemungkinan string. Jadi,
beberapa string kemungkinan mempunyai hashed key yang sama.


Hash Function
Hashing adalah salah satu bagian penting dari data structure dimana
didesain oleh suatu fungsi yang dinamakan hash function yang
digunakan untuk memetakan suatu nilai dengan suatu ciri yang spesifik
untuk akses elemen yang lebih cepat.
Misalkan untuk fungsi H(x) akan memetakan nilai x yang disimpan di
index x%10, maka data {11,13,15,17,19 } akan disimpan secara
berturut-turut akan disimpan di index { 1,3,5,7,9 } di dalam array.

Beberapa metode untuk membuat Hash Function :
- Mid – Square
- Division
- Folding
- Digit Extraction
- Rotating Hash

-Mid-Square
Function: h(k) = s
k = key
s = hash key yang diperoleh dari nilai tengah kuadrat k
 kuadratkan string/identifier (k), lalu kita ambil angka tengah dari
kuadrat string/identifier untuk dijadikan hash key (s)
-Division
Function: h(z) = z mod M
z = key
M = angka yang digunakan untuk membagi key
 ketika ingin memunculkan index dan meletakkan key di index hasil
function division
-Folding
 bagi key menjadi beberapa bagian
 jumlahkan bagian individualnya
-Digit Extraction
 beberapa bagian digit dari key akan dijadikan hash address
-Rotating Hash

Read More

Data Struct 2

                                                                    Linked List 
Kelvin Jonatan
2301923110

1. Circular Single Linked List

Circular Single Linked List adalah jenis struktur data yang terdiri dari node yang dibuat dengan menggunakan struktur referensialnya sendiri,masing-masing node berisi dua bagian yaitu data dan referensi ke daftar simpul berikutnya.

Fungsi insert () menyisipkan data ke awal daftar yang tertaut.menciptakan newnode dan memasukkan angka di bidang data dari newnode.jika head nya adalah NULL ,maka newnode menunjuk ke dirinya sendiri jika tidak,simpulan akhirnya dalam daftar tertaut melingkar menunjuk ke newnode.kemudian head menunjuk ke awal daftar yaitu ke newnode. 

2. Doubly Linked List 

Doubly Linked List adalah struktur data yang terdiri dari sekumpulan catatan yang terhubung secara berurutan yang disebut node.setiap node berisi tiga bidang:dua bidang tautan(referensi ke simpul sebelumnya dan ke simpul berikutnya dalam urutan simpul)dan satu bidang data tautan awal dan akhir dari node sebelumnya dan berikutnya,biasanya node sentinel atau null,untuk memfasilitasi traversal dari daftar,Jika hanya ada satu simpul sentinel,maka akan terhubung secara melingkar melalui simpul sentinel.  

3. Circular Doubly Linked List

Circular Doubly Linked List adalah jenis struktur data yang lebih kompleks di mana sebuah node berisi pointer ke node sebelumnya serta node berikutnya.Daftar tertaut ganda melingkar tidak mengandung NULL di sembarang simpul.Simpul terakhir dari daftar berisi alamat dari simpul pertama dari daftar node juga berisi alamat dari node terakhir di pointer yang sebelumnya.

Sumber :-https://www.tutorialspoint.com/cplusplus-program-to-implement-circular-singly-linked-list

               -https://en.wikipedia.org/wiki/Doubly_linked_list

               -https://www.javatpoint.com/circular-doubly-linked-list

Read More