AVL TREE

AVL Tree

AVL Tree merupakan tree yang menyempurnakan BST (Binary Search Tree) dari segi kecepatan dalam proses Insertion, Deletion, dan Searching. Jika kita menggunakan BST untuk banyak data yang mencapai ribuan atau ratus ribu dan seterusnya, tentu akan membutuhkan waktu yang lama  untuk proses dikarenakan level yang amat dalam.

AVL Tree sendiri merupakan Binary Search Tree (BST) yang hanya memiliki perbedaan height (tinggi) 1 antara subtree kiri dan subtree kanan. Dengan adanya penyeimbangan ini, pencarian data akan semakin cepat dilakukan. Dalam menyeimbangkan node, dikenal istilah yang bernama Balance Factor sebagai penanda yang jika melebihi aturan AVL Tree akan dilakukan Rotation.

AVL Tree mempunyai aturan yang tidak boleh dilanggar di mana Balance Factor harus mempunyai nilai -1, 0, dan 1. Tidak boleh kurang atau lebih dari nilai tersebut. Jika lebih, harus diseimbangkan kembali dengan melakukan Rotation. Balance Factor dapat ditentukan dengan:

                     Balance Factor = Height of Left Subtree - Height of Right Subtree

Berikut adalah contoh dari AVL Tree. Kita dapat melihat jika Balance Factor nya tidak melebihi -1, 0, dan 1 yang artinya Tree ini merupakan AVL Tree.

INSERTION : AVL TREE

Terdapat 4 kasus penambahan node baru (insert) yang seringkali menyebabkan Tree menjadi tidak seimbang, di antaranya:

1.  Left-Left (LL)

Node terdalam terletak pada subtree bagian kiri dari anak kiri T (node yang harus diseimbangkan).

2. Right-Right (RR)

Node terdalam terletak pada subtree bagian kanan dari anak kanan T (node yang harus diseimbangkan).

3. Right-Left (RL)

Node terdalam terletak pada subtree bagian kanan dari anak kiri T (node yang harus diseimbangkan).

4. Left-Right (LR)

Node terdalam terletak pada subtree bagian kiri dari anak kanan T (node yang harus diseimbangkan).

DELETION : AVL TREE

Terdapat 2 kasus yang biasanya terjadi ketika melakukan penghapusan (delete) node, di antaranya:

1. Jika node yang berada di posisi paling bawah (leaf), node akan dapat langsung dihapus.

2. Jika node yang akan dihapus memiliki anak, harus dicek kembali apakah setelah penghapusan node tree akan menjadi tidak seimbang atau tidak. Pengecekan penyeimbangan node ini sama seperti pada saat Insertion.  Jika tree menjadi tidak seimbang, maka harus diseimbangkan lagi.