AVL Tree

AVL Tree

Pada materi kali ini kita akan membahas AVL Tree, pada dasarnya Avl Tree ini mirip dengan BST(Binary Search Tree) hanya saja pada AVL Tree kita perlu menyeimbangkan cabang setiap nodenya.

Pada AVL, perbedaan kedalaman cabang kiri dan kanannya tidak boleh lebih dari 1. Selama dibawah 2 masih diperbolehkan.

Contoh:

Tree diatas bukan merupakan AVL Tree, dikarenakan node 12 kiri dan kanan perbedaannya lebih dari 1. Pada cabang kiri 12 kedalamannya adalah 4, sedangkan yang kanan hanya 2. Perbedaannya yaitu 4-2 = 2 (lebih dari 1).

Contoh pada AVL Tree kali ini, node yang menjadi masalah adalah node 10. Karena setelah dimasukkan angka 3 otomatis cabang kiri dari node 10 akan menjadi lebih berat. Oleh karena itulah dilakukan rotation ke kanan agar cabang kiri dan kanannya seimbang kembali.

Pada gambar ini node 30 lah yang menjadi permasalahan karena cabang kanannya lebih berat, sehingga dilakukan rotation ke kiri seperti digambar.