AVL Tree & B-Tree

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

• Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
• Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
• Root memiliki anak minimal 2, selama root bukan leaf
• Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
• Data yang tersimpan pada node harus terurut secara inorder
• Semua leaf berada pada level yang sama, level terbawah

Summary

Binary Search Tree

1. Setiap node mempunyai value dan tidak ada value yang double.
2. Value yang ada di kiri tree lebih kecil dari rootnya.
3. Value yang ada di kanan tree lebih besar dari rootnya.
4. kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child Jadi BST ini memiliki sifat (rekrusif).

• Operasi insert, pada binary search tree insert dilakukan setelah ditemukan lokasi yang tepat. (lokasi tidak ditemukan oleh user sendiri).
• Operasi search, pencarian dalam binary search tree untuk suatu nilai key dapat dilakukan secara recursive maupun dengan proses iterative.
• Operasi Delete, operasi delete diakukan terhadap node dengan 2 child, maka untuk menggantikannya, diambil node paling kiri dari right subtree

Hash Table & Binary Tree

Hashing Table

(Sumber : https://medium.com/dev-blogs/ds-with-js-hash-table-4715c94083d2)

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.

(Sumber: https://medium.com/dev-blogs/ds-with-js-hash-table-4715c94083d2)

Beberapa contoh bagaimana hashing metode ini digunakan dalam kehidupan sehari-hari misalnya di universitas, setiap mahasiswa pastiya diberi NIP atau nomor identifikasi yang digunakan sebagai informasi mengenai mereka. Atau contoh paling nyatanya juga pada perpustakaan, setiap buku akan diberi nomor unik sebagai informasi mengenai buku tersebut, seperti letak penyimpanan, sehingga pengunjung yang meminjam buku tersebut bisa mencari lewat database perpustakaan apakah buku dipinjam oleh orang lain atau masih tersedia diperpustakaan. Kelebihan dari hash table antara lain relatif lebih cepat dan memiliki kecepatan dalam insertions, deletions, maupun searching relatif sama.

Binary Tree

(Sumber: https://en.wikipedia.org/wiki/Binary_tree)

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.

Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan.

Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order.Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.

Implementasi Hash dalam Blockchain
Teknologi blockchain semakin berkembang dan dapat digunakan dalam  berbagai bidang kehidupan manusia. Salah  satu komponen penting  dalam blockchain adalah fungsi hash yang berguna untuk menjaga konsistensi data dalam blockchain, dan memastikan tidak ada  perubahan data yang terjadi. Penggunaan blockchain oleh banyak orang sekaligus menuntut penggunaan fungsi hash dengan performa yang handal.

Blok awal pada suatu blockchain disebut dengan blok genesis. Setiap blok memiliki nilai hash dari blok sebelumnya, waktu pembuatan blok, dan data. Desain blockchain tersebut membuatnya resisten terhadap pengubahan data, karena setiap perubahan pada suatu blok akan membuat blok selanjutnya menjadi tidak valid. Untuk menambah keamanan, blockchain disimpan dalam jaringan terdistribusi dengan protokol peer-to-peer tertentu.

(Sumber: Fadhil Imam Kurnia. Implementasi dan Perbandingan Blockchaindengan Algoritma Hash. 2018)

Stack & Queue

1. Push : Memasukkan data ke dalam stack.
2. Pop : Menghapus data di dalam stack.
3. Peek : Membaca nilai dari sebuah data, dilakukan berurutan dari awal stack tanpa menghilangkannya.

1. Push : Menambahkan data pada akhir antrian
2. Pop : Menghapus data dari awal antrian
3. Peek : Mengambil nilai dari sebuah data

Linked List (2)

Linked List

(Sumber: https://www.geeksforgeeks.org/data-structures/linked-list/)

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

Linked List dan Array

(Sumber: https://www.pinterest.se/pin/741757001101474327/)

Array
Variable bertipe array adalah suatu tipe data yang bersifat statis (urutan dan ukuran sudah pasti).
Kelemahan dari array statis adalah penggunaan ruang memori yang sudah digunakan tidak dapat dihapus apabila nama variable array tersebut sudah tidak digunakan kembali dalam suatu program (penyebab kemubaziran).
Untuk pemecahannya maka digunakan struktur data dinamis dengan menggunakan variable dinamis.
Variabel dinamis tidak dapat dideklarasikan  secara eksplisit seperti halnya variable statis dan tidak dapat ditunjuk oleh identifier secara langsung, tetapi dapat ditunjuk secara khusus oleh variable dinamis yaitu POINTER.

Linked List
-Struktur ini terdiri dari rangkaian elemen yang saling berhubungan / berkaitan, dimana setiap elemen dihubungkan dengan elemen lainnya oleh sebuah pointer.
-Pointer, sel yang nilainya merupakan alamat sel yang lain dimana sel yang lain itu dapat berupa data atau berupa pointer juga
-Setiap elemen dalam linked list selalu berisi pointer
Istilah – istilah
*Simpul, terdiri dari dua bagian :
  a.  Bagian/medan data (info)
  b.  Bagian/medan sambungan (pointer yang menunjuk kesimpul berikutnya)
*Awal (First), variable yang berisi alamat yang menunjuk lokasi simpul pertama linked list
*Nil / Null, Tidak bernilai yaitu menyatakan tidak mengacu kealamat manapun.
*Akhir, sebuah simpul yang menunjuk pada simpul terakhir

Operasi-operasi pada Linked List
a) Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
b) IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
c) Find First
Fungsi ini mencari elemen pertama dari linked list
d) Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
e) Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
f) Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu. 
g) Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
h) Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
i) Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.