Linked list II

HEAPS AND TRIES

Heaps

Heaps adalah struktur data yang berbasis binary tree komplit yang memenuhi properti heap.
  1. Min heap, dimana nilai parent harus lebih kecil dari nilai children.
  2. Max heap, dimana nilai parent lebih besar dari nilai children. 
  3. Min max heap, dimana lebih mudah untuk menemukan kondisi heap min level dan max level. Setiap elemen memiliki level ganjil/genap yang lebih kecil dari semua children (MIN level), sedangkan setiap elemen yang memiliki level ganjil/genap lebih besar dari semua children (MAX level).
Implementasi Heap menggunakan array yang dimulai dari indeks ke 1. Setiap hubungan node dengan parent, left child, dan right child dalam implementasi array dapat dihitung dengan mudah melalui rumus umum berikut:
  • Parent(x)  = x / 2
  • Left-child(x)  = 2 * x  
  • Right-child(x)  = 2 * x + 1

Insertion 
Saat sebuah data baru dimasukkan dalam heap, maka data langsung ditempatkan di index terakhir dalam heap itu data di-uheap yang maksudnya data dibandingkan dengan parentnya. Bila lebih kecil, maka swap dengan parentnya dan dilakukan terus menerus sampai lebih besar dari parentnya. Max heap sama dengan Min heap hanya berbeda tanda lebih besar dan lebih kecil saja.
Deletion Jika dalam insertion dipakai Upheap, maka dalam deletion dipakai Downheap. Deletion dalam heap otomatis menghapus node root dari heap. Jadi, delete min dalam min heap dan delete max dalam max heap. Node yang dihapus selalu root karena merupakan note yang paling kecil sehinngga node tersebut langsung di downheap sampai ke posisinya.


Tries

Tries adalah suatu pohon struktur data yang terurut yang menyimpan data array, biasanya string. Kata tries diambil dari kata RETRIEVAL, karena tries dapat menemukan kata tunggal dalam kamus dengan hanya awalan katanya saja.

Tries memiliki 2 property, yaitu : 
  • root selalu kosong
  • setiap node diisi kata awalan
contoh gambarannya : 
















Comments

Post a Comment

Popular posts from this blog

AVL TREE

Image
AVL TREE : AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ levelmaksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untukmenyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian danbentuk tree dapat dipersingkat dan disederhanakan. Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru→ root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Prosespenyeimbangan dilakukan dengan: Single rotation dan Double rotation. Penambahan node di AVL Tree         Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan.   Proses penyeimbangan dilakukan dengan:   Single rotation  dan  Double rotation Single Rotation Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 2. T1, T2, d
Read more

Linked List II

Image
Pada pertemuan hari ini saya belajar mengenai  3 hal , yaitu: circular single linked list doubly linked list circular  doubly linked list Circular Single Linked List: Circular Single Linked List adalah single linked list yang pointer nextnya menunjuk pada dirinya sendiri. Jika single list tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya. Doubly linked list: Double Linked List adalah sekumpulan node data yang terurut linear atau sekuensial dengan dua buah pointer yaitu prev dan next. Doubel Linked List adalah linked list dengan node yang memiliki data dan dua buah referensial( biasanya disebut next dan prev ) yang menunjuk ke node sebelum dan node sesudahnya. Circular Doubly Linked List; circular doubly linked list sama seperti circular single linked list tetapi total pointer untuk setiap node memiliki 2 point link Referensi: https://kuliahinformatika.wordpress.com/2010/01/21
Read more

Binary Search Tree

Binary Search Tree BINARY SEARCH TREE Apa itu binary search tree? Sebelum masuk ke materi kita harus paham maksud dari tree dan binary tree terlebih dahulu.Tree (pohon)  adalah salah satu bentuk  struktur data  yang menggambarkan hubungan  hierarki  antar elemen-elemennya (seperti relasi one to many).B inary tree adalah  tree yang hanya dapat mempunyai maksimal 2 percabangan saja . Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada  root node . Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node. Aturan main binary search tree: Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya. Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya. Lalu, ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST : PreOrder :  Print data
Read more