DATA STRUCTURE AVL TREE

DATA STRUCTURE AVL TREE

AVL TREE adalah Binary search tree yang memiliki perbedaan Node / Jumlah tingkatan atau level pada  Subtree kanan/kirinya sebanyak 1. AVL Tree ditemukan oleh Georgy Adelson Velski dan Evgenii Landis pada tahun 1962.

Contoh dari AVL TREE =

Data yang tidak seimbang akan diseimbangkan dengan proses penyeimbangan yang disebut dengan Single rotation dan Double rotation.

SINGLE ROTATION

Rotasi penyeimbangan yang dilakukan sekali untuk menyeimbangkan AVL tree agar menjadi bentuk yang seimbang.

CONTOH = 

Sumber = https://raw.githubusercontent.com/HebleV/valet_parking/master/images/avl_left_rotation.jpg

Bisa dilihat pada gambar di atas terdapat data AVL tree yang tidak balance karena di bagian kiri dan kanannya tidak stabil. Di sini Proses single rotation dilakukan dengan Memutar data yang tidak balance tersebut yang pada kasus di atas adalah B sehingga data menjadi balance dan tidak ada lagi yang jumlah yang lebih baik di kiri atau kanannya.

DOUBLE ROTATION 

Rotasi penyeimbangan yang dilakukan 2 kali untuk menyeimbangkan AVL tree agar menjadi bentuk yang simbang. 

CONTOH = 

SUMBER = https://image.slidesharecdn.com/l3-140202101439-phpapp01/95/binary-search-trees-avl-and-red-black-26-638.jpg?cb=1391344462

Pada gambar di atas Terdapat data yang tidak balance dan harus di selesaikan dengan Double rotation.

AVL TREE DELETE

Delete dalam AVL tree adalah Operasi penghapusan Node dalam binary search tree. Node yang dihapus akan digantikan oleh NODE terbesar pada subtree di kiri / NODE terkecil pada Subtree di kanan.