DATA STRUCTURE

AVL TREE

Pada blog sebelumnya , kita sudah mempelajari mengenai Binary Search Tree (BST)secara umum. Tapi kalian tau gak sih kalo ada kelemahan pada BST? Kelemahannya adalah kalau BST di input oleh user secara incremental atau decremetal bentuknya akan berurutan dan menjadi tidak seimbang.

Nah karena kelemahannya itulah ada yang diciptakanlah AVL Tree yaitu BST yang di seimbangkan. AVL Tree adalah BST yang memiliki perbedaan tinggi atau level maksimal 1 antara subtree kiri dan subtree kanan. Dengan adanya AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Berikut adalah contoh BST yg unbalanced (kanan) dan Tree yang balanced (kiri) dengan AVL.

Biasanya pada saat user melakukan insertion pada sebuah tree, terjadi ketidakseimbangan. Ketidakseimbangan itu bisa diatasi dengan melakukan rotasi (rotation) pada node dalam AVL tree. Ada 2 jenis rotasi pada AVL Tree yaitu :

· Single Rotation (Left Rotation, Right Rotation)

· Double Rotation (Left – Right Rotation, Right – Left Rotation)

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
anggap T adalah node yang harus diseimbangkan kembali

Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)