AVL Tree

AVL Tree

AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisih satu).
contohnya:

cara menentukan Height dan balance factor:

- Jika node(root) tidak memiliki subtree heightnya = 0

    - Jika node adalah leaf, height = height tertinggi dari anak +1

Balance factor : 

- selisih height antara anak kiri dan kanan, jika tidak memiliki anak, dianggap 0.

Insertion

untuk 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

Deletion

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.

delete node 60

                                         

                           

node 55 tidak seimbang, karena anak kiri 0 dan anak kanan 2, selisih 2.
diseimbangkan dengan single rotation (left-left) karena 55 ke 65 kiri dan 65 ke 70 kiri
akan tetapi, node 50 menjadi tidak seimbang, di subtree kiri 4 dan subtree  kanan 2

diseimbangkan dengan double rotation (left-right) karena dari 50 ke 25 kiri dan 25 ke 40 kanan

berikut conoth AVL yang sudah balance

referensi: http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html\

                 http://tugasdatastruktur.blogspot.com/2016/05/pertemuan-6-avl-tree.html