Rangkuman Avl Tree

Avl Tree

Avl Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/level maks 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. Untuk menjaga Tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan node baru ke root. Node pertam yang memiliki balance factor > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan Single Rotation dan Double Rotation.

Single Rotation dilakukan bila kondisi Avl Tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar di bawah. T1, T2, T3 adalah subtree yang urutannya harus seperti demikian serta height harus sama >= 0.

Double Rotation dilakukan dengan kondisi Avl Tree waktu ditambahkan node baru dan posisi nya seperti gambar dibawah. Tinggi subtree T1 harus sama dengan T4, tinggi subtree T2 harus sama dengan T3. Node yang ditambahkan akan menjadi anak subtree T2 dan T3.

a) Left Left Case

T1, T2, T3 and T4 are subtrees.
         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

b) Left Right Case

     z                               z                           x
    / \                            /   \                        /  \ 
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

c) Right Right Case

  z                                y
 /  \                            /   \ 
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

d) Right Left Case

   z                            z                            x
  / \                          / \                          /  \ 
T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      y
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

Avl Tree

Insert : 5, 6, 7, 0, 4, 3, 8

Delete: 3, 4, 8

Insert 5

 Insert 6

 Insert 7

 Insert 0

 Insert 4

 Insert 3

 Insert 8

 Delete 3

 Delete 4

 Delete 8

Reference:

https://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html

https://www.geeksforgeeks.org/avl-tree-set-1-insertion/