AVL Tree Martin Leonardo Hermawan 2301873043

AVL Tree

AVL Tree adalah sebuah BST (Binary Search Tree) yang memiliki maksimal perbedaan tinggi level 1 antara subtree kiri dan subtree kanan. AVL Tree berguna untuk menyeimbangkan BST. Waktu pencarian yang dibutuhkan lebih sedikit dan bentuk tree akan terlihat lebih sederhana.

Contoh AVL Tree

Contoh yang bukan AVL Tree

Dapat dilihat subtree kiri dari node 76 ada 3 tetapi subtree kanannya 0 jadi perbedaan tinggi nya 3.

Insertion

Ada 4 kasus dalm insertion, yaitu :

• Jika ada ketidakseimbangan pada anak kiri subtree kanan, maka dilakukan rotasi kiri-kanan.
• Jika ada ketidakseimbangan pada anak kiri subtree kiri, maka dilakukan rotasi kanan.
• Jika ada ketidakseimbangan pada anak kanan subtree kanan, maka dilakukan rotasi kiri.
• Jika ada ketidakseimbangan pada anak kanan subtree kiri, maka dilakukan rotasi kanan-kiri.

Untuk menjaga tree tetap seimbang, setelah penambahan sebuah node, dilakukan pemeriksaan dari node baru ke root. Node pertama yang memiiki balance factor > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan 2 cara yaitu single rotation dan double rotation.

Single Rotation

Double Rotation

Deletion

Proses menghapus sebuah node AVL Tree hampir sama dengan BST. Penghapusan sebuah node dapat membuat sebuah tree menyadi tidak seimbang. Setelah menghapus sebuah node, lakukan pengecekan dari node yang dihapus ke root. Gunakan single rotation atau double rotation untuk menyeimbangkan node yang tidak imbang.