Binary Search Tree

BINARY SEARCH TREE (BST)

PENGERTIAN

Binary Search Tree adalah sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node. Selain itu, terdapat juga aturan dimana anak kiri dari parent selalu memiliki nilai lebih kecil dari nilai parent dan anak kanan selalu memiliki nilai lebih besar dari parent.

Operasi dasar pada Binary Search Tree :

1.  Find(x) : menemukan value x didalam BST (Search)
2.  Insert(x) : memasukan value baru x ke BST (Push)
3.  Remove(x) : menghapus key x dari BST (Delete)

Ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada Binary Search Tree :

• PreOrder : Print data, telusur ke kiri, telusur ke kanan
• InOrder : Telusur ke kiri, print data, telusur ke kanan
• Post Order : Telusur ke kiri, telusur ke kanan, print data

Operasi : Search

Misalkan mencari value x

•  Memulai pencarian dari Root
•  Jika Root adalah value yang dicari, maka berhenti
•  Jika x lebih kecil dari Root, maka cari ke dalam rekursif tree sebelah kiri
•  Jika x lebih besar dari Root, maka cari ke dalam rekursif tree sebelah kanan

Operasi : Insertion

Memasukan value (data) baru kedalam BST dengan rekrusif

Misalkan menginsert value x

• Dimulai dari Root
• Jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang (rekrusif)
• Jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang (rekrusif)
• Ulangi sampai menemukan node yang kosong untuk memasukan value x (x akan selalu berada dipaling bawah biasa disebut Leaf atau daun)

Contoh Insertion :

Operasi : Delete (Remove)

• Jika value yang ingin dihapus adalah Leaf (daun) atau paling bawah, langsung delete
• Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
• Jika value yang akan di hapus adalah node yang memiliki 2 anak, maka ada 2 cara, kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf)(kiri,kanan) atau dengan cari dari right sub tree anak kiri paling terakhir (leaf)(kanan,kiri)

Referensi :

https://socs.binus.ac.id/2017/05/10/implementasi-insert-pada-binary-search-tree-dengan-single-dan-double-pointer/

https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/

https://abdilahrf.github.io/2015/06/pengenalan-binary-search-tree/

Dibuat oleh :

Livia Leonita

2301905726

CB01

Hash Table & Tree

HASH TABLE

I. Pengertian

Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. 

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan). 

Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

II. Operasi pada Hash Table

• insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
• find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
• remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
• getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

III. Struktur dan Fungsi pada Hash Table

Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.

Cara untuk mendapatkan field kunci ini sangatlah beragam, namun hasil akhirnya adalah sebuah bilangan hash yang digunakan untuk menentukan lokasi record. Bilangan hash ini dimasukan ke dalam hash function dan menghasilkan indeks lokasi record dalam tabel.

            k(x) = fungsi pembangkit field kunci (1)

            h(x) = hash function (2)

Hashing Table pada Blockchain

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.

Stack & Queue CB01

Stack & Queue


I. Pengertian Stack

Stack atau tumpukan dapat diartikan sebagai suatu kumpulan data yang seolah-olah terlihat seperti ada data yang diletakkan di atas data yang lain. Kaidah utama dalam konsep stack adalah LIFO yang merupakan singkatan dari Last In First Out, artinya adalah data yang terakhir kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.

Sebuah struktur data dari sebuah stack setidaknya harus mengandung dua buah variabel, misalnya variabel top yang akan berguna sebagai penanda bagian atas tumpukan dan array data dari yang akan menyimpan data-data yang dimasukkan ke dalam stack tersebut.

II. Operasi-operasi Dasar Stack

• Operasi push, berfungsi untuk memasukkan sebuah nilai atau data ke dalam stack. Sebelum sebuah nilai atau data dimasukkan ke dalam stack, prosedur ini terlebih dahulu akan menaikkan posisi top satu level ke atas. Berikut ilustrasi kerja pada operasi push :

• Operasi pop, berfungsi untuk mengeluarkan atau menghapus nilai terakhir (yang berada pada posisi paling atas) dari stack, dengan cara menurunkan nilai top satu level ke bawah. Berikut ilustrasi kerja pada operasi pop :

• CREATE(S), berfungsi untuk membuat sebuah stack kosong(menjadi hampa) dan didefinisikan bahwa; 
  NOEL (CREATE(S)) = 0 dan TOP (CREATE(S)) = null/tidak terdefinisi

• ISEMPTY(S), berfungsi untuk menentukan apakah suatu stack adalah stack kosong(hampa) atau tidak. Operasinya akan bernilai boolean dengan definisi sebagai berikut : 
• ISEMPTY(S) = true, jika S adalah stack kosong atau NOEL(S) = 0
• False, jika S bukan stack kosong atau NOEL(S)  0
  Catatan : ISEMPTY(CREATE(S)) = true
  

III. PENGERTIAN QUEUE

Queue atau antrian merupakan struktur data linear dimana penambahan komponen dilakukan disatu ujung, sementara pengurangan dilakukan diujung lain. Kaidah utama dalam konsep queue adalah FIFO yang merupakan singkatan dari First In First Out, artinya adalah data yang pertama kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.

Sebuah queue di dalam program komputer dideklarasikan sebagai sebuah tipe bentukan baru. Sebuah struktur data dari sebuah queue setidaknya harus mengandung dua tiga variabel, yakni variabel head yang akan berguna sebagai penanda bagian depan antrian, variabeltail yang akan berguna sebagai penanda bagian belakang antrian danarray dari yang akan menyimpan data-data yang dimasukkan ke dalam queue tersebut.

IV. Operasi-operasi Dasar Queue

• Operasi Enqueue

Operasi push pada antrian disebut juga enqueue. Operasi ini digunakan untuk menambah sebuah elemen baru. Elemen baru akan dimasukkan ke belakang antrian. Algoritma operasi push pada queue adalah sebagai berikut:

• Menentukan kondisi antrian, apakah antrian dalam keadaan kosong atau tidak.
• Jika kosong maka mendeklarasikan data baru yang akan dimasukkan ke dalam antrian.
• Memasukkan nilai data yang baru.
• Melakukan perulangan untuk memasukkan data hingga batas penuh antrian dengan cara menempatkan penunjuk front menunjuk ke elemen terdepan (head) pada antrian dan rear menunjuk ke elemen baru yang ditambahkan dan nilai count bertambah satu .
• Jika antrian sudah penuh maka selesai.
• Operasi Dequeue

Operasi pop pada antrian disebut juga dequeue. Operasi ini digunakan untuk menghapus elemen pada antrian. Elemen yang akan dihapus adalah elemen yang terletak paling depan pada antrian. Algoritma operasi pop pada queue adalah sebagai berikut:

• Melakukan pengecekan kondisi antrian, ada isi data atau tidak.
• Jika terdapat data pada antrian, maka lakukan penghapusan data dengan cara memindahkan head (elemen terdepan antrian) ke elemen setelahnya atau membuat penunjuk front menunjuk ke elemen setelah elemen terdepan pada queue.
• Kemudian menghapus elemen terdepan antrian dan nilai count antrian berkurang satu.
• Jika tidak terdapat data pada antrian maka selesai.

Referensi : 

http://tutetutetute.blogspot.com/2010/02/operasi-dasar-stack.html
https://bocahngoding.blogspot.com/2018/01/pengertian-stack-dan-queue-dalam.html

Dibuat oleh:

Livia Leonita

CB01-2301905726