Rangkuman AVL Tree

AVL Tree adalah salah satu bentuk dari Binary Search Tree. Yang menyebabkan AVL Tree berbeda adalah AVL Tree memiliki perbedaan tinggi antara subtree kiri dengan kanan maksimal satu atau perbedaan tingginya bisa memiliki tinggi yang sama. Hal ini untuk mempersingkat waktu pencarian serta mempersingkat dan menyerdehanakan bentuk tree.

Insertion 

Seperti Binary Search Tree pada umumnya, AVL Tree juga memiliki operasi insertion, bedanya terletak pada jenisnya. Terdapat 2 jenis Insertion yaitu : 

1. Single Rotation

operasi insertion ini bisa dilakukan pada node terdalam pada subtree kiri dan anak kiri dan juga pada subtree kanan dan anak kanan ( operasi ini dilakukan jika memasukan node pada tree yang berurutan seperti gambar diatas)

2. Double Rotation 

operasi insertion ini dilakukan pada node terdalam pada subtree kiri dan anak kanan serta subtree kanan dan anak kiri. 

Deletion 

untuk menghapus node pada AVL Tree memiliki kasus yang serupa dengan Binary Seach Tree yang normal, yaitu : 

a. jika node yang akan dihapus terletak pada leaf (node tanpa anak) maka akan langsung terhapus

b. jika node yang akan dihapus terletak pada node dengan anak maka harus diseimbangkan dengan menyesuaikan tinggi dengan perbedaan 1 tinggi dengan menggunakan single atau double rotation