Heap and Tries

Heap adalah bentuk pohon biner yang mempertahankan properti unik.satu tumpukan populer adalah min-heap,yang mengatur data sedemikian rupa sehingga sangat mudah untuk mengakes yang terkecil dari elemen heap.
Heap-pohon biner khusus untuk menyimpan data yang diurutkan,dapat membuat lebih lambat untuk pencarian,tetapi lebih cepat untuk pemasangan,struktur heap data dapat digunakan secara efisien untuk menemukan elemen terkecil atau elemen terbesar dalam array.

Tries:struktur pohon yang digunakan untuk mewakili kata-kata,yang dimana tidak diperlukan simpul dalam menjalankannya,sebagai kunci dari tries atau nilai yang sangat dikaitkan dengan tepi,dan node dan hanya ada untuk pelengkap
A simple Node class can be used to represent nodes in the trie:

class Node:
   def __init__(self) -> None:
       # Note that using dictionary for children (as in this implementation)
       # would not allow lexicographic sorting mentioned in the next section
       # (Sorting), because an ordinary dictionary would not preserve the
       # order of the keys
       self.children: Dict[str, Node] = {}  # mapping from character ==> Node
       self.value: Any = None

Sumber :https://ada110.github.io/dist/course_notes/Heaps_and_Tries.pdf
             https://www.codingblocks.net/podcast/data-structures-heaps-and-tries/

Read More

AVL TREE

AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).

Insert suatu node pada AVL sama halnya pada insert node pada binary search tree, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam.

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

anggap T adalah node yang harus diseimbangkan kembali

- Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
- Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
- Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
- Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
- Kasus 1 dan 2 dengan single rotation
- Kasus 3 dan 4 dengan double rotation

 

Single rotation

single rotation dilakukan bila kondisi AVL tree akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut.t1,t2,t3 adalah subtree yang urutannya height-nya harus sama (>=0)

Double rotation

Double rotation dijalankan bila kondisi AVL tree akan ditambahkan node baru dan posisi node baru.t1,t2,t3,dan t4 adalah subtree yang urutannya harus seperti demikian.tinggi subtree T1 harus sama dengan T4(>=0),tinggi subtree T2 harus sama dengan T3(>=0).Node yang ditambahkan akan menjadi child dari T2 dan T3.

Deletion AVL

operasi penghapusan node sama seperti pada Binary Search Tree yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan.jika yang dihapus adalah leaf,maka langsung dihapus.namun jika node yang dihapus memiliki child maka childnya yang menggantikannya.dan tree dicek sampai keduanya seimbang.

delete node 60

Sumber:http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html

               https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/

               http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html

Read More

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

DATA STRUCTURES



                                               LINKED LIST 2


LINKED LIST

Linked list atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memliki field yang menyimpan alamat/ referensi dari record selanjutnya (dalam urutan) elemen data yang dihubungkan dengan link pada linked list disebut Node. Biasanya didalam suatu lnked list, terdapat istilah head and tail.

•             Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

•             Tail adalah element yang berada pada posisis terakhir dalam suatu linked list

Ada Beberapa macam Linked List, yaitu:

1.            Single Linked List

Single Linked List merupakan suatu linked list yang hanya memiliki satu varuabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya.Biasanya field pada tail menunjuk ke NULL

Contoh:

2.            Double Linked List

Double Linked List Merupakan suatau linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke  NULL Contoh:

3.            Circular Linked List

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head(node pertama).Jadi tidak ada pointer yang menunjuk NULL ada 2 jenis Circular Linked List Yaitu:

•             Circular Single Linked List

Circular singly linked list is a type of data structure that is made up of nodes that are created using self referential structures. 

Contoh:

•             Circular Double Linked List

Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node. Circular doubly linked list doesn't contain NULL in any of the node. The last node of the list contains the address of the first node of the list. The first node of the list also contain address of the last node in its previous pointer.

Contoh:

4.            Multiple Linked List

Multi Linked List Merupakan Suatu Linked List yang Memiliki Lebih dari 2 buat variabel pointer

Contoh:

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

http://alvinstrukturdata.blogspot.com/2016/01/apa-itu-linked-list.html

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

Read More

On The Spot - Kontroversi Bumi Datar

Read More