AVL Tree (Balanced Binary Search Tree)

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Worst Case dari BST terjadi saat bentuk tree yang tidak balance, misalnya jika sederetan data terurut diinsert ke dalamnya akan membentuk cabang yang berbentuk rantai panjang (tanpa pencabangan lain). Situasi ini mengakibatkan operasi searching pada BST menjadi O(n), tidak sebagaimana yang diharapkan yaitu O(log n). Adelson-Velskii dan Landis mempelajari mekanisme tambahan pada operasi-operasi insert/delete pada BST sehingga BST selalu kembali ke dalam situasi “balanced”. Untuk memungkinkan mekanisme tsb bekerja secara O(log n) maka didefinisikan AVL tree sebagai BST dengan tinggi subtree kiri dan subtree kanan dari setiap node di dalamnya berbeda tidak boleh lebih dari 1 (jadi, jika HL dan HR adalah masing-masing tinggi subtree kiri dan kanan, maka HL – HR| ≤ 1).

Mekanisme rebalancing pada operasi insert dilakukan dengan mencari subtree terkecil yang mengalami “kerusakan” sesaat insert dilakukan. Di posisi itu dilakukan “operasi rotasi” yang dilakukan secara O(1). Ada empat jenis rotasi Single Right Rotation (SRR), Single Left Rotation (SLR), Double Right Rotation (DRR), dan Double Left (Rotation) sesuai dengan kondisi “kerusakan yang terjadi. Setelah rotasi yang dilakukan, subtree tersebut kembali menjadi AVL-tree dengan tinggi yang sama dengan tinggi sebelum insert. Dengan demikian, rotasi hanya dilakukan satu kali saja. Karena menentuan subtree terkecil mana yang terjadi kerusakan adalah operasi backtrack dari leaf ke arah root, maka mekanisme rebalancing ini menjadi operasi O(log n).  Mekanisme rebalancing pada operasi remove mirip dengan yang dilakukan pada insert kecuali operasi rotasi bisa terjadi beberapa kali karena setelah suatu rotasi di suatu subtree dilakukan, karena tinggi subtree kemudian menjadi berkurang, maka subtree yang lebih besar di atasnya harus diperiksa pula karena kemungkinan juga tidak balanced. Namun, operasi keseluruhan tetap adalah O(log n).

contoh :

insert values : 25, 17, 12, 22, 27, 33, 36

insert 25

insert 17

insert 12

insert 22

insert 27

insert 33

insert 36

jika masih bingung, berikut ini adalah link untuk simulasi AVL Tree
 
Simulasi

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s