AVL Tree (Balanced Binary Search Tree)

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 H_L dan H_R adalah masing-masing tinggi subtree kiri dan kanan, maka H_L – H_R| ≤ 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).