Heap & Tries

Heap

Dalam ilmu komputer, sebuah heap adalah struktur data yang berdasarkan konsep struktur data pohon. Di heap, juga diterapkan konsep binary tree.

Terdapat 3 jenis heap, diantaranya 

a.     Min heap

Min heap merupakan heap yang node rootnya adalah angka terkecil dan setiap anak dari rootnya selalu lebih kecil daripada parentnya. Biasanya min heap ini, dia ascending ( dari terkecil ke terbesar ).

b.    Max heap

Max heap ini sama seperti min heap, tapi bedanya adalah angka yang berada di root adalah angka terbesar dan max heap ini descending ( dari terbesar ke terkecil ).

c.     Min Max heap

Untuk min max heap ini cukup unik, dimana root dari heap ini merupakan angka terkecil didalam tree nya, tapi angka yang berada dii node anak dari sebuah root merupakan angka paling besar dan berlaku seterusnya sampai ke bawah.

Tries

Tries disini sama dengan kebanyakan tree pada umumnya, tapi pada tree yang kita temukan hingga sekarang, mereka mengisinya dengan angka disetiap nodenya. Tapi di tries, kita akan menggunakan dengan next levelnya lagi, yaitu diisi dengan character huruf. Implementasi trie ini bisa anda temukan di game yang seperti susun kalimat, dapat juga ditemukan pada google search dimana kita mengetik 1 huruf, akan keluar recommended yang diberikan oleh google. Misalkan kita mengetik Y, maka dapat ditemukan banyak rekomendasi yang diberikan oleh google. 

Seperti itu contoh pencarian di google.

Di trie ini, mereka selalu memiliki 1 parent yang sama dan beberapa jenis cabang di bawahnya. Nah di cabang ini dapat bercabang lagi dan seterusnya. Dan bisa menghasilkan kata yang masuk akal disana.

Rangkuman

1. Linked List

Linked List ada 4 jenis :
1. Single Linked List
2. Double Linked List
3. Circular Single Linked List
4. Circular Double Linked List


1. 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

2. Double Linked List
adalah sekumpulan node yang terhubung melalui pointer tetapi terdapat 2 arah yaitu 1 pointer menunjuk ke node selanjutnya dan satu lagi menunjuk ke node sebelumnya. Jadi kita bisa mengakses kembali node yang sebelum node sekarang.

3. Circular Single Linked List
adalah sekumpulan node yang terhubung melalui pointer tetapi pointer node terakhir menunjuk ke node pertama.

4. Circular Double Linked List
adalah sekumpulan node yang terhubung melalui pointer tetapi pointer node terakhir menunjuk ke node pertama dan node pertama juga bisa ke node terakhir.

Beda Linked List dan Array adalah:
- alamat memori Array berurutan, sedangkan Linked List tidak
- Linked List dinamis, bisa berapapun datanya, sedangkan Array statis , hanya bisa diisi data sesuai dengan ukuran array yang sudah diinisialisasi sebelumnya

Insert dalam Linked list ada 3 macam :
1. Push Head ( memasukkan data di depan / head ) FILO
2. Push Tail ( memasukkan data di belakang / tail ) FIFO
3. Push Mid ( memasukkan data di tengah-tengah dengan kondisi tertentu )

Stack & Queue 

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/

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.

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

Linked List ada 4 jenis :
1. Single Linked List
2. Double Linked List
3. Circular Single Linked List
4. Circular Double Linked List


1. 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

2. Double Linked List
adalah sekumpulan node yang terhubung melalui pointer tetapi terdapat 2 arah yaitu 1 pointer menunjuk ke node selanjutnya dan satu lagi menunjuk ke node sebelumnya. Jadi kita bisa mengakses kembali node yang sebelum node sekarang.

3. Circular Single Linked List
adalah sekumpulan node yang terhubung melalui pointer tetapi pointer node terakhir menunjuk ke node pertama.

4. Circular Double Linked List
adalah sekumpulan node yang terhubung melalui pointer tetapi pointer node terakhir menunjuk ke node pertama dan node pertama juga bisa ke node terakhir.

Beda Linked List dan Array adalah:
- alamat memori Array berurutan, sedangkan Linked List tidak
- Linked List dinamis, bisa berapapun datanya, sedangkan Array statis , hanya bisa diisi data sesuai dengan ukuran array yang sudah diinisialisasi sebelumnya

Insert dalam Linked list ada 3 macam :
1. Push Head ( memasukkan data di depan / head ) FILO
2. Push Tail ( memasukkan data di belakang / tail ) FIFO
3. Push Mid ( memasukkan data di tengah-tengah dengan kondisi tertentu )