Felina Suryadi
2301914604
Hari: Rabu, 10 Juni 2020
Kelas: CB01-CL
Lecture: Henry Chong (D4460)
dan
Ferdinand Ariandy Luwinda (D4522)
------------------------------------------------------
Hari: Rabu, 10 Juni 2020
Kelas: CB01-CL
Lecture: Henry Chong (D4460)
dan
Ferdinand Ariandy Luwinda (D4522)
------------------------------------------------------
--- TUGAS BLOG ALGO-BINUS Mingguan ---
REVIEW II
-------------------------------------
------------------------------------------------------
------------------------------------------------------
LINKED LISTED
------------------------------------------------------------------------
------------------------------------------------------------------------
a. Pengertian Linked List
Linked list adalah bagian dari data structure yang terdiri dari kumpulan record data yang berurutan dimana setiap record data mengandung sebuah field atau tempat yang berhubungan dengan referensi dari record selanjutnya (dalam urutan).
Istilah-istilah dalam linked list:
Berikut gambaran dari linked list
*Contoh gambar single linked list
- Setiap elemen pada struktur data terkandung lebih dari satu tempat/field, satu tempat/field sebagai value dari integer, dan satu tempat/field lainnya digunakan untuk menghubungkan(linked) dengan node urutan selanjutnya.
- Contoh gambaran diatas adalah single linked list (hanya terkandung satu tempat/field untuk menghubungan dengan node selanjutnya).
Linked list adalah bagian dari data structure yang terdiri dari kumpulan record data yang berurutan dimana setiap record data mengandung sebuah field atau tempat yang berhubungan dengan referensi dari record selanjutnya (dalam urutan).
Istilah-istilah dalam linked list:
• Node adalah element data yang terhubung menggunakan linked list,
• Head adalah elemen yang berada pada posisi pertama dalam suatu linked list, dan
• Tail adalah element yang berada pada posisis terakhir dalam suatu linked list
Linked list memperbolehkan penambahan atau penghapusan setiap elemen dalam linked list pada posisi struktur manapun.
Berikut gambaran dari linked list
Berikut gambaran dari linked list
*Contoh gambar single linked list
- Setiap elemen pada struktur data terkandung lebih dari satu tempat/field, satu tempat/field sebagai value dari integer, dan satu tempat/field lainnya digunakan untuk menghubungkan(linked) dengan node urutan selanjutnya.
- Contoh gambaran diatas adalah single linked list (hanya terkandung satu tempat/field untuk menghubungan dengan node selanjutnya).
b. Cara Kerja Linked List
Linked list dalam algoritma programming menggunakan pointer untuk menjalankannya dan saling terhubung.
Linked list dalam algoritma programming menggunakan pointer untuk menjalankannya dan saling terhubung.
c. Jenis-jenis Linked List
Ada 2 tipe linked list, yaitu:
- Single Linked List
- Double Linked List
1. Single Linked List
Single linked list adalah jenis linked list yang hanya mengarah ke satu node saja (hanya memiliki satu variabel pointer). Karena hanya menunjuk ke satu node, maka single linked list hanya dapat berjalan ke satu arah saja (ke atas, ke bawah, ke kanan, atau ke kiri). Biasanya, field atau elemen tail dari struktur data single linked list tidak mengarah ke elemen field manapun(atau mengarah ke NULL).
contoh gambaran single linked list (1)
contoh gambaran single linked list (2)
Dalam single linked list akan dikenal istilah insert dan delete. Insert digunakan ketika kita hendak menambahkan data pada struktur data di bagian tertentu. Sedangkan delete digunakan untuk menghapus data pada struktur data di bagian tertentu.
--Circular Single Linked List--
Dalam single linked list, terdapat juga circular linked list. Circular single linked list dapat diartikan sebagai single linked list yang elemen akhir (tail) pada struktur data mengarah/menuju/terhubung dengan elemen awal (head) dari struktur data tersebut.
Gambaran Circular Single Linked List
2. Double Linked List
Double linked list adalah jenis linked list yang dapat mengarah ke lebih dari satu node (memiliki variabel pointer ganda). Karena terdapat 2 field/tempat, maka double linked list dapat mengarah ke 2 node elemen lainnya. Biasanya head dan tail dari double linked list tidak mengarah kemanapun (atau mengarah ke NULL).
Berikut contoh gambaran double linked list:
contoh gambaran double linked list
Dalam double linked list juga dikenal istilah insert dan delete. sama seperti single linked list, kegunaan insert adalah untuk menambahkan data pada struktur data di bagian tertentu. Sedangkan delete digunakan untuk menghapus data pada struktur data di bagian tertentu.
--Circular Double Linked List--
Dalam double linked list juga terdapat circular linked list. Circular double linked list sendiri diartikan sama seperti circular singe linked list, namun yang membedakan adalah setiap node head dan tail pada circular double linked list memiliki 2 pointer (head mengarah ke tail, dan tail mengarah ke head melalui arah yang saling belawanan).
contoh gambaran circular double linked list
------------------------------------------------------------------------
Ada 2 tipe linked list, yaitu:
- Single Linked List
- Double Linked List
1. Single Linked List
Single linked list adalah jenis linked list yang hanya mengarah ke satu node saja (hanya memiliki satu variabel pointer). Karena hanya menunjuk ke satu node, maka single linked list hanya dapat berjalan ke satu arah saja (ke atas, ke bawah, ke kanan, atau ke kiri). Biasanya, field atau elemen tail dari struktur data single linked list tidak mengarah ke elemen field manapun(atau mengarah ke NULL).
 |
| contoh gambaran single linked list (1) |
 |
| contoh gambaran single linked list (2) |
Dalam single linked list akan dikenal istilah insert dan delete. Insert digunakan ketika kita hendak menambahkan data pada struktur data di bagian tertentu. Sedangkan delete digunakan untuk menghapus data pada struktur data di bagian tertentu.
--Circular Single Linked List--
Dalam single linked list, terdapat juga circular linked list. Circular single linked list dapat diartikan sebagai single linked list yang elemen akhir (tail) pada struktur data mengarah/menuju/terhubung dengan elemen awal (head) dari struktur data tersebut.
Gambaran Circular Single Linked List
2. Double Linked List
Double linked list adalah jenis linked list yang dapat mengarah ke lebih dari satu node (memiliki variabel pointer ganda). Karena terdapat 2 field/tempat, maka double linked list dapat mengarah ke 2 node elemen lainnya. Biasanya head dan tail dari double linked list tidak mengarah kemanapun (atau mengarah ke NULL).
Berikut contoh gambaran double linked list:
 |
| contoh gambaran double linked list |
Dalam double linked list juga dikenal istilah insert dan delete. sama seperti single linked list, kegunaan insert adalah untuk menambahkan data pada struktur data di bagian tertentu. Sedangkan delete digunakan untuk menghapus data pada struktur data di bagian tertentu.
--Circular Double Linked List--
Dalam double linked list juga terdapat circular linked list. Circular double linked list sendiri diartikan sama seperti circular singe linked list, namun yang membedakan adalah setiap node head dan tail pada circular double linked list memiliki 2 pointer (head mengarah ke tail, dan tail mengarah ke head melalui arah yang saling belawanan).
 |
