Linked list - 003

-

Linked List

Rangkuman tanggal 10 Maret 2020


Materi GLSC ( Hashing and hash table, trees and binary tree )

Hashing and Hash Table


Hashing adalah teknik untuk menyimpan dan mengambil data secara cepat, lalu dalam Hashing sebuah string dari karakter akan diubah menjadi nilai (kunci) yang merepresentasikan string tersebut.
lalu string yang sudah diubah menjadi key tersebut disimpan dalam array yang biasa disebut hash table.

Hash table adalah sebuah sebuah array tempat kita menyimpan original string, index dari table nya berupa (kunci) yang kita dapatkan dari string tadi.

Ada beberapa cara untuk mengubah string menjadi kunci.
- Mid-square
- Division
- Folding
- Digit extraction
- Rotating dash

Mid-square
jadi cara ini adalah memangkatkan nilai dari sebuah string atau integer, lalu ambil bagian tengahnya.
misal angka 2020.
pangkat 2020 adalah 4.080.400
bagian tengahnya adalah 804.
804 adalah key dari 2020.

Division
ambil value ascii dari string, lalu kita modulo dengan jumlah ukuran table.
misal kata "BUDI" dan ukuran tabel kita ada 40.
kata "BUDI" mempunyai ascii (64+2 + 64+21 + 64+4 + 64+9) % 40 = 1
jadi 1 adalah key dari kata "BUDI".

Folding
pecah angka menjadi beberapa bagian, tambahkan dan ambil jumlah nya
misal angka 1234
pecah jadi 12 34
12+34 = 46
46 adalah key.

Digit extraction
mengekstrak key dari angka
misal ada angka 67890
angka pertama adalah 6, angka ketiga adalah 8, dan angka kelima adalah 0
maka key nya adalah 680.

Rotating dash
pakai metode division atau mid-square untuk mendapatkan key
lalu rotate untuk mendapatkan alamat dash yang baru.
misal key nya 804.
setelah di rotate menjadi 408.

karena kemungkinan pembentukan string atau angka sangatlah banyak, maka sangatlah mungkin ada beberapa string atau angka memiliki alamat yang sama.
bagaimana cara mengatasi nya?

kita bisa menggunakan linear probing dan chaning.

Linear probing adalah cara untuk menempatkan string di tempat yang kosong, dengan cara mengescan tiap array dan mencari tempat kosong.

Chaning adalah konsep untuk menempatkan string di tempat yang sama dan membuat chained list dengan linked list.

Implementasi hash table pada blockchain

Jadi didalam setiap block tersimpan data transaksi, siapa yang melakukan transaksi dan kapan transaksi dilakukan, data yang ada didalam setiap block akan diubah menjadi "hash"
setiap block saling terhubung dan setiap block menyimpan alamat "hash" dari block sebelumnya.

Tree

Tree adalah data-structure non linear yang merepresentasikan hubungan antara objek dalam data.


Node yang ada di paling atas disebut sebagai Node
Node yang tidak mempunyai children (cabang) disebut sebagai leaf
Node dan children nya dihubungkan dengan edge
Binary tree adalah tree yang setiap nodenya mempunyai paling banyak 2 children

 Tipe-tipe dari binary tree

 1.  Perfect binary tree
Adalah binary tree yang setiap nodenya mempunyai depth yang sama.
maksimum node dari perfect binary tree adalah 2^k-1.
dimana k adalah jumlah level.


2. Complete binary tree
Sama seperti perfect binary tree tetapi node yang berada di level paling bawah child nya bisa tidak ada.


3. Skewed binary tree
Adalah binary tree yang setiap node nya hanya mempunyai 1 cabang.


4. Balanced binary tree
Adalah binary tree yang ketika jumlah height di kiri - jumlah height di kanan = <=1.


sekian dari saya, dan maaf bila ada kesalahan karena saya juga masih belajar :) .
sumber :
https://www.researchgate.net/profile/Karim_Pichara/publication/322557308/figure/fig1/AS:588699666489344@1517368346649/The-generic-tree-data-structure-with-its-main-parts.png
https://www.barantum.com/blog/wp-content/uploads/2019/03/infographics-blockchain-1024x538.png

Comments

Post a Comment

Popular posts from this blog

Source code untuk Tugas GSLC

-
Source code untuk Tugas GSLC Aplikasi untuk jual beli barang Nama : Leander Ignacio Jose Antonius NIM : 2301922285 #include<stdio.h> #include<string.h> #include<stdlib.h> struct item { char namabarang[20]; int hargabarang; int quantitybarang; struct item *next; struct item *previous; }*head=NULL, *tail=NULL; void Printitem() { if(head==NULL&&tail==NULL) { printf("No Data\n"); } else { struct item *curr=head; int nomor=1; printf("==========================================\n"); while(curr!=NULL) { printf("Data %d\n",nomor); printf("Nama barang : %s\n",curr->namabarang); printf("Harga barang : %d\n",curr->hargabarang); printf("Jumlah barang : %d\n",curr->quantitybarang); curr=curr->next; printf("==========================================\n"); nomor++; } nomor=1; } } void Updateitem() { ...
Read more

Heaps and tries

-
Image
Video conference 12-5-2020 Heaps and Tries Heaps adalah sebuah binary tree yang isinya (nodenya) dapat direpresentasikan dalam sebuah array. cara memasukkan datanya adalah masukkan data dari array secara berurutan dari index 1-10 data pertamanya sebagai root, data ke 2 dan 3 sebagai left child dan right child, dan seterusnya. cara menghitung index x sebagai index menghitung index parent : x/2 menghitung index left child : 2*x menghitung index right child : (2*x)+1 misal kita mengambil node 18 yang memiliki index 4 (dari gambar di atas) untuk menghitung index parent (node 15) : 4/2=2 untuk menghitung index left child : 4*2=8 untuk menghitung index right child : (4*2)+1=9 Min heap dan max heap Min heap : setiap node pasti lebih kecil dari pada child node. angka terkecil yang ada di min heap pasti ada di rootnya. Insertion di Min heap ada 2 cara untuk insert di min heap cara 1 : Upheap Masukkan node seperti biasa, lalu bandingkan dengan node di atas...
Read more

Linked list - 002

-
Image
Linked list Rangkuman tanggal 3 maret 2020 Jadi di post ini saya akan merangkum materi yang disampaikan hari ini, dan juga materi yang ada di minggu pertama. Rangkuman minggu pertama Mulai dari cara mendeclare struct untuk linked list dan cara menambahkan node meng-set value ke node yang sudah dibuat dan meng-set penunjuk dari node ke node lain dengan ini kedua node yang baru saja kita buat sudah terhubung, dan jika kita print kedua node tadi kita bisa mengeprint node dengan cara printf("%d",node->value); printf("%d",node->next->value); Namun jika kita ingin membuat banyak node, akan lebih mudah jika kita membuat fungsi untuk membuat node fungsi ini untuk membuat node baru,cara menggunakannya adalah : struct tnode* node=node_maker(1); struct tnode* node1=node_maker(2); dan secara otomatis akan terbuat (node) yang berisi 1 dan (node1) yang terisi 2 namun disini kita tetap harus memberi tahu bahwa nod...
Read more