Binary Search Tree

Binary Search Tree atau BST adalah salah satu Data Structure yang memiliki atribut yang sama dengan Binary Tree, namun memiliki susunan data yang lebih terstruktur, data yang masuk otomatis telah dimasukkan secara teratur, sebagai contoh:

Apabila ada data yang masuk dengan nilai lebih kecil daripada nilai root, maka data akan diletakkan dicabang kiri, jika ada data yang masuk lebih besar daripada nilai root, data akan diletakkan di sebelah kanan.

Ciri ciri Binary Search Tree:

1. Cabang bagian kiri memiliki nilai lebih kecil daripada root
2. Cabang bagian kanan memiliki nilai lebih besar daripada root
3. Setiap cabang hanya dapat memiliki 2 anak

Search

Search dalam BST pastinya lebih cepat terproses dibandingkan dengan Binary Tree biasa, untuk BST sehat, memiliki kompleksitas O (log n). Untuk algoritmanya, biasanya berdasarkan dengan nilai data. Apabila data yang dicari lebih kecil daripada root, maka root sekarang menjadi anak kiri dari root, begitu juga sebaliknya. ketika datanya ternyata sudah habis atau sudah ketemu, maka program search selesai,

Insert

Untuk insert seharusnya mirip dengan algoritma search, Insert diawali dengan root, kemudian dicek datanya, apakah lebih besar atau lebih kecil dari root, jika lebih kecil, root sekarang menjadi 

root->left, hal ini terus dilakukan sampai didapatkan cabang yang masih kosong (null). Begitu juga sebaliknya.

Deletion

Mirip seperti insert, root, kemudian dicek datanya, apakah lebih besar atau lebih kecil dari root, jika lebih kecil, root sekarang menjadi root->left, program selesai apabila datanya ditemukan ataupun menemukan cabang null.

Sumber :

https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/

https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

Hash Table and Binary Search Tree

Hash Table
Hashing adalah sebuah cara dalam memproses data (biasanya yang diproses adalah sebuah variabel "kunci" atau sebuah string) ke dalam suatu array. hal ini bertujuan untuk mempermudah dalam menyimpan atau mencari data. Biasanya, hasil hashing yang terlalu besar, akan dimodulo dengan ukuran maksimum dari Array tersebut agar tidak terjadi Index Out of Bound

Contoh Hashing data pada gambar adalah dengan me-modulus 10 dari setiap data yang ada, kemudian dimasukkan ke dalam Array yang sama dengan hasil modulusnya.


Contoh Contoh Hashing :
1. Mid Square
Ciri khas dari hashing ini adalah, data "kunci" (bisa berupa char ataupun integer. Jika char diambil ASCII), dipangkatkan, kemudian dicari angka bagian tengah dari hasil pangkat tersebut.
Misal : key = 75, arrayMax = 35;
            hasil pangkat = 5'62'5
            hasil hash = 62 % 35 = 27;

           Data akan dimasukkan ke index ke 27

2. Division
Menjumlahkan semua string yang ada pada data "kunci", kemudian dimodulo kan dengan angka tertentu. Angka yang memodulo bebas, tetapi harus konsisten untuk tiap kali Hashing.
Contoh : "HELLO" -> 72(H) + 69(E) + 76(L) + 76(L) + 79(O) =  372 % 35 = 22;


3. Folding
Menjumlahkan semua string ang ada pada data "kunci", kemudian hasil jumlah itu dipecah menjadi beberapa angka, kemudian dijumlah lagi.
Contoh : "HELLO" -> 72(H) + 69(E) + 76(L) + 76(L) + 79(O) =  372
              Folding -> 37 + 2 (dipecah menjadi per angka puluhan)
                           -> 39;

4. Digit Extraction
Mengambil beberapa bagian dari data kunci, dijadikan menjadi data Hash
Misal : key = 52635;
Yang diambil misalkan hanya angka ke-1, 3 dan 5
hasil Hash = 565;

5.Rotate Hash
Memutar data kunci, menjadi hasil hash baru
Misal : key = 52635;
Hash -> 53625;

Hasil dari Hashing tidak mungkin selalu berbeda antara satu data dengan yang lain.
Misalkan jika penggunaan Hashing dengan modulo 10.
Data 25 dan Data 35 akan memiliki hasil modulo yang sama.
Hal seperti ini yang disebut dengan Collision (tabrakan)

Ada 2 cara untuk mengatasi Collision:
a. Linear Probling
Menambahkan index pada data yang tertabrak.
Misalkan Hashing berdasarkan index pertama suatu data.
Data "Anak" dan "Aku" akan memiliki hasil Hashing yang sama
(65 bila berdasarkan ASCII)
maka data "Aku" yang bertabrakan dapat dimasukkan dalam index ke 66.
Hal ini dilakukan sampai menemukan Table baru yang kosong

b. Chaining
Jika Linear Probling dilakukan dengan menambakan index pada data yang bertabrakan.
Chaining dilakukan dengan menambakan Dynamic Array pada setiap Hash Table. Jadi ketika data pertama masuk. Data tersebut akan menjadi Head dalam satu row tersebut. Ketika ada data lain yang masuk index yang sama, data itu akan digeser menjadi next. Begitu pula seterusnya, penjelasannya dapat dilihat dalam gambar



Binary Tree
Binary Tree adalah tipe data struktur yang bentuknya seperti pohon, dimana ada satu data yang menjadi Root. Berbeda dengan data structure biasa yang menggunakan Head sebagai data pacuan. Binary Tree menggunakan data root sebagai data pacuannya.

Disebut sebagai Binary Tree karena data structure ini memiliki dua cabang, yaitu left dan right. Dalam memasukkan data dalam binary tree, biasanya, data yang memiliki value lebih kecil dari root, akan diletakkan di cabang kiri, sedangkan data yang memiliki value lebih besar dari root akan diletakkan di cabang kanan.

Contoh Binary Tree

Pointer yang harus ada dalam suatu Linked List

Pointer yang Harus Ada dalam Suatu Linked List

Pada post sebelumnya, sudah dibahas jenis jenis dari Linked List.
Post kali ini akan membahas pointer apa saja yang harus diperlukan agar suatu Linked List dapat terbentuk

1. Pointer Awal (*head)

Pointer Awal ini berfungsi untuk menunjuk kepada data yang terakhir kali dimasukkan dalam suatu Linked List, untuk penamaan secara umum menggunakan nama head (untuk memudahkan).
Pointer Awal ini dapat digunakan untuk mengecek kondisi apakah suatu Linked List sudah terisi atau belum, sebagai pacuan dalam PushHead, PopHead.

2. Pointer Akhir (*tail)

Pointer Akhir ini berfungsi untuk menunjuk kepada data yang pertama kali dimasukkan dalam suatu Linked List, untuk penamaan secara umum menggunakan nama tail.
Pointer Akhir ini dapat digunakan untuk mengecek apakah suatu Linked List sudah terisi atau belum, dapat juga digunakan sebagai pacuan dalam PushTail, PopHead, juga dapat menandakan bahwa data yang ditunjuk merupakan data yang terakhir.

3. Pointer untuk Menunjuk Data Lainnya (*next, *prev(optional))

Pointer ini memiliki fungsi yang sangat krusial, yaitu untuk menunjuk data selajutnya, bila tidak ada pointer ini, data dalam Linked List tidak dapat saling terhubung