2301900744
Hari : Selasa, 9 Juni 2020
Kelas : CB01-CL
Lecturer : Ferdinand Ariandy Luwinda (D4522) , Henry Chong (D4460)
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.
Gambar BST
digambar tersebut sudah menjadi AVL Tree, Tree sudah sesuai dengan syarat menjadi AVL Tree, Tree nya sudah balance antara satu dan lain.
Untuk memeriksa Tree tersebut sudah balance atau tidak, dengan cara [balance faktor] > 1, ditiap node di cek kedalamnya, digambar node 7 sisi kiri 2 dan sisi kanan 3, maka antara sisi kiri dan kanan dikurangkan kedalam nya (3-2= 1) , nah selanjutnya cek masing-masing node tree ya, apakah tidak >1 jika iya semua 1 atau 0 maka sudah di sebut AVL Tree
di AVL Tree ada 2 cara rotation dalam mencari balance Tree:
1. Single Rotation
a. Left Left Rotation
b. Right Right Rotation
contoh Single Rotation
a. Right Left Rotation
b. Left Right Rotation
Left-Right
Right-Left
Delete node di AVL Tree
Delete node di AVL Tree sama percis dengan Binary Search Tree, yaitu node yang dihapus digantikan oleh node tersebar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus leaf maka langsung di hapus. Namun jika node yang ingin di hapus memiliki anak maka anaknya yang menggantikannya. Pada saat delete pun harus di cek kembali, apakah tree tersebut sudah balance atau tidak. Jika belum maka lakukan proses Rotation.
Pengertian Heap...
Heap adalah Sebuah Complete Binary Tree yang memenuhi persyaratan heap. nah di heap terbagi 3 yaitu, Min Heap, Max Heap, dan Min-Max Heap
-Min Heap
urutan berdasarkan Array yang diberikan, Tree di mulai dari angka terkecil karena Min Heap
-Max Heap
Urutan Array dari 2, 33, 36, 5, 4, 8
2. Tries
Tries yang tadi saya pelajari, Tries semacam penampung karakter agar suatu game dalam mencari kata-kata tidak usah repot-repot mencari sebanyak kalimat.
referensi :
http://apalah-ini-itu.blogspot.com/2011/06/heap.html
urutan berdasarkan Array yang diberikan, Tree di mulai dari angka terbesar karena Max Heap.
- Min Max Heap
- Min Max Heap
Urutan Array dari 2, 33, 36, 5, 4, 8
2. Tries
Tries yang tadi saya pelajari, Tries semacam penampung karakter agar suatu game dalam mencari kata-kata tidak usah repot-repot mencari sebanyak kalimat.
referensi :
http://apalah-ini-itu.blogspot.com/2011/06/heap.html
PPT : Binus (Data Structure)
