Postingan

HEAP & TRIES

Gambar
HEAP - Min heap: nilai child selalu lebih besar, makin ke bawah makin besar nilainya. - Max heap: nilai child selalu lebih kecil, root paling besar nilainya. - Min max heap: min - max - min - max. Root selalu paling minimum, anak dari root selalu maksimum Heap biasanya menggunakan array. Array dimulai dengan index 0, sedangkan heap dimulai dari 1. Rumus mencari parent = index sekarang/2 Rumus mencari left child = index sekarang*2 Rumus mencari right child = (index sekarang*2)+1 Insertion Min Heap Taruh di array index terakhir (buat baru) lalu up head bandingin dengan parentnya apakah dirinya lebih kecil dari parent , kalau lebih kecil tukar posisi dengan parent. Dilakukan berulang hingga syarat lebih kecil tersebut tidak memenuhi. Insertion Max Heap  Taruh di array index terakhir (buat baru) lalu up head bandingin dengan parentnya apakah dirinya lebih besar dari parent , kalau lebih besar tukar posisi dengan parent. Dilakukan berulang hingga syarat lebih ...
Posting Komentar
Baca selengkapnya

AVL Tree

Gambar
AVL Tree merupakan bentuk BST yang lebih rumit. Syarat – syaratnya selain pertimbangan besaran value seperti BST dimana yang lebih kecil ke kiri serta yang lebih besar ke kanan, AVL Tree juga mempertimbangkan height dan balance. Height adalah ketinggian atau kedalaman tingkat seperti lantai pada node. Height dari sebuah node adalah height maksimal dari anak – anaknya ditambah 1.  Sedangkan balance adalah nilai yang didapat dari pengurangan height kiri dengan height kanan. Balance pada AVL hanya boleh 0 atau 1, tidak boleh lebih atau kurang, jika terjadi violation maka harus dirotate. AVL berguna untuk memudahkan pencarian daripada BST karena syarat terurutnya lebih banyak, pencarian dapat dilakukan dengan cepat menggunakan AVL. Syarat insert adalah: 1.     Jika node lebih kecil daripada root maka akan bergerak ke kiri, jika lebih besar maka ke kanan (seperti pada BST). 2.       Balancing -   ...
Posting Komentar
Baca selengkapnya