Binary Search Tree(BST)

Kali ini , kita belajar Binary Search Tree / BST. Kita pertama - tama akan membahas struktur dasar Tree terlebih dahulu . Tree (pohon) adalah salah satu bentuk struktur ata yang menggambarkan hubungan hierarki antar elemen-elemennya(seperti relasi one to many).

Nah... Binary Tree atau pohon biner adalah suatu tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree terhebut harus terpisah. Tiap node dalam binary tree boleh memiliki paling banyak 2 child / anak simpul (anak kiri ,anak kanan). Dan saat Menginsert nya dia masih belum tersusun rapi.

Binary Search Tree adalah tree yang terurut (ordered Binary Tree) / Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang di simpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah sebagai patokannya. Binary Tree terdiri dari 1. simpul utama yang disebut dengan istilah root, dan setiap root mempunyai 2 child. 

2. 2 child yang memiliki 1 root yang sama di sebut Sibling , 

3. suatu root yang tidak memiliki child sama sekali di sebut leaf

Data yang tersusun dalam struktur data BST juga dapat dicari dengan mudah dan memiliki rata- rata kompleksitas sebesar O(log n),namun membutuhkan waktu sebesar O(n) pada kondisi terjelek dimana BST tidak berimbang dan membentuk seperti linked list.

2 aturan yang harus di penuhi pada saat data di atur dalam BST :

1. Semua data di bagian kiri sub-tree dari node  selalu lebih kecil dari data dalam node t itu

2. semua data dibagian kanan sub-tree dari node  selalu lebih besar atau sama dengan data dalam node 

Operasi BST : 

-Insertion 

1. Dimulai dari root 

2. Jika x lebih kecil dari key kemudian cek dengan sub-tree sebelah kiri , lakukan pengecekan secara rekursif.

3. Jika x lebih besar dari key kemudian cek dengan sub-tree sebelah kanan ,lakukan pengecekan secara rekursif.

4. Ulangi sampai menemukan node yang kosong untuk memasukkan value 

-Delete

1. Jika value yang ingin dihapus adalah leaf , langsung delete saja

2. Jika value yang akan dihapus mempunyai satu child , hapus nodenya dan gabungkan childnya ke parent value yang dihapus.

3. Jika value yang akan di hapus adalah noode yang mempunyai 2 child , maka cari dari left sub-tree ,kemudian bandingan dengan yang kanan .

Hashing  and Hash Table , Trees and Binary Tree

Tugas Utama dari Hashing adalah untuk memastikan integritas(keutuhan).Contohnya kita mempunyai sebuah file . Dengan di-Hashing kita akan mendapatkan nilai tertentu sebagai bagian integritas file tersebut.Apabila file itu dirubah, maka nilainya tidak akan sama lagi dengan Hashing pertama.

Nah.. kan udah pada tau kira - kira hashing itu apa , Sekarang Apa sih itu Hash Table?

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

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat.
Operasi pada Hash Table :
1. Insert -> diberikan sebuah key dan nilai , insert nilai dalam tabel
2. Find -> diberikan sebuah key,temukan nilai yang berhubungan dengan key
3. Remove -> diberikan sebuah key, temukan nilai yang berhubungan dengan key , kemudian hapus nilai tersebut.
4. getIterator -> mengembalikan iterator , yang memeriksa nilai satu demi satu.

Tahap Tahap Membuat Hash Table : 

1. Inisialisasi
2. Menambah Element Baru
3. Menghapus Sebuah element
4. Searching , teknik pencarian pada hash table yaitu mencari nilai hash yang sesuai menggunakan deklarasi sama seperti pada linked list. Jika data tidak
 ditemukan maka menggunakan return NULL .
5. Resizing , Jumlah element pada hash table tidak selalu diketahui ketika terjadi penambahan data.

Collision / Tabrakan

Keterbatasan tabel hash menyebabkan ada dua angka yang jika dimasukkan ke dalam fungsi hash maka menghasilkan nilai yang sama . Hal ini disebut dengan collision
contoh : kita memasukkan angka 6 dan 29
Hash(6) = 6 % 23 = 6;
Hash(29) = 29 %23 =6;

Cara mengatasi Collision / Collision Resolution :
1. Open Addressing (Linear Probing,Quadratic Probing,Double Hashing)
2. Chaining

Biasanya dalam Hash Table kita sering memakai Linear Probing / Chaining,
Contoh pada Linear Probing , Saat kita memiliki String yang sama seperti "bima" dan "bima"
dia akan mengeluarkan output seperti ini
(index).bima
(index).bima
Sedangkan Chaining , ia menggunakan konsep seperti linked List
(index).bima->bima

Tree dan Binary Tree

Binary Tree atau pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa di definisikan sebagai kumpulan simpul dengan setiap simpul yang mempunyai paling banyak dua anak (anak kanan , anak kiri).

Operasi dalam Binary Tree -> Create , Clear , Find , Update , Delete

Binary Search Tree adalah Tree yang terurut (Ordered Binary Tree). Binary Serach Tree juga sering di sebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam meory . 

Aturan dalam BST :
1. Semua data di bagian kiri sub tree  dari root selalu lebih kecil dari root itu sendiri
2. Semua data di bagian kanan sub tree dari root selalu lebih besar dari root itu sendiri










https://www.codepolitan.com/apa-itu-encoding-obfuscation-hashing-dan-encryption-58bfb7eee3215
https://sourcecodegeneration.blogspot.com/2018/08/pengertian-binary-tree-binary-search.html