AVL Tree

AVL Tree
AVL tree adalah binary search tree di mana perbedaan ketinggian sub pohon kiri dan kanan dari setiap node kurang dari atau sama dengan satu.

AVL tree bersifat seimbang.

AVL tree memiliki jaminan tambahan:

Perbedaan antara kedalaman subtrees kanan dan kiri tidak boleh lebih dari satu. Untuk menjaga jaminan ini, implementasi AVL akan menyertakan algoritme untuk menyeimbangkan kembali pohon saat menambahkan elemen tambahan akan mengganggu jaminan ini.
Pohon AVL memiliki pencarian kasus terburuk, masukkan dan hapus waktu O (log n).

Proses Insertion AVL
Anda akan melakukan insertion yang mirip dengan penyisipan Binary Search Tree normal. Setelah memasukkan, Anda memperbaiki properti AVL menggunakan rotasi kiri atau kanan.

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

Rotasi AVL Tree
Di AVL Tree, setelah melakukan setiap operasi seperti penyisipan dan penghapusan kita perlu memeriksa faktor keseimbangan setiap simpul di pohon. Kami menggunakan operasi rotasi untuk membuat pohon seimbang setiap kali pohon menjadi tidak seimbang karena operasi apa pun.

Operasi rotasi digunakan untuk membuat pohon seimbang. Ada empat rotasi dan diklasifikasikan menjadi dua jenis:

• Single Left Rotation

Dalam Rotasi ini setiap node bergerak satu posisi ke kiri dari posisi saat ini.

• Single Right Rotation (RR Rotation)

Dalam RR Rotation setiap node bergerak satu posisi ke kanan dari posisi saat ini.

• Left Right Rotation (LR Rotation)

Rotasi LR adalah kombinasi dari rotasi kiri tunggal diikuti oleh rotasi kanan tunggal. Dalam LR Rotation, pertama setiap node bergerak satu posisi ke kiri lalu satu posisi ke kanan dari posisi saat ini.

• Right Left Rotation (RL Rotation)

Rotasi RL adalah kombinasi dari rotasi kanan tunggal diikuti oleh rotasi kiri tunggal. Dalam Rotasi RL, pertama setiap node bergerak satu posisi ke kanan lalu satu posisi ke kiri dari posisi saat ini.