AVL Tree

            Jadi, apa itu AVL Tree? AVL Tree merupakan bentuk yang lebih advance atau terusan dari Binary Search Tree yang memiliki batas toleransi tinggi maksimal 1 antara subtree kiri dan subtree kanan dengan tujuan untuk menyeimbangkan serta mempermudah dalam pengoperasian Binary Search Tree. Dengan AVL Tree, waktu pencarian suatu data serta bentuk tree dapat dipersingkat dan disederhanakan. Untuk menjaga sebuah tree tetap seimbang meskipun telah disisipi nodes, maka perlu dilakukan pemeriksaan node baru dengan root. Jika node pertama memiliki balance factor lebih dari satu, maka perlu dilakukan penyetaraan. Ada dua jenis penyetaraan yang dapat dilakukan, yaitu single serta double rotation.

·               Single Rotation

Kapan kita harus menggunakan single rotation? Pada dasarnya kita akan menggunakan single rotation jika kondisi AVL Tree searah. Berikut contoh pengimplementasiannya :

·              Double Rotation

Pada beberapa soal di AVL tree umumnya dapat diselesaikan  hanya  dengan  cara  single rotation, seperti pada contoh diatas.  Tetapi ada beberapa soal yang tidak bisa diselesaikan jika kita hanya menggunakan single rotation.  Berarti kita harus  menggunakan  teknik double rotation untuk menyelesaikan masalah imbalance pada tree Berikut contoh pengimplementasiannya :

 Sekian rangkuman saya mengenai dua operasi pada metode insert di AVL Tree, Terimakasih.