Binary Search Tree

--- TUGAS BLOG ALGO-BINUS Mingguan ---

  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.

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:

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

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.

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)

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)

-------------------------------------------------------------------------------------------------------------

Referensi:

• Power Point Binary Search Tree
• https://en.wikipedia.org/wiki/Binary_search_tree

-------------------------------------------------------------------------------------------------------------

Berikut adalah tugas mingguan membuat blog berisi rangkuman materi Binary Search Tree yang telah saya pelajari.
Sekian,

---Terima kasih.---

   Nama: Felina Suryadi                  

   NIM: 2301914604                        

   Kelas Besar: CB01                        

-------------------------------------------------------------------------------------------------------------

Hashing table & Binary Tree

--- TUGAS BLOG ALGO-BINUS Mingguan ---

  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.

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.

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

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.

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

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.

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.

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.

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.

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.

J. Kesimpulan

Hashing merupakan salah satu dasar dalam penciptaan teknologi blockchain.

-------------------------------------------------------------------------------------------------------------

Referensi:

• 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/

-------------------------------------------------------------------------------------------------------------

Berikut adalah tugas mingguan membuat blog berisi rangkuman materi Hashing Table dan Binary Tree yang telah saya pelajari.
Sekian,

---Terima kasih.---

   Nama: Felina Suryadi                  

   NIM: 2301914604                        

   Kelas Besar: CB01                        

-------------------------------------------------------------------------------------------------------------

STACK & QUEUE

--- TUGAS BLOG ALGO-BINUS Mingguan ---

  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.

B. Penggunaan Stack

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.

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().

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.

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().

...

-------------------------------------------------------------------------------------------------------------

Referensi:

• 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/

-------------------------------------------------------------------------------------------------------------

Berikut adalah tugas mingguan membuat blog berisi rangkuman materi Stack and Queue yang telah saya pelajari.
Sekian,

---Terima kasih.---

   Nama: Felina Suryadi                  

   NIM: 2301914604                        

   Kelas Besar: CB01                        

-------------------------------------------------------------------------------------------------------------