AVL 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.

Terdapat beberapa perintah yang dapat di berikan kepada avl tree. Diantaranya adalah insert dan delete. Pada insert terdapat beberapa kemungkinan. Kemungkinan pertama adalah saat avl tree ditambahkan, avl tetap stabil (beda tinggi kiri dan kanan tidak lebih dari 1) maka insert dilakukan seperti biasa. Kemungkinan kedua adalah terjadi ketidak seimbangan. Bila terjadi ketidak seimbangan maka kita harus mengecek 2 node setelah node yang tidak seimbang. Bila 2 node yang meada yang membuat tidak seimbang berada pada 1 garis lurus (missal kiri dan kiri) maka lakukan single rotation. Bila tidak lurus( missal kiri lalu kanan) maka lakukan double rotation.

Perintah kedua yang dapat dilakukan pada avl tree adalah delete. Pada perintah ini juga bisa terjadi beberapa scenario. Bila pada saat didelet avl tree tetap seimbang, maka lakukan delete seperti biasa. Bila pada saat delete ada yang tidak seimbang maka, lakukan rotasi sesuai dengan kemungkinan pada insert.