Heap and Tries

Heap adalah complete binary tree (bukan binary search tree) yang mempunyai 2 properties yaitu :

1.Min heap

dalam min heap disimpulkan parentnya merupakan nilai terkecil , dan nilai terbesar berada dalam salah satu leaf / anaknya.

contoh :

 .

Insertion Min heap :

dalam menginsert di min heap , kita menaruh anak di tempat setelah terakhir , jika anak tersebut lebih kecil dari parentnya , maka di tukar.

Deletion Min heap :

Node yang di delete adalah root (karena nilainya paling kecil) lalu di gantikan oleh node yang terakhir kali di insert dan di sesuaikan dengan properties secara rekursif.

2.Max heap

node paling atas adalah node yang terbesar , dan node terkecil berada salah satu leaf / anaknya.

Insertion Max heap :

dalam menginsert di min heap , kita menaruh anak di tempat setelah terakhir , jika anak tersebut lebih besar dari parentnya , maka di tukar.

Deletion Max heap :

menukar anak kiri atau kanan dari root dengan node terakhir dari heap lalu hapus. Lalu downheapmax dari node tersebut.

3.Min-Max heap :

gabungan dari min dan max , dalam konsep ini root akan bernilai terkecil , selanjutnya akan bernilai maksimum , lalu minimum lgi ,dan seterusnya

insertion Min-max heap :

• Insert node sesuai urutan, lalu cek upheap lalu sesuaikan dengan properties level.
• Umumnya dilakukan penyesuaian rekursif dengan urutan sebagai berikut:
1. Parent
2. Grand Parent

Deletion Min - max heap :

• Deletion selalu dilakukan pada root, lalu sesuaikan dengan downheap sesuai properties
• Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebahai berikut:
1. Grand child
2. Child ( grand child disesuaikan dengan parentnya)

Tries
Berasal dari kata reTRIEval yang berarti untuk menyimpan asosiatif array dan jika dalam aplikasinya trie concept ini seperti auto-complete

• Properties pada tries:
• Setiap vertex/node merepresentasikan satu huruf
• Root merepresentasikan karakter kosong

.

Nama : Joviandy Widyananda

Kelas : LK01

            CB01

NIM : 2301846225

referensi :

http://hardiyanticitrawati1901527971.blogspot.com/2016/05/dalam-pertemuan-kali-ini-kami-membahas.html

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