| contoh gambaran circular double linked list |
------------------------------------------------------------------------
STACK & QUEUE
------------------------------------------------------------------------
------------------------------------------------------------------------
A. Stack Concept
Stack diartikan sebagai tumpukan. Stack sendiri dapat kita analogikan oleh tumpukan piring. Pada posisi terbawah tumpukan adalah piring yang pertama kali kita taruh. Sedangkan pada posisi paling atas adalah piring yang terakhir kita taruh.
analogi stack
Ilustrasi penumpukan piring tersebut adalah gambaran mengenai stack, maka pada stack data yang terakhir kali ditumpuk, maka data tersebut yang akan diambil pertama kali pada saat pemrosesan. Metode ini disebut LIFO ( Last In First Out ).
Jadi, karakteristik penting Stack yang bersifat LIFO (Last In First Out) ini, diartikan bahwa data yang terakhir masuk merupakan data yang akan keluar terlebih dahulu.
Stack ini merupakan data struktur linear yang bisa di emplementasikan dengan penggunaan array ataupun linked list.
Stack diartikan sebagai tumpukan. Stack sendiri dapat kita analogikan oleh tumpukan piring. Pada posisi terbawah tumpukan adalah piring yang pertama kali kita taruh. Sedangkan pada posisi paling atas adalah piring yang terakhir kita taruh.
|
| analogi stack |
Ilustrasi penumpukan piring tersebut adalah gambaran mengenai stack, maka pada stack data yang terakhir kali ditumpuk, maka data tersebut yang akan diambil pertama kali pada saat pemrosesan. Metode ini disebut LIFO ( Last In First Out ).
Jadi, karakteristik penting Stack yang bersifat LIFO (Last In First Out) ini, diartikan bahwa data yang terakhir masuk merupakan data yang akan keluar terlebih dahulu.
Stack ini merupakan data struktur linear yang bisa di emplementasikan dengan penggunaan array ataupun linked list.
B. Penggunaan Stack
Pada beberapa literatur menyebutkan bahwa stack umumnya digunakan untuk memisahkan ekspresi aritmatika.
Pada beberapa literatur menyebutkan bahwa stack umumnya digunakan untuk memisahkan ekspresi aritmatika.
C. Algoritma Stack
Sederhananya seperti ini: ketika memasukkan data, uji apakah stack (array) sudah penuh? Jika benar, maka data tidak dapat disimpan. Jika tidak, maka data akan disimpan dan menjadi data yang paling atas dari data sebelumnya. Kemudian bagaimana dengan langkah mengeluarkan data? Sama. Uji apakah stack kosong? Jika benar, maka proses selesai karena tidak ada data yang harus dikeluarkan. Sebaliknya, maka ambil data yang paling akhir (atas) untuk dikeluarkan.
Sederhananya seperti ini: ketika memasukkan data, uji apakah stack (array) sudah penuh? Jika benar, maka data tidak dapat disimpan. Jika tidak, maka data akan disimpan dan menjadi data yang paling atas dari data sebelumnya. Kemudian bagaimana dengan langkah mengeluarkan data? Sama. Uji apakah stack kosong? Jika benar, maka proses selesai karena tidak ada data yang harus dikeluarkan. Sebaliknya, maka ambil data yang paling akhir (atas) untuk dikeluarkan.
D. Operasi pada Stack
- push(x) : menambahkan sebuat elemen atau data pada stack terakhir (atas),
- pop() : menghapus sebuah elemen atau data dari stack terakhir (atas),
- top() : berfungsi untuk melihat data yang berada pada tumpukan paling atas
(akan dikeluarkan), top ini juga dikenal dengan peek().
- push(x) : menambahkan sebuat elemen atau data pada stack terakhir (atas),
- pop() : menghapus sebuah elemen atau data dari stack terakhir (atas),
- top() : berfungsi untuk melihat data yang berada pada tumpukan paling atas
(akan dikeluarkan), top ini juga dikenal dengan peek().
- pop() : menghapus sebuah elemen atau data dari stack terakhir (atas),
- top() : berfungsi untuk melihat data yang berada pada tumpukan paling atas
(akan dikeluarkan), top ini juga dikenal dengan peek().
E. Queue Concept
Queue adalah struktur data penting yang menyimpan elemen-elemennya secara teratur. Jika pada Stack data diurutkan dengan metode LIFO, queue memiliki karakteristik First In First Out (FIFO), jadi data akan disusun secara antrian, sama pada saat kita mengantri. Yang pertama kali datang maka akan berada di posisi terdepan dan siap untuk dilayani terlebih dahulu, sedangkan yang datang terakhir akan berada di posisi paling belakang dan mendapatkan layanan terakhir.
Queue juga bisa di emplementasikan dengan penggunaan array ataupun linked list.
Queue adalah struktur data penting yang menyimpan elemen-elemennya secara teratur. Jika pada Stack data diurutkan dengan metode LIFO, queue memiliki karakteristik First In First Out (FIFO), jadi data akan disusun secara antrian, sama pada saat kita mengantri. Yang pertama kali datang maka akan berada di posisi terdepan dan siap untuk dilayani terlebih dahulu, sedangkan yang datang terakhir akan berada di posisi paling belakang dan mendapatkan layanan terakhir.
Queue juga bisa di emplementasikan dengan penggunaan array ataupun linked list.
F. Operasi pada Queue
- push(x) : menambahkan sebuat elemen atau data pada belakang antrian/queue,
- pop() : menghapus sebuah elemen atau data pada depan antrian/queue,
- front() : berfungsi untuk melihat data yang berada pada baris paling depan (akan
dikeluarkan), front juga dikenal dengan peek().
...
------------------------------------------------------------------------
- push(x) : menambahkan sebuat elemen atau data pada belakang antrian/queue,
- pop() : menghapus sebuah elemen atau data pada depan antrian/queue,
- front() : berfungsi untuk melihat data yang berada pada baris paling depan (akan
dikeluarkan), front juga dikenal dengan peek().
- pop() : menghapus sebuah elemen atau data pada depan antrian/queue,
- front() : berfungsi untuk melihat data yang berada pada baris paling depan (akan
dikeluarkan), front juga dikenal dengan peek().
...
------------------------------------------------------------------------
------------------------------------------------------------------------
HASHING TABLE & BINARY TREE
------------------------------------------------------
------------------------------------------------------
A. Hashing
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Dalam hashing, string karakter ditransformasikan menjadi nilai panjang yang biasanya lebih pendek atau menjadi kunci baru yang mewakili string asli. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli. Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut tabel hash menggunakan fungsi yang telah ditentukan yang disebut fungsi hash.
Tugas utama Hashing adalah untuk memastikan integritas (keutuhan). Contohnya, kita ada sebuah file. Dengan di-Hashing kita akan memdapatkan nilai tertentu sebagai bagian integritas file tersebut. Apabila file itu dirubah, maka nilainya tidak akan sama lagi dengan Hashing pertama. Jadi kita bisa tahu ini bukan file yang sama, ini yang kita sebuat integritas dari sebuah file.
Penerapan umum dari Hashing ini terlihat pada saat kita melakukan Authentication. Pada saat kita login, yang dikirim ke server adalah hash yang akan dibandingkan dengan hashyang sudah ada di server. Jadi kita tidak pernah mengirim user-name dan password lewat jaringan, yang ada kemungkinan disadap.
Dan cara yang sama ketika kita mengirim pesan yang sudah sudah di-Encryption dengan private-key. Kita kirim pesan itu disertai private-key yang di-hash. Di sisi server hash itu dicocokan dengan yang ada di-server. Kalau valid maka paket itu akan bisa dibuka.
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Dalam hashing, string karakter ditransformasikan menjadi nilai panjang yang biasanya lebih pendek atau menjadi kunci baru yang mewakili string asli. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli. Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut tabel hash menggunakan fungsi yang telah ditentukan yang disebut fungsi hash.
Tugas utama Hashing adalah untuk memastikan integritas (keutuhan). Contohnya, kita ada sebuah file. Dengan di-Hashing kita akan memdapatkan nilai tertentu sebagai bagian integritas file tersebut. Apabila file itu dirubah, maka nilainya tidak akan sama lagi dengan Hashing pertama. Jadi kita bisa tahu ini bukan file yang sama, ini yang kita sebuat integritas dari sebuah file.
Penerapan umum dari Hashing ini terlihat pada saat kita melakukan Authentication. Pada saat kita login, yang dikirim ke server adalah hash yang akan dibandingkan dengan hashyang sudah ada di server. Jadi kita tidak pernah mengirim user-name dan password lewat jaringan, yang ada kemungkinan disadap.
Dan cara yang sama ketika kita mengirim pesan yang sudah sudah di-Encryption dengan private-key. Kita kirim pesan itu disertai private-key yang di-hash. Di sisi server hash itu dicocokan dengan yang ada di-server. Kalau valid maka paket itu akan bisa dibuka.
Tugas utama Hashing adalah untuk memastikan integritas (keutuhan). Contohnya, kita ada sebuah file. Dengan di-Hashing kita akan memdapatkan nilai tertentu sebagai bagian integritas file tersebut. Apabila file itu dirubah, maka nilainya tidak akan sama lagi dengan Hashing pertama. Jadi kita bisa tahu ini bukan file yang sama, ini yang kita sebuat integritas dari sebuah file.
Penerapan umum dari Hashing ini terlihat pada saat kita melakukan Authentication. Pada saat kita login, yang dikirim ke server adalah hash yang akan dibandingkan dengan hashyang sudah ada di server. Jadi kita tidak pernah mengirim user-name dan password lewat jaringan, yang ada kemungkinan disadap.
Dan cara yang sama ketika kita mengirim pesan yang sudah sudah di-Encryption dengan private-key. Kita kirim pesan itu disertai private-key yang di-hash. Di sisi server hash itu dicocokan dengan yang ada di-server. Kalau valid maka paket itu akan bisa dibuka.
B. Hash Table
Hash table adalah tabel (larik) tempat kami menyimpan string asli. Indeks tabel adalah kunci hash sementara yang nilainya adalah string asli. Ukuran tabel hash biasanya beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki kunci hash yang sama.
Hash table adalah tabel (larik) tempat kami menyimpan string asli. Indeks tabel adalah kunci hash sementara yang nilainya adalah string asli. Ukuran tabel hash biasanya beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki kunci hash yang sama.
C. Hash Function
Ada sangat banyak cara untuk meng-hash sebuah string menjadi sebuah kunci. Berikut merupakan beberapa cara penting untuk mengkontruksi fungsi hash:
•Mid-square
•Division (most common)
•Folding
•Digit Extraction
•Rotating Hash
Ada sangat banyak cara untuk meng-hash sebuah string menjadi sebuah kunci. Berikut merupakan beberapa cara penting untuk mengkontruksi fungsi hash:
•Mid-square
•Division (most common)
•Folding
•Digit Extraction
•Rotating Hash
D. Tree Introduction
Tree adalah struktur data non-linear yang mewakili hubungan hierarkis antar objek data. Beberapa hubungan tree dapat diamati dalam struktur direktori atau hierarki organisasi. Node pada tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan kemudian dapat dihubungkan oleh pointer.
Tree adalah struktur data non-linear yang mewakili hubungan hierarkis antar objek data. Beberapa hubungan tree dapat diamati dalam struktur direktori atau hierarki organisasi. Node pada tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan kemudian dapat dihubungkan oleh pointer.
E. Tree Concept
Tree juga dapat dikatakan kumpulan dari satu atau lebih node-node.
Dalam konsep tree, terdapat:
- Node pada atas tree disebut sebagai root
- Garis yang menghubungkan parent(induk) ke children(anak) disebut edge
- Node yang tidak memiliki childreen (anak) disebut leaf
- Node yang memiliki parent(induk) yang sama disebut sibling
- Derajat node(degree) adalah total sub node dari tree
- Height/Depth adalah tingkat degree maksimum node dalam tree
- Jika ada garis yang menghubungkan p ke q, maka p disebut ancestor dari q, dan q adalah descendant dari p
Contoh Gambaran Tree:
Dari gambar di atas, didapatkan:
- DEGREE dari TREE = 3
- DEGREE dari C = 2
- HEIGHT/DEPTH = 3
- PARENT dari C = A
- CHILDREN dari A = B, C, D
- SIBILING dari F = G
- ANCESTOR dari F = A, C
- DESCENDANT dari C = F, G
Tree juga dapat dikatakan kumpulan dari satu atau lebih node-node.
Dalam konsep tree, terdapat:
- Node pada atas tree disebut sebagai root
- Garis yang menghubungkan parent(induk) ke children(anak) disebut edge
- Node yang tidak memiliki childreen (anak) disebut leaf
- Node yang memiliki parent(induk) yang sama disebut sibling
- Derajat node(degree) adalah total sub node dari tree
- Height/Depth adalah tingkat degree maksimum node dalam tree
- Jika ada garis yang menghubungkan p ke q, maka p disebut ancestor dari q, dan q adalah descendant dari p
Contoh Gambaran Tree:
Dari gambar di atas, didapatkan:
- DEGREE dari TREE = 3
- DEGREE dari C = 2
- HEIGHT/DEPTH = 3
- PARENT dari C = A
- CHILDREN dari A = B, C, D
- SIBILING dari F = G
- ANCESTOR dari F = A, C
- DESCENDANT dari C = F, G
F. Binary Tree Concept
Binary tree adalah struktur data rooted tree di mana setiap node memiliki paling banyak dua children(anak). Kedua children(anak) itu biasanya dibedakan sebagai left child(anak kiri) dan right child(anak kanan). Node yang tidak memiliki anak disebut leaf.
Binary tree adalah struktur data rooted tree di mana setiap node memiliki paling banyak dua children(anak). Kedua children(anak) itu biasanya dibedakan sebagai left child(anak kiri) dan right child(anak kanan). Node yang tidak memiliki anak disebut leaf.
G. Type of Binary Tree
Berikut merupakan jenis-jenis binary tree:
-
PERFECT binary tree : Merupakan tree biner di mana semuanya berada pada depth yang sama.
- COMPLETE binary tree: Merupakan tree biner di mana semuanya, kecuali yang terakhir, terisi penuh, dan semua node sejauh mungkin diabaikan. Complete binary tree adalah tree biner yang lengkap.
- SKEWED binary tree: Merupakan tree biner di mana setiap node memiliki paling banyak satu children(anak).
- BALANCED binary tree: Merupakan tree biner di mana tidak ada leaf yang jauh dari root daripada terhadap leaf lainnya.
Berikut merupakan jenis-jenis binary tree:
- PERFECT binary tree : Merupakan tree biner di mana semuanya berada pada depth yang sama.
- COMPLETE binary tree: Merupakan tree biner di mana semuanya, kecuali yang terakhir, terisi penuh, dan semua node sejauh mungkin diabaikan. Complete binary tree adalah tree biner yang lengkap.
- SKEWED binary tree: Merupakan tree biner di mana setiap node memiliki paling banyak satu children(anak).
- BALANCED binary tree: Merupakan tree biner di mana tidak ada leaf yang jauh dari root daripada terhadap leaf lainnya.
H. Blockchain
Sebagian besar dunia teknologi cryptocurrency seperti Bitcoin mengandalkan bentuk database dengan keunggulan mampu melacak volume transaksi yang besar dan aman. Teknologi yang digunakan banyak mata uang digital itu adalah Blockchain.
Blockchain pertama kali diimplementasikan pada tahun 2009, dan direvolusi dengan Blockchain 2.0 pada tahun 2014. Teknologi Blockchain terdiri dari blok yang menampung transaksi, di mana masing-masing blok saling terkait melalui kriptografi, sehingga membentuk jaringan.
Seiring dengan perkembangan jagat digital, cryptocurreny di masa depan telah menjadi proposisi yang semakin menarik di pasar dan mungkin tidak memiliki infrastruktur perbankan tradisional. Beberapa negara berkembang di dunia bahkan telah menerapkan mata uang nasional berbasis Blockchain, seperti Bitcoin, dan teknologinya juga digunakan oleh beberapa proyek amal besar untuk membantu mereka yang tidak memiliki rekening bank.
Blockchain juga berpotensi untuk digunakan di luar lingkup mata uang digital, dan menarik minat banyak lembaga keuangan tradisional untuk diadopsi.
Sebagian besar dunia teknologi cryptocurrency seperti Bitcoin mengandalkan bentuk database dengan keunggulan mampu melacak volume transaksi yang besar dan aman. Teknologi yang digunakan banyak mata uang digital itu adalah Blockchain.
Blockchain pertama kali diimplementasikan pada tahun 2009, dan direvolusi dengan Blockchain 2.0 pada tahun 2014. Teknologi Blockchain terdiri dari blok yang menampung transaksi, di mana masing-masing blok saling terkait melalui kriptografi, sehingga membentuk jaringan.
Seiring dengan perkembangan jagat digital, cryptocurreny di masa depan telah menjadi proposisi yang semakin menarik di pasar dan mungkin tidak memiliki infrastruktur perbankan tradisional. Beberapa negara berkembang di dunia bahkan telah menerapkan mata uang nasional berbasis Blockchain, seperti Bitcoin, dan teknologinya juga digunakan oleh beberapa proyek amal besar untuk membantu mereka yang tidak memiliki rekening bank.
Blockchain juga berpotensi untuk digunakan di luar lingkup mata uang digital, dan menarik minat banyak lembaga keuangan tradisional untuk diadopsi.
Blockchain pertama kali diimplementasikan pada tahun 2009, dan direvolusi dengan Blockchain 2.0 pada tahun 2014. Teknologi Blockchain terdiri dari blok yang menampung transaksi, di mana masing-masing blok saling terkait melalui kriptografi, sehingga membentuk jaringan.
Seiring dengan perkembangan jagat digital, cryptocurreny di masa depan telah menjadi proposisi yang semakin menarik di pasar dan mungkin tidak memiliki infrastruktur perbankan tradisional. Beberapa negara berkembang di dunia bahkan telah menerapkan mata uang nasional berbasis Blockchain, seperti Bitcoin, dan teknologinya juga digunakan oleh beberapa proyek amal besar untuk membantu mereka yang tidak memiliki rekening bank.
Blockchain juga berpotensi untuk digunakan di luar lingkup mata uang digital, dan menarik minat banyak lembaga keuangan tradisional untuk diadopsi.
I. Cara Kerja Blockchain
Sistem Blockchain terdiri dari dua jenis record, transaksi dan blok. Transaksi ini disimpan secara bersama-sama dalam satu blok. Hal yang unik dari Blockchain adalah setiap blok berisi hash kriptografi sehingga membentuk jaringan. Fungsi hash kriptografi adalah mengambil data dari blok sebelumnya dan mengubahnya menjadi compact string. String ini memungkinkan sistem bisa mudah mendeteksi adanya sabotase.
Dengan metode tersebut, artinya setiap blok tidak perlu memiliki nomor seri, hash memungkinkan setiap blok dapat memverifikasi integritasnya. Setiap blok akan menegaskan validitasnya dari blok sebelumnya. Keterkaitan blok bukanlah satu-satunya hal yang membuat jaringan tetap aman. Teknologi ini juga terdesentralisasi, setiap komputer dengan perangkat lunak yang diinstal memiliki salinan Blockchain yang terus diperbarui dengan blok baru. Tidak ada server terpusat yang memegang transaksi, dan karena setiap blok baru harus memenuhi persyaratan dalam rantai atau jaringan, maka tidak ada yang bisa menimpa transaksi sebelumnya.
Persyaratan transaksi lainnya, yaitu dapat digunakan untuk menentukan entri yang valid. Di Bitcoin, misalnya, transaksi yang valid harus ditandatangani secara digital, dan harus mengeluarkan satu atau lebih output yang tidak terpakai dari transaksi sebelumnya, serta jumlah keluaran transaksi tidak dapat melebihi jumlah input.
Sistem Blockchain terdiri dari dua jenis record, transaksi dan blok. Transaksi ini disimpan secara bersama-sama dalam satu blok. Hal yang unik dari Blockchain adalah setiap blok berisi hash kriptografi sehingga membentuk jaringan. Fungsi hash kriptografi adalah mengambil data dari blok sebelumnya dan mengubahnya menjadi compact string. String ini memungkinkan sistem bisa mudah mendeteksi adanya sabotase.
Dengan metode tersebut, artinya setiap blok tidak perlu memiliki nomor seri, hash memungkinkan setiap blok dapat memverifikasi integritasnya. Setiap blok akan menegaskan validitasnya dari blok sebelumnya. Keterkaitan blok bukanlah satu-satunya hal yang membuat jaringan tetap aman. Teknologi ini juga terdesentralisasi, setiap komputer dengan perangkat lunak yang diinstal memiliki salinan Blockchain yang terus diperbarui dengan blok baru. Tidak ada server terpusat yang memegang transaksi, dan karena setiap blok baru harus memenuhi persyaratan dalam rantai atau jaringan, maka tidak ada yang bisa menimpa transaksi sebelumnya.
Persyaratan transaksi lainnya, yaitu dapat digunakan untuk menentukan entri yang valid. Di Bitcoin, misalnya, transaksi yang valid harus ditandatangani secara digital, dan harus mengeluarkan satu atau lebih output yang tidak terpakai dari transaksi sebelumnya, serta jumlah keluaran transaksi tidak dapat melebihi jumlah input.
Dengan metode tersebut, artinya setiap blok tidak perlu memiliki nomor seri, hash memungkinkan setiap blok dapat memverifikasi integritasnya. Setiap blok akan menegaskan validitasnya dari blok sebelumnya. Keterkaitan blok bukanlah satu-satunya hal yang membuat jaringan tetap aman. Teknologi ini juga terdesentralisasi, setiap komputer dengan perangkat lunak yang diinstal memiliki salinan Blockchain yang terus diperbarui dengan blok baru. Tidak ada server terpusat yang memegang transaksi, dan karena setiap blok baru harus memenuhi persyaratan dalam rantai atau jaringan, maka tidak ada yang bisa menimpa transaksi sebelumnya.
Persyaratan transaksi lainnya, yaitu dapat digunakan untuk menentukan entri yang valid. Di Bitcoin, misalnya, transaksi yang valid harus ditandatangani secara digital, dan harus mengeluarkan satu atau lebih output yang tidak terpakai dari transaksi sebelumnya, serta jumlah keluaran transaksi tidak dapat melebihi jumlah input.
J. Hashing dalam Blockchain
Secara sederhana, hashing berarti mengambil string input dengan panjang berapa pun dan memberikan output dengan panjang tetap .Dalam konteks cryptocurrency seperti Bitcoin, transaksi diambil sebagai input dan dijalankan melalui algoritma hashing (Bitcoin menggunakan SHA-256 ) yang memberikan output dengan panjang tetap.
Mari kita lihat bagaimana proses hashing bekerja. Kami akan memasukkan input tertentu. Untuk latihan ini, kita akan menggunakan SHA-256 (Secure Hashing Algorithm 256).
Seperti yang Anda lihat, dalam kasus SHA-256 , tidak peduli seberapa besar atau kecil input Anda, output akan selalu memiliki panjang 256-bit tetap. Ini menjadi penting ketika Anda berurusan dengan sejumlah besar data dan transaksi. Jadi pada dasarnya, alih-alih mengingat input data yang bisa jadi besar, Anda bisa mengingat hash dan terus melacak. Sebelum kita melangkah lebih jauh, kita perlu terlebih dahulu melihat berbagai properti fungsi hashing dan bagaimana mereka diimplementasikan di blockchain.
Secara sederhana, hashing berarti mengambil string input dengan panjang berapa pun dan memberikan output dengan panjang tetap .Dalam konteks cryptocurrency seperti Bitcoin, transaksi diambil sebagai input dan dijalankan melalui algoritma hashing (Bitcoin menggunakan SHA-256 ) yang memberikan output dengan panjang tetap.
Mari kita lihat bagaimana proses hashing bekerja. Kami akan memasukkan input tertentu. Untuk latihan ini, kita akan menggunakan SHA-256 (Secure Hashing Algorithm 256).
Mari kita lihat bagaimana proses hashing bekerja. Kami akan memasukkan input tertentu. Untuk latihan ini, kita akan menggunakan SHA-256 (Secure Hashing Algorithm 256).
Seperti yang Anda lihat, dalam kasus SHA-256 , tidak peduli seberapa besar atau kecil input Anda, output akan selalu memiliki panjang 256-bit tetap. Ini menjadi penting ketika Anda berurusan dengan sejumlah besar data dan transaksi. Jadi pada dasarnya, alih-alih mengingat input data yang bisa jadi besar, Anda bisa mengingat hash dan terus melacak. Sebelum kita melangkah lebih jauh, kita perlu terlebih dahulu melihat berbagai properti fungsi hashing dan bagaimana mereka diimplementasikan di blockchain.
J. Kesimpulan
Hashing merupakan salah satu dasar dalam penciptaan teknologi blockchain.
.....
------------------------------------------------------------------------
Hashing merupakan salah satu dasar dalam penciptaan teknologi blockchain.
.....
------------------------------------------------------------------------
BINARY SEARCH TREE
------------------------------------------------------------------------
------------------------------------------------------------------------
1. Binary Search Tree (BST)
Binary Search Tree (BST) merupakan salah satu struktur data yang mensupport metode pencarian(searching) dan pengurutan(sorting) secara cepat, serta penambahan atau pengurangan data/elemen secara mudah. BST juga diketahui sebagai binary tree yang terurut.
Binary Search Tree (BST) merupakan salah satu struktur data yang mensupport metode pencarian(searching) dan pengurutan(sorting) secara cepat, serta penambahan atau pengurangan data/elemen secara mudah. BST juga diketahui sebagai binary tree yang terurut.
2. Sifat Binary Search Tree
Dalam binary search tree, intinya adalah data-data tersebut terurut. Biasanya uruta-urutan data/node/elemen tersebut adalah:
- Subtree kiri mengandung semua elemen yang lebih kecil dibanding subtree kanan
- Subtree kanan mengandung semua elemen yang lebih besar dibanding subtree kiri
Karena intinya terurut, maka bisa juga sebaliknya, namun, yang lazim dan biasa digunakan saat ini adalah subtree kiri selalu mengandung elemen yang lebih kecil dibanding subtree kanan.
contoh BST:
Dalam binary search tree, intinya adalah data-data tersebut terurut. Biasanya uruta-urutan data/node/elemen tersebut adalah:
- Subtree kiri mengandung semua elemen yang lebih kecil dibanding subtree kanan
- Subtree kanan mengandung semua elemen yang lebih besar dibanding subtree kiri
Karena intinya terurut, maka bisa juga sebaliknya, namun, yang lazim dan biasa digunakan saat ini adalah subtree kiri selalu mengandung elemen yang lebih kecil dibanding subtree kanan.
contoh BST:
- Subtree kiri mengandung semua elemen yang lebih kecil dibanding subtree kanan
- Subtree kanan mengandung semua elemen yang lebih besar dibanding subtree kiri
Karena intinya terurut, maka bisa juga sebaliknya, namun, yang lazim dan biasa digunakan saat ini adalah subtree kiri selalu mengandung elemen yang lebih kecil dibanding subtree kanan.
contoh BST:
3. Operasi Binary Search Tree
Berikut merupakan operasi-operasi dasar dalam binary search tree:
- find(x) : untuk menemukan key x dalam BST
- insert(x) : untuk memasukkan/insert key x yang baru ke dalam BST
- remove(x) : untuk menghapus/menghilangkan key x dalam BST
Berikut merupakan operasi-operasi dasar dalam binary search tree:
- find(x) : untuk menemukan key x dalam BST
- insert(x) : untuk memasukkan/insert key x yang baru ke dalam BST
- remove(x) : untuk menghapus/menghilangkan key x dalam BST
4. Operasi Search/Find
Karena sifat dari BST, pencarian / searching / finding yang dilakukan dalam tree mmenggunakan BST menjadi mudah. Berikut algoritma pseucode ketika kita hendak mencari dimana X:
- Memulai dari root
- Jika root merupakan X, maka proses selesai
- Jika X lebih kecil dari root, maka pencarian dilanjukan ke subtree kiri, tapi jika X lebih besar dari root, maka dilanjutkan pencarian ke subtree kanan, begitu seterusnya hingga ditemukan X.
Karena sifat dari BST, pencarian / searching / finding yang dilakukan dalam tree mmenggunakan BST menjadi mudah. Berikut algoritma pseucode ketika kita hendak mencari dimana X:
- Memulai dari root
- Jika root merupakan X, maka proses selesai
- Jika X lebih kecil dari root, maka pencarian dilanjukan ke subtree kiri, tapi jika X lebih besar dari root, maka dilanjutkan pencarian ke subtree kanan, begitu seterusnya hingga ditemukan X.
5. Operasi Insertion
Memasukkan/inserting data/node/elemen kedalam BST diselesaikan sebacar berulang. Berikut algoritma pseucode memsukkan key X ke dalam BST:
- Dimulai dari root
- Jika X lebih kecil dari root atau node, X di masukkan ke bagian kiri subtree, jika X lebih besar maka ditempatkan ke bagian kanan subtree, hal ini terus dilakukan hingga ditemukan ruang kosong dalam tree untuk memasukkan X (X menjadi leaf baru).
Contoh: memasukkan key(35)
Memasukkan/inserting data/node/elemen kedalam BST diselesaikan sebacar berulang. Berikut algoritma pseucode memsukkan key X ke dalam BST:
- Dimulai dari root
- Jika X lebih kecil dari root atau node, X di masukkan ke bagian kiri subtree, jika X lebih besar maka ditempatkan ke bagian kanan subtree, hal ini terus dilakukan hingga ditemukan ruang kosong dalam tree untuk memasukkan X (X menjadi leaf baru).
Contoh: memasukkan key(35)
6. Operasi Delete
Dalam penghapusan node/elemen/data (contohnya: penghapusan key X) dalam BST, ada 3 pertimbangan:
1. Jika key X merupakan leaf(data paling bawah dalam tree), maka kita hapus data/leaf tersebut.
2. Jika key X merupakan node dengan satu anak, maka hapus node tersebut dan kemudian hubungkan anak dari X dengan parent dari X.
3. Jika key X merupakan node dengan dua anak, maka cari data paling kanan bawah(value paling tinggi) dari subtree sebelah kiri, kemudian replace/tukar dengan data tersebut dengan key X, lalu hapus key X, atau bisa menggunakan data paling kiri bawah (value paling kecil) dari subtree sebelahh kanan lalu replace/tukar data tersebut dengan key X lalu hapus key X.
contoh: deleting key(21)
contoh 2: delete key (37)
contoh 3: delete key(30)
------------------------------------------------------------------------
Dalam penghapusan node/elemen/data (contohnya: penghapusan key X) dalam BST, ada 3 pertimbangan:
1. Jika key X merupakan leaf(data paling bawah dalam tree), maka kita hapus data/leaf tersebut.
2. Jika key X merupakan node dengan satu anak, maka hapus node tersebut dan kemudian hubungkan anak dari X dengan parent dari X.
3. Jika key X merupakan node dengan dua anak, maka cari data paling kanan bawah(value paling tinggi) dari subtree sebelah kiri, kemudian replace/tukar dengan data tersebut dengan key X, lalu hapus key X, atau bisa menggunakan data paling kiri bawah (value paling kecil) dari subtree sebelahh kanan lalu replace/tukar data tersebut dengan key X lalu hapus key X.
contoh: deleting key(21)
contoh 2: delete key (37)
contoh 3: delete key(30)
------------------------------------------------------------------------
Heap and Tries
------------------------------------------------------------------------
------------------------------------------------------------------------
1. Heap
Heap adalah sebuah complete binary tree pada struktur data yang memenuhi properti heap. Properti heap yang dimaksud adalah min heap dan max heap.
Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika menggunakan array.
Heap adalah sebuah complete binary tree pada struktur data yang memenuhi properti heap. Properti heap yang dimaksud adalah min heap dan max heap.
Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika menggunakan array.
2. Min-Heap
Pada min heap, setiap elemen node pada tree lebih kecil daripada children/anaknya. Hal ini berarti elemen/nilai terkecil pada tree tersebut harus terletak pada root dan nilai/elemen tertinggi pada tree terletak di salah satu leaf/daun.
Contoh min-heap tree:
Pada min heap, setiap elemen node pada tree lebih kecil daripada children/anaknya. Hal ini berarti elemen/nilai terkecil pada tree tersebut harus terletak pada root dan nilai/elemen tertinggi pada tree terletak di salah satu leaf/daun.
Contoh min-heap tree:
3. Max-Heap
Pada max heap, setiap elemen node lebih besar daripada children/anaknya (kebalikan min-heap). Hal ini berarti elemen/nilai terkecil pada tree tersebut harus terletak pada salah satu leaf/daun dan nilai/elemen tertinggi pada tree terletak di root.
Contoh max-heap tree:
Pada max heap, setiap elemen node lebih besar daripada children/anaknya (kebalikan min-heap). Hal ini berarti elemen/nilai terkecil pada tree tersebut harus terletak pada salah satu leaf/daun dan nilai/elemen tertinggi pada tree terletak di root.
Contoh max-heap tree:
4. Heap Applications
Dalam pengaplikasi-an heap, dapat menggunakan Priority Queue dengan:
1. Selection Algorithms
2. Dijkstra's Algorithm
3. Prim Algorithm
Dapat juga menggunakan Heap Sort dengan: An O(n.lg(n)) algotihm.
Dalam pengaplikasi-an heap, dapat menggunakan Priority Queue dengan:
1. Selection Algorithms
2. Dijkstra's Algorithm
3. Prim Algorithm
Dapat juga menggunakan Heap Sort dengan: An O(n.lg(n)) algotihm.
1. Selection Algorithms
2. Dijkstra's Algorithm
3. Prim Algorithm
Dapat juga menggunakan Heap Sort dengan: An O(n.lg(n)) algotihm.
5. Heap dengan Priority Queue
Implementasi heap efisien dengan priority queue struktur data.
1. find-min = mencari elemen/nilai terkecil dalam heap
2. insert = meng-insert/menambahkan elemen baru ke dalam heap
3. delete-min = menghapus elemen/nilai terkecil pada heap
delete-min disebut juga pop, sedangkan insert disebut juga push.
Implementasi heap efisien dengan priority queue struktur data.
1. find-min = mencari elemen/nilai terkecil dalam heap
2. insert = meng-insert/menambahkan elemen baru ke dalam heap
3. delete-min = menghapus elemen/nilai terkecil pada heap
delete-min disebut juga pop, sedangkan insert disebut juga push.
1. find-min = mencari elemen/nilai terkecil dalam heap
2. insert = meng-insert/menambahkan elemen baru ke dalam heap
3. delete-min = menghapus elemen/nilai terkecil pada heap
delete-min disebut juga pop, sedangkan insert disebut juga push.
6. Heap dengan Array
Heap biasanya diemplementasikan melalui array. Elemen-elemen heap dalam array disimpan berdasarkan index 1 sampai N dengan berurutan dari atas kebawah dan dari kiri ke kanan node pada tree. *Root disimpan dalam index 1 (index 0 dibiarkan kosong/tidak digunakan)
Contoh heap dengan array:
Setiap node pada array ini berhubungan dengan parent, anak/child kiri, dan anak/child kanan nya masing-masing
Jika index dari suatu node adalah x, maka:
- Parent(x) = x / 2
- Left-child(x) = 2 * x -->(anak kiri(x))
- Right-child(x) = 2 * x + 1 --> (anak kanan(x))
#rumus inilah yang menjadi alasan index pada heap array dimulai dari 1
Heap biasanya diemplementasikan melalui array. Elemen-elemen heap dalam array disimpan berdasarkan index 1 sampai N dengan berurutan dari atas kebawah dan dari kiri ke kanan node pada tree. *Root disimpan dalam index 1 (index 0 dibiarkan kosong/tidak digunakan)
Contoh heap dengan array:
Setiap node pada array ini berhubungan dengan parent, anak/child kiri, dan anak/child kanan nya masing-masing
Jika index dari suatu node adalah x, maka:
Jika index dari suatu node adalah x, maka:
- Parent(x) = x / 2
- Left-child(x) = 2 * x -->(anak kiri(x))
- Right-child(x) = 2 * x + 1 --> (anak kanan(x))
#rumus inilah yang menjadi alasan index pada heap array dimulai dari 1
7. Pengaplikasi-an Heap
Heap biasanya sering digunakan untuk:
- Sorting dengan heap
- Algoritma selection
- Algoritma Graph
Heap biasanya sering digunakan untuk:
- Sorting dengan heap
- Algoritma selection
- Algoritma Graph
8. Tries
Tries atau prefix tree adalah sebuah tree yang tersusun/berurutan pada struktur data yang digunakan untuk menyimpan kumpulan array (biasanya berupa string).
TRIES berasal dari kata RETRIEVAL, karena tries dapan menemukan sebuat kata dalam kamis dengan hanya dengan menggunakan kata depan dari kata tersebut.
Tries atau prefix tree adalah sebuah tree yang tersusun/berurutan pada struktur data yang digunakan untuk menyimpan kumpulan array (biasanya berupa string).
TRIES berasal dari kata RETRIEVAL, karena tries dapan menemukan sebuat kata dalam kamis dengan hanya dengan menggunakan kata depan dari kata tersebut.
9. Pengaplikasi-an Tries
Contohnya adalah ketika sebuat web browser dapat otomatis menyelesaikan kata yang kita tulis (auto-complete) atau dengan menunjukkan pada pengguna banyaknya kemungkinan-kemungkinan dari teks yang akan ditulis. Contoh lainnya adalah spell-checker dalam mengecek kata yang ada dalam kamus apakah sudah sesuai apa belum.
Contohnya adalah ketika sebuat web browser dapat otomatis menyelesaikan kata yang kita tulis (auto-complete) atau dengan menunjukkan pada pengguna banyaknya kemungkinan-kemungkinan dari teks yang akan ditulis. Contoh lainnya adalah spell-checker dalam mengecek kata yang ada dalam kamus apakah sudah sesuai apa belum.
10. Tree of Tries
Setiap vertex menyimpan sebuah kata atau kata depan.
Root dalam Tries menyimpan sebuah kata kosong ('").
Contoh Tries yang menyimpan/mengandung kata:
- ALGO
- API
- BOM
- BOX
- BOSAN
- BOR
Setiap vertex menyimpan sebuah kata atau kata depan.
Root dalam Tries menyimpan sebuah kata kosong ('").
Contoh Tries yang menyimpan/mengandung kata:
- ALGO
- API
- BOM
- BOX
- BOSAN
- BOR
10. Struktur Tries
Kita dapat menggunakan struktur ini dalam mengimplementasi tree:
struct trie {
char chr;
int word;
struct trie* edge[128];
} *root = 0;
root = (struct trie*)malloc(sizeof(struct trie));
root->chr = ‘’;
root->word = 0;
note: chr is the character stored in that node.
word is 1 if there is a word ends at this node, 0 otherwise.
Kita dapat menggunakan struktur ini dalam mengimplementasi tree:
struct trie {
char chr;
int word;
struct trie* edge[128];
} *root = 0;
root = (struct trie*)malloc(sizeof(struct trie));
root->chr = ‘’;
root->word = 0;
note: chr is the character stored in that node.
word is 1 if there is a word ends at this node, 0 otherwise.
10. Insertion dalam Tries
Untuk menambahkan/memasukkan sebuah kata pada tries, kita dapat menggunakan kode:
void insert(struct trie *curr, char *p) {
if ( curr->edge[*p] == 0 )
curr->edge[*p] = newnode(*p);
if ( *p == 0 ) curr->word = 1;
else insert(curr->edge[*p],p+1);
}
newnode() function
struct trie* newnode(char x) {
struct trie* node =
(struct trie*)malloc(sizeof(struct trie));
node->chr = x;
node->word = 0;
for (i = 0; i < 128; i++ )
node->edge[i] = 0;
return node;
}
Untuk menambahkan/memasukkan sebuah kata pada tries, kita dapat menggunakan kode:
void insert(struct trie *curr, char *p) {
if ( curr->edge[*p] == 0 )
curr->edge[*p] = newnode(*p);
if ( *p == 0 ) curr->word = 1;
else insert(curr->edge[*p],p+1);
else insert(curr->edge[*p],p+1);
}
newnode() function
struct trie* newnode(char x) {
struct trie* node =
(struct trie*)malloc(sizeof(struct trie));
node->chr = x;
node->word = 0;
for (i = 0; i < 128; i++ )
node->edge[i] = 0;
return node;
}
11. Finding dalam Tries dengan Prefix
Untuk mencari sebuah kata lengkap jika kita memiliki sebuat kata awal dari kata tersebut, kita dapat menggunakan kode:
contoh mencari kata dengan awalan okay:
char s[100] = {“...”}; // global
int i, n, okay;
struct trie *curr;
n = strlen(s);
okay = 1;
curr = root;
for ( i = 0; i < n && okay == 1; i++ )
if ( curr->edge[s[i]] == 0 ) okay = 0;
else curr = curr->edge[s[i]];
if ( okay ) find(curr,n);
mengeprint semua kata lengkap yang memiliki awalan okay, dengan code :
void find(struct trie *curr, int x) {
if ( curr->word == 1 ) {
s[x] = 0;
puts( s );
}
for ( i = 0; i < 128; i++ )
if ( curr->edge[i] != 0 ) {
s[x] = i;
find(curr->edge[i],x+1);
}
}
Untuk mencari sebuah kata lengkap jika kita memiliki sebuat kata awal dari kata tersebut, kita dapat menggunakan kode:
contoh mencari kata dengan awalan okay:
char s[100] = {“...”}; // global
int i, n, okay;
struct trie *curr;
n = strlen(s);
okay = 1;
curr = root;
for ( i = 0; i < n && okay == 1; i++ )
if ( curr->edge[s[i]] == 0 ) okay = 0;
else curr = curr->edge[s[i]];
if ( okay ) find(curr,n);
mengeprint semua kata lengkap yang memiliki awalan okay, dengan code :
void find(struct trie *curr, int x) {
if ( curr->word == 1 ) {
s[x] = 0;
puts( s );
}
for ( i = 0; i < 128; i++ )
if ( curr->edge[i] != 0 ) {
s[x] = i;
find(curr->edge[i],x+1);
}
}
------------------------------------------------------
------------------------------------------------------
AVL TREE
------------------------------------------------------
------------------------------------------------------
1. AVL Tree
AVL Tree atau disebut juga dengan Balance Binary Search Tree (BST) merupakan binary search tree (BST) yang perbedaan tinggi/level dari subtree kiri dan subtree kanan tidak lebih dari 1 node sehingga dapat dikatakan balance.
gambar AVL Tree
AVL Tree atau disebut juga dengan Balance Binary Search Tree (BST) merupakan binary search tree (BST) yang perbedaan tinggi/level dari subtree kiri dan subtree kanan tidak lebih dari 1 node sehingga dapat dikatakan balance.
gambar AVL Tree
2. Kegunaan AVL Tree
Kegunaan AVL Tree adalah untuk memudahkan pencarian data atau operasi dalam Binary Search Tree sehingga mempercepat dan memperingan kerja program.
Kegunaan AVL Tree adalah untuk memudahkan pencarian data atau operasi dalam Binary Search Tree sehingga mempercepat dan memperingan kerja program.
3. Single Rotation
Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut.
T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar diatas.
Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut.
T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar diatas.
T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar diatas.
4. Double Rotation
Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut.
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 subtree T2 atau T3. Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar diatas.
Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut.
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 subtree T2 atau T3. Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar diatas.
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 subtree T2 atau T3. Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) gambar diatas.
5. Operasi Insertion
Secara umum, operasi insertion pada AVL sama seperti insertion pada BST. Namun pada AVL Tree, 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
Contoh – Single Rotation: Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root
Contoh – Double Rotation : Jika terdapat sebuah tree yang kemudian dilakukan insertnode 26. Maka akan terjadi ketidak seimbangan, sehingga terlihat dari bentuknya dapat diselesaikan dengan kasus 4.
Secara umum, operasi insertion pada AVL sama seperti insertion pada BST. Namun pada AVL Tree, 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)
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
Contoh – Single Rotation: Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root
Contoh – Double Rotation : Jika terdapat sebuah tree yang kemudian dilakukan insertnode 26. Maka akan terjadi ketidak seimbangan, sehingga terlihat dari bentuknya dapat diselesaikan dengan kasus 4.
6. Operasi Deletion
Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :
–Kasus 1: Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
- Kasus 2: Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
- 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)
Berikut contoh dalam menghapus node AVL Tree, terdapat AVL Tree yang kemudian di hapus node 60. Dengan gambaran sebagai berikut :
Yang akan menggantikan posisi node 60 adalah node 55. Akan terjadi ketidak seimbangan. Dengan tampilan sebagai berikut :
Maka akan dilakukan single rotation pada node 55 dengan kasus ketidak seimbangan pada kasus no. 2. Dengan tampilan setelah dilakukan single rotation sebagai berikut :
Ketika sudah dilakukan single rotation dan dilakukan kembali perbedaan tinggi / level maksimal 1 ternyata terdapat ketidak seimbangan yang terjadi. Sehingga diperlukan double rotation dengan kasus no. 4. Sehingga hasil dari rotasi yang dilakukan adalah sebagai berikut :
-------------------------------------------------------------------------------------------------------------
Referensi:
- Power Point Linked List I
- Power Point Linked List II
- http://suciantinovi.blogspot.com/2014/03/linked-list-i_14.html
- http://apriliyatiwen.blogspot.com/2013/04/linked-list.html
- http://rizkiyantikolono.blogspot.com/p/1-penjelasan-dari-linked-list-linked.html
- https://www.mahirkoding.com/struktur-data-single-linked-list-dengan-bahasa-c/
- Power Point Stack and Queue
- https://medium.com/easyread/memahami-konsep-stack-secara-sederhana-bd4409ec560c
- https://brainly.co.id/tugas/16131099
- https://www.mahirkoding.com/struktur-data-stack-dan-implementasinya/
- Power Point Hashing and Hash Table, Trees & Binary Tree(L)
- https://www.codepolitan.com/apa-itu-encoding-obfuscation-hashing-dan-encryption-58bfb7eee3215
- https://sis.binus.ac.id/2019/05/22/apa-itu-blockchain/
- https://selembardigital.com/apa-itu-hashing-di-bawah-tudung-blockchain/
- Power Point Binary Search Tree
- https://en.wikipedia.org/wiki/Binary_search_tree
- Power Point Heap and Tries (L)
- Power Point AVL Tree
- https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
- https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/
- https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/
- http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html
-------------------------------------------------------------------------------------------------------------
Berikut adalah tugas mingguan membuat blog berisi rangkuman materi yang telah saya pelajari selama dalam semester ini.
Sekian,
---Terima kasih.---
Nama: Felina Suryadi
NIM: 2301914604
Kelas Besar: CB01
-------------------------------------------------------------------------------------------------------------
Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :
–Kasus 1: Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
- Kasus 2: Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
–Kasus 1: Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
- Kasus 2: Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
- 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)
Berikut contoh dalam menghapus node AVL Tree, terdapat AVL Tree yang kemudian di hapus node 60. Dengan gambaran sebagai berikut :
Yang akan menggantikan posisi node 60 adalah node 55. Akan terjadi ketidak seimbangan. Dengan tampilan sebagai berikut :
Maka akan dilakukan single rotation pada node 55 dengan kasus ketidak seimbangan pada kasus no. 2. Dengan tampilan setelah dilakukan single rotation sebagai berikut :
Ketika sudah dilakukan single rotation dan dilakukan kembali perbedaan tinggi / level maksimal 1 ternyata terdapat ketidak seimbangan yang terjadi. Sehingga diperlukan double rotation dengan kasus no. 4. Sehingga hasil dari rotasi yang dilakukan adalah sebagai berikut :
-------------------------------------------------------------------------------------------------------------
Referensi:
- Power Point Linked List I
- Power Point Linked List II
- http://suciantinovi.blogspot.com/2014/03/linked-list-i_14.html
- http://apriliyatiwen.blogspot.com/2013/04/linked-list.html
- http://rizkiyantikolono.blogspot.com/p/1-penjelasan-dari-linked-list-linked.html
- https://www.mahirkoding.com/struktur-data-single-linked-list-dengan-bahasa-c/
- Power Point Stack and Queue
- https://medium.com/easyread/memahami-konsep-stack-secara-sederhana-bd4409ec560c
- https://brainly.co.id/tugas/16131099
- https://www.mahirkoding.com/struktur-data-stack-dan-implementasinya/
- Power Point Hashing and Hash Table, Trees & Binary Tree(L)
- https://www.codepolitan.com/apa-itu-encoding-obfuscation-hashing-dan-encryption-58bfb7eee3215
- https://sis.binus.ac.id/2019/05/22/apa-itu-blockchain/
- https://selembardigital.com/apa-itu-hashing-di-bawah-tudung-blockchain/
- Power Point Binary Search Tree
- https://en.wikipedia.org/wiki/Binary_search_tree
- Power Point Heap and Tries (L)
- Power Point AVL Tree
- https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
- https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/
- https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/
- http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html
-------------------------------------------------------------------------------------------------------------
Berikut adalah tugas mingguan membuat blog berisi rangkuman materi yang telah saya pelajari selama dalam semester ini.
Sekian,
Sekian,
---Terima kasih.---
Nama: Felina Suryadi
NIM: 2301914604
Kelas Besar: CB01
-------------------------------------------------------------------------------------------------------------
