Avl Tree

AVL TREE

Avl tree merupakan BST yang telah diseimbangkan dengan  perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. 

Contoh AVL :

Insert pada AVL Tree

Sebenarnya insert pada AVL Tree sama dengan insert pada BST, tetapi untuk tetap menjaga keseimbangan tree akan ada pemeriksaan peberdaan tinggi pada subtree kanan dan subtree kiri, jika perbedaannya lebih dari 1 tingkat, maka akan dilakukan perubahan pada node dengan rotasi-rotasi tertentu, Sehingga  insert pada AVL Tree dibagi menjadi 2 macam :

1. Single Rotation
   Single rotation akan digunakan apabila  jalur dari node yang bermasalah sampai porosnya itu lurus/tidak berbelok.
   
   Konsep Single Rotation :

      2. Double Rotation
          Double rotation akan digunakan apbila jalur dari node yang bermasalah sampai porosnya itu
          berbelok.

         Konsep Double Rotation :

Delete pada AVL Tree

Untuk delete pada AVL Tree hampir sama dengan Delete pada BST, tapi karena untuk menghapus node juga dapat menyebabkan tree menjadi tidak seimbang, jadi untuk itu pada Delete juga digunakan konsep Single Rotation dan Double Rotation.

Contoh :

Sumber :

http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html
PPT Binus AVL Tree