TREE

AVL Tree

AVL tree adalah Binary Search Tree (BST) yang dapat menyeimbangkan diri sendiri di mana perbedaan antara ketinggian subtree kiri dan kanan tidak boleh lebih dari satu untuk semua node.

Pohon di atas adalah AVL karena perbedaan antara ketinggian sub pohon kiri dan kanan untuk setiap node kurang dari atau sama dengan 1.

Untuk memastikan bahwa pohon yang diberikan tetap AVL setelah setiap penyisipan, kita harus menambah operasi penyisipan BST standar untuk melakukan penyeimbangan ulang.

Waktu yang diperlukan untuk melakukan insertion, deletion, search, atau operasi lainnya bergantung pada ketinggian pohon, ini berarti mereka dapat menjadi O (n) dalam kondisi terburuk.

Balance factor:

Perbedaan ketinggian subtree KIRI dan subtree KANAN.

Single Rotation

Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar tersebut. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0).

Double rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada tersebut. T1, T2, T3, dan T4 adalah subtree yang urutannya harus seperti demikian. Tinggi subtree T1 harus sama dengan T4, tinggi subtree T2 harus sama dengan T3. Node yang ditambahkan akan menjadi child dari subtree T2 atau T3.