Skip to main content

Heap & Tries

Heap 
Heap adalah suatu tree yang terdiri dari 3, yaitu Min Heap, Max Heap, dan Min-Max Heap. Heap juga berguna untuk membuat Priority Queue.

Ciri - ciri dari heap adalah :
- Setiap parent mempunyai maksimal 2 child
- Root dari heap berupa angka maksimal / minimal dari tree tersebut
- Berbeda dengan tree lain, heap menyimpan data-datanya di dalam array
- Index array di heap dimulai dari 1 untuk memudahkan ketika mencari parent dari child
- Setiap angka baru yang dimasukkan akan berada pada index terakhir yang akan dibandingkan dengan parentnya

Rumus untuk mencari parent di heap adalah :
Parent_index = index/2
Leftchild_index = index * 2
Rightchild_index = index*2+1

1. Min Heap
Min Heap adalah heap yang dimana rootnya adalah angka minimum dari heap itu sendiri.
Contoh Insertion :

Contoh Deletion :


2. Max Heap
Max Heap adalah kebalikan dari min heap. Max heap adalah sebuah heap yang dimana rootnya adalah angka maksimum dari heap itu sendiri.
Contoh Insertion :
Contoh Deletion :



3. Min-Max Heap
Min-Max Heap adalah sebuah heap yang terdiri dari level-level yang setiap levelnya itu berbeda.
Level genap di heap ini adalah berupa angka min dan level ganjil terdapat angka max.
Angka terkecil dari heap berada di array pertama,
Angka terbesar dari heap berada di array kedua atau ketiga.


Tries
Biasanya di tree pada umumnya, tries menyimpan dalam bentuk karakter. Tries bisa mempunyai anak lebih dari 2. Biasa digunakan untuk auto-complete / searching, bubble words, list/set/collection
misalnya space,spaces,spade,speak,speaker,speakers, dll
Maka kita gak perlu simpan per katanya, melainkan per karakter.

Comments

Post a Comment

Popular posts from this blog

Binary Search Tree

Binary Search Tree        -         Pengertian       Binary search tree (BST) adalah sebuah data struktur yang digunakan untuk mempercepat        searching, sorting, insertion dan deletion.       BST juga dikenal sebagai binary tree yang sudah disortir       Untuk sebuah node x dari BST : è Value di subtree kiri lebih kecil dari value dalam x è Value di subtree kanan lebih besar dari value dalam x       -         Binary search tree operations       BST mempunyai beberapa operasi : è Search(x) : untuk mencari key x di dalam BST Misalnya kita ingin mencari key x : o    Pertama kita mulai dari root o    Jika root adalah x maka proses selesai o    Jika x lebih kecil dari key root maka dilakukan searching secara rekursif di subtree sebelah kiri, be...
Post a Comment
Read more

AVL Tree (Insertion and Deletion)

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree digunakan untuk melakukan searching yang lebih singkat dan sederhana. Ada 4 case dalam melakukan operasi insert : Single Rotation Ada 2 case yang dapat diselesaikan dengan single rotation, yaitu ketika node terdalam terletak pada subtree kiri dan anak kiri T, (left rotation) dan ketika node terdalam terletak pada subtree kanan dan anak kanan T (right rotation). Double Rotation Di double rotation juga terdapat 2 case yang dapat terselesaikan dengan double rotation, yaitu jika node terdalam terletak pada subtree kanan dan anak kiri T (right-left), dan node terdalam terletak pada subtree kiri dan anak kanan T (left-right). Ada 2 case yang terjadi saat operasi delete : Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus. Jika node yang akan dihapus memiliki anak, maka pros...
Post a Comment
Read more