AVL Tree

AVL Tree adalah binary tree yang diseimbangkan, yang dimana perbedaan tinggi antara kanan dan kiri subtree tidak boleh lebih dari satu.

Misalkan T adalah node yang harus diseimbangkan kembali,

-Kasus 1 : node terletak pada subtree kiri dari anak kiri T (Left - Left) / LL

-Kasus 2 : node terletak pada subtree kanan dari anak kanan T (Right - Right) / RR

-Kasus 3 : node terletak pada subtree kanan dari anak kiri T (Right - Left) / RL

-Kasus 4 : node terletak pada subtree kiri dari anak kanan T (Left - Right) / LR

Kasus-kasus diatas dapat diselesaikan dengan cara rotasi.

Kasus 1 & Kasus 2 = Single rotation

Kasus 3 & Kasus 4 = Double rotation

1. Single Rotation

Single rotation adalah : pengubahan node yang dilakukan bila node terletak searah

2. Double Rotation

Double rotation adalah : pengubahan node yang dilakukan bila node terletak tidak searah

Penghapusan node dalam AVL Tree

Cara:

1. Jika node yang akan dihapus berasa di posisi leaf, maka langsung hapus

2. Jika node yang akan dihapus memiliki anak, maka harus dilakukan penyeimbangan, supaya perbedaan tinggi maksimal satu.