HEAP and TRIES

HEAP

Heaps adalah binary tree yang nodenya dapat direpresentasikan dalam sebuah array.

Type of Heap

A. Max Heap
Max yang berarti parentnya lebih besar daripada childnya. Elemen terbesar pada Max Heap terdapat di root tree dan semakin kebawah artinya semakin kecil.


B. Min Heap
Min yang berarti parentnya lebih kecil daripada childnya. Elemen terbesar pada Min Heap terdapat di root tree dan semakin kebawah artinya semakin besar. Heap dapat diimplementasikan menggunakan linked list tapi lebih mudah menggunakan array.


C. Min Max Heap
Ini adalah case unik atau spesial dari heap. Max dan min bergantian pada setiap level. Urutan level dari heap berupa min(dimulai dari root) lalu max lalu min lagi dan seterusnya. Pada bagian min akan selalu ganjil dan max akan selalu genap.


Di dalam heap terdapat 2 metode yaitu insertion dan deletion.

Max Heap Insertion
step 1 : membuat node baru di akhir dari heap
step 2 : memasukkan nilai baru ke node tersebut
step 3 : membandingkan node tersebut dengan parentnya
step 4 : apabila node lebih besar dari parent maka swap node tersebut dengan parentnya
step 5 : ulangi langkah 3 & 4 hingga heap selesai
Contoh:
Max Heap Deletion
step 1 : hapus rootnya
step 2 : pindah element terakhir dari level terakhir untuk menjadi root baru
step 3 : bandingkan child nodenya dengan parentnya
step 4 : apabila nilai parent lebih kecil dari child maka swap mereka
step 5 : ulangi langkah 3 & 4 hingga tuntas

TRIES

Tries ini adalah jenis pohon atau jenis tree yang memiliki banyak nodes yang digunakan untuk mempermudah searching/pencarian. Tries ini sudah diimplementasikan dalam banyak hal salah satu contohnya adalah pada web browser, google, dan lain sebagainya. Program ini dapat mengira atau menebak kata-kata yang akan kita ketik seperti autocomplete.

Contoh dalam google :

Tries ini sendiri berupa tree yang dimana setiap vertex/pathnya menggambarkan suatu kata sehingga tree ini memiliki root yang sangat banyak dan membentuk kata-kata yang berbeda-beda. Rootnya Tries ini tidak memiliki isi atau kosongan.

Contoh:
Pada gambar tersebut, simbol "$" itu biasanya berisi NULL.

Komentar

Posting Komentar

Postingan populer dari blog ini

AVL Tree

Gambar
Pada dasarnya AVL Tree ini adalah Binary Search Tree namun yang lebih seimbang atau balance karena pasti total node kiri dan kanan selisih tingginya tidak akan lebih dari 1. Sedangkan di BST bisa saja tinggi node kiri dan kanan tidak seimbang sehingga bisa menyebabkan proses pencarian, insert, maupun delete lebih lama yaitu n sedangkan dengan AVL Tree proses pencarian,insert, atau delete menjadi log n. Contoh hasil BST jika dengan insert 2, 5, 7, 8, 13: Contoh hasil AVL Tree jika dengan insert yang sama: Untuk menyeimbangkan node tersebut, AVL Tree menggunakan rotasi atau rotation. Rotation ini dibagi menjadi 2 yaitu single rotation dan double rotation. rotation ini terjadi akibat perbedaan selisih tinggi node kiri dan kanan yang lebih dari 1. Contoh single rotation Contoh double rotation
Baca selengkapnya

Summary

Gambar
Linked List Pada pertemuan kedua kelas besar kemarin saya belajar mengenai cara membuat linked list di C. Setelah saya mempelajarinya kemarin, saya juga mencoba membuat linked list buatan saya sendiri. Berikut codingan linked list saya : #include<stdio.h> #include<stdlib.h> #include<string.h> struct Node{ int test; char nama[1000]; struct Node *next; }*head,*curr,*tail,*temp1,*temp2; void pushhead(int a,char nama[]){ curr = (struct Node*)malloc(sizeof(struct Node)); curr -> test = a; strcpy(curr->nama,nama); if(head==NULL){ head=curr; tail=curr; tail->next=NULL; } else{ curr->next = head; head = curr; } } void pushtail(int a,char nama[]){ curr = (struct Node*)malloc(sizeof(struct Node)); curr -> test = a; strcpy(curr->nama,nama); if(head==NULL){ head=curr; tail=curr; tail->next=NULL; } else{ tail->next = curr; curr->next=NULL; tail = curr; } } void poptail(){ curr=head; while(curr->next->nex...
Baca selengkapnya