Data Structure AVL Tree

AVL TREE

AVL Tree Mirip dengan BST ( Binary Search Tree) Bedanya adalah didalamnya memiliki perbedaan ketinggian antara subtree kiri dan subtree kanan dari node 0 atau yang sama dengan 1.

Insertion

Ada 4 kasus yang biasanya terjadi saat operasi insert di AVL Tree dilakukan, yaitu :
– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri N (left-left)
– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan N (right-right)
– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri N (right-left)
– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan N (left-right)

( N = Node)

Cara menyelesaikan Masalah pada AVL Tree ada 2, yaitu :

1. Single Rotation

2. Double Rotation

• Single Rotation

Single rotation dilakukan bila kondisi AVL Tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut ini

• Double Rotation

Double rotation dilakukan bila kondisi AVL Tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar berikut ini

Deletion

Ada 4 langkah yang bisa dilakukan pada beberapa kasus di AVL Tree, yaitu :

Langkah 1: Menemukan bahwa node mana k disimpan
Langkah 2: Menghapus isi dari node (Misalkan node N)
Langkah 3: Menghapus node dalam pohon AVL dapat dikurangi dengan menghapus daun.

Langkah 4: ketika N memiliki dua anak, Temukan penerus N M (yang tidak memiliki anak kiri)
                   kemudian ganti isi N dengan isi M, dan Hapus M.