Pertemuan 6 - (AVL Tree)

Jika suatu Binary Tree yang diinsert terus menerus pada saat kondisi tertentu akan menimbulkan height tree semakin besar dan berat sebelah yang menjadikan binary tree tidak efektif. 

Maka dari itu dibutuhkan Balanced Binary Tree agar tetap efektif. Salah satunya dengan menggunakan AVL Tree

AVL TREE

AVL Tree adalah binary tree yang memiliki perbedaan tinggi/level maksimal 1 antara subtree kiri dan subtree kanan.

Penambahan node 

Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation.

Terdapat 4 kasus pada saat tidak balance :

1. Node yang terdalam terletak di sebelah left subtree dari left child node T (LL)
2. Node yang terdalam terletak di sebelah right subtree dari right child node T (RR)
3. Node yang terdalam terletak di sebelah left subtree dari right child node T (LR)
4. Node yang terdalam terletak di sebelah lright subtree dari left child node T (RL)

Terdapat dua cara penyelesaian :

• Single Rotation (Kasus 1 & 2)
• Double Rotation (Kasus 3 & 4)

Single Rotation

Double Rotation

Penghapusan Node

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, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.

Delete 60

terjadi ketidak seimbangan, lakukan single rotation (RR) 

masih terjadi ketidak seimbangan, lakukan double rotation (LR) setelah itu lakukan single rotation (LL)

Binary Tree sudah dalam keadaan Balance