Rangkuman Data Structure Week 7

Rangkuman Heap

Nama: Julian Andhika Diputra

NIM: 2301858023

Heap adalah sebuah data structure tree. Heap dibagi menjadi dua tipe:

A. Min-heap: Semua node yang terdapat di tree tersebut harus lebih besar dari node di root tree tersebut. Jadi root pertamanya adalah node paling kecil. Hal itu akan secara rekursif di semua sub tree binary tree.

B. Max-heap: Semua node yang terdapat di tree tersebut harus lebih kecil dari node di root tree tersebut. Jadi root pertamanya adalah node paling besar. Hal itu akan secara rekursif di semua sub tree binary tree. 

Min-Heap

Insertion:

1. Masukkan elemen seperti binary tree biasa

2. Jika properti heap tidak valid ( Angka yang diinsert lebih kecil daripada root ), tukar dengan elemen tersebut. Lakukan terus sampai properti heap benar.

Deletion:

1. Delete root sebuah binary heap

2. Tukar dengan elemen yang terakhir kali di-insert

3. Heapify ( Tukar jika root bukan angka paling kecil ) binary heap tersebut.

Max-Heap

Insertion:

1.  Masukkan elemen seperti binary tree biasa

2. Jika properti heap tidak valid ( Angka yang diinsert lebih besar daripada root ), tukar dengan elemen tersebut. Lakukan terus sampai properti heap benar.

Deletion:

1. Delete root sebuah binary heap

2. Tukar dengan elemen yang terakhir kali di-insert

3. Heapify ( Tukar jika root bukan angka paling besar ) binary heap tersebut. 

Implementasi Min-Max Heap:

1. Gunakan array untuk store data, tapi mulai dari dari index 1

2.  Untuk semua node di posisi i:

- Left Child = 2*i

- Right Child = 2*i+1

- Parent Node = i/2

Tries

Trie adalah sebuah contoh data structure yang dibuat berdasarkan sebuah prefix dari string. Tries ini digunakan untuk menyimpan sebuah string yang divisualisasi seperti sebuah grafik. Setiap node memiliki maximal 26 anak.