Heaps & Tries

heaps itu terbagi menjadi 3 jenis:

• min heap
• max heap
• min-max heap

heap itu selalu berurut, jika min heap maka root akan merupakan angka yang paling kecil dan semaikin kebawah semakin besar. dan ketika di insert baru dia akan selalu mencocokkan dengan parentnya terus hinga angka yang diatasnya lebih kecil daripada dia. dan ketika di delete dia akan mencari angka yang lebih kecil antara childnya. hal ini pun juga berlaku untuk max heap.

sedangkan dengan min-max heap mereka berbeda pada setiap levelnya. misalnya pada level genap akan selalu min dan ganjill max. jadi mereka membandingkan dengan kedua sisi atas bawah.

tries itu merupakan prefix tree dimana dia akan memanfaatkan huruf yang ada sebelumnya dan mencabang dari sana sehingga menghemat banyak tempat dalam penyimpanannya

AVL Tree

Pada pertemuan kali ini saya mempelejari tentang AVL Tree. AVL Tree merupakan salah satu contoh dari balanced binary search tree.

AVL Tree harus memiliki sisi yang jarangnya satu sama lain tidak boleh lebih dari 1. Jika lebih maka itu tidak balance dan harus segera diperbaiki. Dan lebih baik apabila tidak ada perbedaan sama sekali agar menjadi benar-benar balance.

Setiap AVL Tree melakukan insert maupun delete harus diperhatikan balance atau tidak.

Jika AVL Tree tersebut tidak balance maka akan ada 2 pilihan cara membenarkannya: yaitu, single rotation dan double rotation.

Sisanya secara dasar sama dengan tree biasa. Jika lebih besar dari parent akan dimasukkan ke sisi kanan dan jika lebih kecil akan dimasukkan ke sisi kiri.

Ketika melakukan insertion dapat terjadi 4 kasus dimana masing-masing tidak seimbang dan harus diperbaiki.

1. LL rotation, hal ini dapat diperbaiki dengan single rotation dengan mudahnya.
2.  RR rotation, sama pula halnya seperti LL rotation hal ini dapat diperbaiki dengan single rotation
3. LR rotation, sedangkan dengan ini tidak bisa dengan single rotation tapi harus dengan double rotation.
4. RL rotation, sama halnya dengan LR rotation hal ini dapat dipeerbaiki dengan double rotation.