Binary Search Tree

Binary Search Tree atau biasa disingkat BST adalah sebuah data struktur yang berbentuk atau diilustrasikan merupai sebuah pohon,sesuai namanya Binary Search Tree. Prinsip dari Binary Search Tree ini, adalah ketika data baru yang masuk , dicek dlu apakah dia lebih kecil atau lebih besar dari root nya atau akarnya(sebagai acuan) jikalau lebih kecil akan di masukkanke bagian kiri rootnya , jika lebih besar akan dimasukkan sebelah kanan rootnya, dan seterusnya tanpa batas. Jadi kita bisa menambahkan data sebanyak apa pun tanpa batas, karena setiap data itu dihubungkan dengan pointer sama seperti Array dinamis. Dan juga setiap cabang hanya boleh memiliki 2 anak , 1 dikiri yang lebih kecil dari root atau bapaknya, 1 lagi yang dikanan lebih besar dari root atau bapaknya.

contoh binary search tree :

Keuntungan kita memakai binary search tree untuk menyusun data kita adalah, ketika kita mau mencari data , algoritmanya yaitu jika kita mau mencari sebuah angka x, kita cek dulu si x ini apakah lebih besar dari root atau tidak, jika lebih besar maka dia cek lg kekanan , jika lebih kecil maka cek ke kiri lagi , jika uda sama dengan brarti uda dapat xnya , dan seterusnya dicari sampai datanya habis atau data nya ditemukan.
Jadi dengan binary search tree kita bisa mempercepat pencarian karena kita tidak cek 1 1 lagi melainkan mengeliminasi bebrapa proses yang menyebabkan pencarian jadi lama.

selain untuk mencari data, secara tidak langsung jika kita memakai binary search tree, kita sudah mensort data2 kita.

sekian,terima kasih.

Hash Table & Binary Tree

Hash table

Hash table adalah cara dalam memproses data biasanya dilakukan dengan mengenerate key terlebih dahulu lalu key tersebut dijadikan sebagai index yang nanti data tersebut akan dimasukkan ke array dengan index sesuai yang kia dapat tadi.

Tapi karena ada kemungkinan kalo misalnya setelah kita generate index, kita mendapat kan index yang sudah pernah kita pakai sebelumnya, maka akan terjadi tubrukan data, sehingga jika kita tetap masukkan data baru ke index tersebut, data sebelumnya yang ada pada index yang sama akan teroverwrite, sehingga akan hilang.

Jadi untuk mengatasi hal tersebut terjadi, ada namanya linear probing dan chaining :
1. Linear probing
Cara ini dilakukan pada saat menemukan index yang sama, kita mencari index setelahnya yang masih belum terpakai(kosong), dengan looping, kita tambah-tambah index nya dengan 1 sambil mengecek apakah isi dari array pada index tersebut sudah terisi apa kosong, jika kosong maka masukkan data ke index tersebut, kalao udah terisi maka lanjut looping dan tambah-tambah 1 lagi hingga menemukan yang kosong.

2.Chaining
Cara ini dilakukan pada saat menemukan index yang sama setelah itu menjadikan setiap array dalam hash table menjadi dynamic array, sehingga data yang pertama masuk menjadi headnya setelah itu jika ada data yang masuk lagi akan menjadi nextnya, dan seterusnya tanpa ada batas

Binary Tree

Binary Tree adalah sebuah tipe struktur data yang bentuknya mrip pohon, berbeda dengan linked list mnggunakan head sebagai acuan, binary tree ini menggunakan root sebagai acuannya, dan ada left dan right, biasa nya left adalah data dengan value yang lebih kecil dari rootnya, sedangkan yang right memiliki value yang lebih besar dari rootnya, sehingga nanti ini akan sangat membantu dalam pencarian data, dan sorting data.

Single Linked List
adalah sekumpulan node yang terhubung melalui pointer. Single linked list hanya memiliki pointer yang menunjuk ke node selanjutnya tapi tidak ad pointer yang menunjuk ke node sebelumnya

Dalam memasukkan data baru pada linked list terdapat 2 cara :
1. Stack
yaitu data yang terakhir kita masukkin, itu yang bakal jadi yang pertama(LIFO Last In First Out)
atau biasa di linked list di sebut PushHead

2.Queue
yaitu data yang terakhir kita masukkin, itu yang bakal jadi yang terakhir juga (FIFO First In First Out) atau biasa di linked list di sebut PushTail

Untuk detail yang lebih jelas bisa diklik aja link berikut :
https://www.geeksforgeeks.org/data-structures/linked-list/singly-linked-list/


Terima kasih