AVL Tree

AVL Tree merupakan bentuk BST yang lebih rumit. Syarat – syaratnya selain pertimbangan besaran value seperti BST dimana yang lebih kecil ke kiri serta yang lebih besar ke kanan, AVL Tree juga mempertimbangkan height dan balance.

Height adalah ketinggian atau kedalaman tingkat seperti lantai pada node. Height dari sebuah node adalah height maksimal dari anak – anaknya ditambah 1. 

Sedangkan balance adalah nilai yang didapat dari pengurangan height kiri dengan height kanan. Balance pada AVL hanya boleh 0 atau 1, tidak boleh lebih atau kurang, jika terjadi violation maka harus dirotate.

AVL berguna untuk memudahkan pencarian daripada BST karena syarat terurutnya lebih banyak, pencarian dapat dilakukan dengan cepat menggunakan AVL.

Syarat insert adalah:

1.    Jika node lebih kecil daripada root maka akan bergerak ke kiri, jika lebih besar maka ke kanan (seperti pada BST).

2.      Balancing

-        Kasus 1: node terbawah terletak di subtree kiri dari left child root (left – left rotation).

-        Kasus 2: node terbawah terletak di subtree kanan dari right child root (right – right rotation).

-        Kasus 3: node terbawah terletak di subtree kanan dari left child root (left – right rotation).

-        Kasus 4: node terbawah terletak di subtree kiri dari right child root (right – left rotatioin).

Untuk kasus 3 dan 4 perlu dilakukan rotate sebanyak 2 kali.

Code sama persis seperti BST, hanya ditambahkan pengecekan balancing dan rotate. Untuk rotate kek kiri, codenya adalah sebagai berikut.

Syarat delete adalah:

1.      Ambil anak node dari kiri yang terbesar atau anak node dari kanan yang terkecil (seperti pada BST).

2.      Hapus lalu lakukan balancing, jika belum balance maka rotate.