AVL TREE

AVL TREE

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi atau level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Contoh AVL Tree: 

ntuk menjaga tree tetap seimbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru -> root. Node pertama yang memiliki[balance factor]>1 diseimbangkan. proses penyeimbangan dilakukan dengan: Single rotation dan double rotation.

terdapat 4 kasus tidak balance, yaitu:

1. Node yang terdalam terletak di sebelah left subtree dari left child node T (LL)

2. Node yang terdalam terletak di sebelah right subtree dari right child node T (RR)

3. Node yang terdalam terletak di sebelah left subtree dari right child node T (LR)

4. Node yang terdalam terletak di sebelah right substree dari left child node T (Rl)

terdapat 2 cara penyelesaian:

- Single Rotation (Kasus 1 & 2)

- Double Rotation (kasus 3 & 4)

Single Rotation

Single rotation dilakukan apabila searah, keft-left atau right-right

gambaran single rotation

Double Rotation

Double rotation dilakukan apabila searah, left-right atau right-left.

gambaran Double Rotation 

                                  Step 1(Rotasi pertama)

                               kasus diatas adalah left-right

                                    Step 2(Rotasi kedua)

                                    kasus diatas, left-left

Delete AVL TREE

Deletion dalam AVL Tree sama seperti teknik deletion dalam binary search tree yang tidak seimbang.

Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan yaitu :

1.      Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.

2.      Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.

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)

Contoh: