AVL Tree

AVL adalah balanced Binary search tree yang memiliki perbedaan jumlah node subtree kiri dan subtree kanannya maksimal 1

Cara menentukan Height dan Balance Factor :

Height :
- Jika node tidak memiliki subtree heightnya = 0
- Jika node adalah leaf, height =  1
- Jika internal node, maka heightnya jumlah anaknya +1

Balance Factor :
-Selisih height antara anak kiri dan kanan,jika tidak memiliki anak, dianggap 0.

Insertion
Insert suatu node pada AVL sama halnya pada insert node pada Binary search tree, dimana node baru diposisikan sebagai leaf. Setiap melakukan Insert, maka kita harus melakukan pengecekan balance factor

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
Anggap O adalah node yang harus diseimbangkan kembali
- Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri O (left-left)
- Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan O (right-right)
- Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri O (right-left)
- Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan O (left-right)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
- Kasus 1 dan 2 dengan single rotation
- Kasus 3 dan 4 dengan double rotation

Single Rotation
Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right

Double Rotation
Double rotasi (rotasi 2x) dilakukan apabila searah, left-right atau right-left
Gambaran Double Rotation :

Step 1 (Rotasi pertama)

Deletion
Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan pengecek balance factor