Skip to main content

Heaps & Tries


Heaps
Heaps adalah binary tree yang menyimpan datanya dengan sorting. Karena terdapat sorting dalam heaps, insertion dalam heaps menjadi lebih cepat namun untuk mencari atau menghapus data dalam heaps membutuhkan proses yang lama.
Heaps dibagi menjadi 3 macam, yaitu:
1.      Min Heaps
o   Node pasti lebih kecil valuenya daripada childnya
o   Root mempunyai value yang paling kecil dalam tree
o   Leaf mempunyai value terbesar dalam tree
2.      Max Heaps
o   Value dari node pasti lebih besar daripada childnya
o   Root mempunyai value paling besar dalam tree
o   Leaf memiliki value terkecil dalam tree
3.      Min – Max Heaps
o   Min heaps diterapkan pada level ganjil dan max heaps diterapkan pada level genap


Heaps dapat diimplementasi menggunakan array maupun linked list. Aplikasi heaps adalah sebagai berikut:
o   Priority Queue
o   Selection algorithm
o   Dijkstra's Algorithm
o   Prim Algorithm

Tries
Tries adalah binary tree yang digunakan untuk mengurutkan suatu kumpulan string.
Tries memiliki ciri-ciri sebagai berikut:
-        Setiap node merepresentasikan satu huruf
-        Root merepresentasikan karakter kosong
Aplikasi pada tries adalah auto-complete yang ada pada search engine browser.


Sumber:

http://gabrielyakub.blogspot.com/2016/05/pertemuan-8-heap-tries-hashing.html?view=timeslide

Comments

Post a Comment

Popular posts from this blog

Rangkuman 2

Nama: Christopher Wibisono NIM: 2301913822 Nama Dosen: CB01 (Kelas Besar) : Henry Chong(D4460) & Ferdinand Ariandy Luwinda (D4522) LM01 (Kelas Kecil) : Alexander (D5319) Pada blog kali ini, kita akan mereview apa saja yang sudah dipelajari selama akhir semester 2 ini. AVL Tree  adalah lanjutan dari  Binary Search Tree . Dengan  AVL Tree ,  Binary Search Tree  yang tingginya berat sebelah akan dibuat menjadi rata dengan mengubah posisi dari  node  yang membuat  tree  tidak seimbang. Pengubahan posisi tersebut dilakukan dengan cara  rotating , dimana  node  yang menjadi akar masalah dalam  tree  tersebut akan dipindahkan menjadi node yang berada diatas nya dan node yang berada pada atasnya akan berubah tempat mengikuti dengan aturan  Binary Search Tree . Rotating  terbagi menjadi dua, yaitu  Single Rotate  dan  Double Rotate . Seperti namanya,  Single Rotation  merupakan Rotasi yang dilakukan sekali saja. Rotasi ini hanya dilakukan sekali saja, dengan menemukan  n
Post a Comment
Read more

Hash Table & Binary Tree

Hash Table Hashing adalah teknik untuk memberi identifikasi pada objek tertentu dari sekelompok objek yang mirip dengan objek tersebut. Dengan begitu, kita dapat mengakses objek tersebut dengan cepat. Ambil contoh jika kita memiliki sebuah objek dan kita ingin memberi sebuah key kepada objek tersebut. Untuk menyimpan nilai dari key tersebut, kita dapat menggunakan array simpel dimana index dari array tersebut dapat menjadi key (integer) dari objek yang ingin dicari. Namun, ada beberapa kasus dimana nilai dari key sendiri cukup besar dan tidak dapat digunakan langsung dari index array , dan kita harus menggunakan hashing . Hash Table adalah tabel ( array ) untuk menyimpan string awal.   Ukuran dari hash table biasanya beberapa kali lebih rendah dari total angka dari string , maka beberapa string dapat mempunyai hashed-key yang sama. Berikut contoh source code dari menyatakan data dengan hash key serta cara me
Post a Comment
Read more

Stack & Queue

Materi hari ini membahas tentang proses yang dapat terjadi dalam Linked List . Dua proses pengumpulan data yang dibahas hari ini adalah Stack & Queue . Bagiamanakah proses ini terjadi, serta bagaimana cara implementasi dalam Bahasa C? Kita akan membahas hal tersebut dibawah ini. Yang ditekankan saat ini adalah operasi dalam Linked List. Beberapa operasi yang ada adalah push() , pop() , serta top() . top() juga dikenal sebagai peek() . Ilustrasi dari push(), pop(), serta top() dalam array (Stack) Ilustrasi dari push(), pop(), serta top() dalam array(Queue) Contoh fungsi dari push() dalam Bahasa C Contoh fungsi dari pop() dalam Bahasa C Contoh fungsi dari top() dalam Bahasa C Kesimpulannya, push() adalah fungsi untuk menambahkan sebuah data ke dalam kumpulan data. pop() adalah fungsi untuk menghapus sebuah data dalam kumpulan data yang ada. top() atau peek() adalah fungsi untuk mengakses data paling pertama yang ada tanpa mengu
Post a Comment
Read more