AVL Tree

Nama: Bryan Frederick

NIM : 2301871984

AVL Tree

AVL Tree adalah binary search tree yang diseimbangkan, maksudnya diseimbangkan jadi dalam binary tree itu ada namanya perbedaan tinggi, nah untuk perbedaan tinggi ini untuk avl tree maksimalnya 1, jadi boleh 1 atau 0. tapi apa yang akan terjadi jika 2? nah itu yang akan diibahas. tapi sebelum itu kita harus tau bahwa prinsip binary tree itu memiliki anakan 2.

jadi ini contoh gambar binary tree yang tidak simetris.

Nah dapat diperhatikan dalam gambar ini bahwa binary tree ini belum termasuk avl tree karena ada tinggi yang 2, jadi ketinggian yang dimaksud dapat dilihat anakannya, pada node 17 anakan sebelah kirinya ada 2 yaitu 14 dan 16 dan sebelah kanan tidak ada, maka ketinggiannya 2-0 = 2. Nah ini perlu diperbaiki.

Dalam memperbaiki ini ada 2 jenis perbaikan yang dapat dilakukan yaitu single rotation dan double rotation.

Contoh ini ada kasus :

Dapat dilihat bahwa node 30 tidak seimbang maka ini harus diperbaiki, bagaimana kita tahu bahwa ini menggunakan single rotation, caranya lihat garis biru itu, garis itu menandakan bahwa yang tidak seimbang merupakan garis lurus tidak bengkok berarti itu bisa menggunakan single rotation. Jadinya seperti ini.

Nah ini anggap 30 jadi poros lalu ditarik ke kanan, maka otomatis 30 jadi sebelah kanannya 22 dan sebelah kanan 22 dianggap dimasukkan ulang menjadi demikian.

Lalu double rotation bagaimana, kalua single dapat dipakai karena lurus maka jika ada bengkokan maka kita gunakan double rotation. Contoh:

Nah ini bengkokannya ada pada node 22 yaitu kearah kanan, maka

Yang menjadi poros pertama adalah node 22 yang ditarik ke sebelah kiri maka node 27 menjadi poros baru setelah itu.

Nah lalu putaran kedua yaitu porosnya ada pada node 30 sehingga ditarik ke sebelah kanan.

Untuk node yang berwarna hijau itu sebetulnya yang mempengaruhi ketidak seimbangan tree tersebut.

Demikian materi AVL yang dapat saya sampaikan.

Sumber: binusmaya resources