AVL Tree

• AVL Tree

AVL Tree Adalah Balanced Binary Search Tree, karena mengikuti aturan BST. Kata "Balanced" mengacu pada panajng/kedalaman BST dimana kita menghindari "Skewed Binary Tree". oleh karena itu, akan ada "Balanced Factor" untuk menunjukan apakah BST memenuhi AVL Tree. Pohon AVL dianggap seimbang ketika faktor keseimbangan (BF) adalah : -1, 0, +1. ketika BF mencapai -2 atau +2, itu berarti Rotasi harus dilakukan untuk memastikan bahwa pohon mendapatkan kembali keseimbangannya. Bagaimana cara melakukannya?

Pertama-tama kita harus mengetahui sistem Rotasi pada AVL. AVL memiliki dua jenis rotasi yaitu Single Rotation & Doubel Rotation.

• Single Rotation AVL

Gambar ini adalah BST pada umumnya.

Gambar ini adalah BST yang menggunakan AVL Tree.

Bagaimana cara kerjanya? Berikut adalah cara kerja dari Single Rotation AVL.

Disini kita bisa lihat bahwa 72 memiliki kedalaman yang tidak seimbang antara anak kiri dan anak kanan. seperti pada aturan jika kedalaman yang dimiliki parent > 1 maka harus di rotasi. Pada kasus ini kita bisa melihat bahwa anak dari parent yang berlebihan rata sebelah kiri jadi kita bisa langsung menjalankan konsep dari Single Rotation AVL. Cara kerja dari rotasi AVL ini seperti cara kerja katrol yang bisa ditarik kekiri ataupun ke kanan.

• Double Rotation AVL

Ini adalah gambar BST dari contoh Double Rotation.

BST ini diselesaikan dengan doubel rotaion karena anak dari parentnya tidak sejajar sehingga harus di rotasi 2 kali.

Pada step 1 dilakukan rotasi ke kiri pada 54 sehingga 63 menjadi parent dari 54, selanjutnya pada step 2 di lakukan rotasi ke kanan pada 72 sehingga 63 menjadi parent dari 72 dan 54 lalu anak dari 63 di input lagi sehingga berada pada parent 72 sebelah kiri.

sehingga BST menjadi balanced.