Binary Search Tree

Binary Search Tree

Dalam it ,binary search tree atau biasanya juga disebut ordered/sorted binary trees adalah sebuah data structure yang menyimpan item didalam memory yang disusun dalam bentuk seperti akar pohon dan setiap cabang akar memiliki paling maksimal 2 buah cabang.

Diatas adalah gambar binary tree yang benar,selain berbentuk seperti akar dan memiliki cabang paling maksimal 2,binary search tree juga memiliki syarat lain yaitu data yang lebih besar ditaruh dicabang sebelah kanan dan data yang memiliki nilai lebih kecil ditaruh di cabang sebelah kiri.cara ini memungkikan pencarian data yang lebih cepat karena data sudah diatur sedemikian rupa dan computer akan memulai pencarian daric aba terbawah sebelah kiri.

1.searching

Langkah-langkah:

1.mulai dari root.

Root merupakan bagian teratas dari binary search tree,jadi kita mempunyai 1 variabel yang akan bergerak,kita taruh variable itu di root.

2.bandingkan nilai yang dicari kepada node,jika nilai yang dicari lebih besar maka akan ke kanan jika lebih nilai yang dicari lebih kecil maka ke kiri cara ini dilakukan secara recursif.

3.jika nilai yang dicari sudah sama dengan nilai node maka return true.

2.insertion

Langkah-langkah:

            1.mulai dari root

2.bandingkan ke node jika lebih besar maka ke sebelah kanan ,jika lebih kecil maka akan kekiri jika ketika pindah belum ada nilainya maka proses berhenti dan nilai nya di taruh di memory itu.

Hash table

Dalam pemograman,hash table adalah sebuah data structure yang meng-inplementasikan sebuah “associative array abstract data type”, sebuah structure yang dapat memetakan kata kunci menjadi value .hash table menggunakan fungsi hash untuk mendapatkan sebuah index yang juga disebut hash code ,ke array of buckets atau slots yang dimana value yang dicari bisa ditemukan.

Hashing adalah sebuah Teknik yang mengubah vlue value  menjadi sebuah Panjang dari index of array .kita akan mengmodulokan untuk mendapatkan range of key values .anggap contoh dari hash table dengan besar 20 dan item item berkut disimpan item didalam (key,value) format.

• (1,20)
• (2,70)
• (42,80)
• (4,25)
• (12,44)
• (14,32)
• (17,11)
• (13,78)
• (37,98)

Sr.No.	Key	Hash	Array Index
1	1	1 % 20 = 1	1
2	2	2 % 20 = 2	2
3	42	42 % 20 = 2	2
4	4	4 % 20 = 4	4
5	12	12 % 20 = 12	12
6	14	14 % 20 = 14	14
7	17	17 % 20 = 17	17
8	13	13 % 20 = 13	13
9	37	37 % 20 = 17	17

Linear probing

Seperti yang kita lihat,kadang kadang hashing Teknik digunakan untuk membuat index of array yang sudah digunakan.dala kasus itu kita bisa mencari lokasi kosong sselanjutnya sampai menemukan tempat kosong .teknik ini dinamakan linear probing.

Sr.No.	Key	Hash	Array Index	After Linear Probing, Array Index
1	1	1 % 20 = 1	1	1
2	2	2 % 20 = 2	2	2
3	42	42 % 20 = 2	2	3
4	4	4 % 20 = 4	4	4
5	12	12 % 20 = 12	12	12
6	14	14 % 20 = 14	14	14
7	17	17 % 20 = 17	17	17
8	13	13 % 20 = 13	13	13
9	37	37 % 20 = 17	17	18

Secara sederhana,hashing berarti mengubah string dengan Panjang berapa pun dan mengoutputnya dengan output yang punya Panjang sama. Salah satu Cryptocurrency,bitcoin transaksi yang terjadi diambil sebagai input dan algoritma hashing berjalan(bitcoin menggunakan SHA-256) yang memberikan output dangan Panjang tetap.

Dalam pemograman ,binary tree adalah data struktur pohon dimana setiap nodenya mempunyai paling banyak dua anak atau cabang,dimana dinamakan left child dan right child. Binary tree node mempunyai bagian bagian berikut:

1.     Data

2.     Pointer to left child

3.     Pointer to right child