---

---

BALANCED BINARY TREE

Salah satu Balanced Binary Tree adalah AVL. AVL itu sendiri adalah jenis binary tree yang memiliki balance factor atau perbedaan level / tinggi nya tidak boleh melebihi 1 antara substree kiri dan kanannya. Manfaat atau tujuan dari AVL tree itu sendiri adalah menyeimbangkan binary search tree agar lebih mudah proses pencarian / searching nya.

Konsep AVL Tree :

1. Height dari sub tree yang kosong adalah 0.
2. Height dari leaf adalah 1.
3. Height dari internal node adalah max height dari anaknya + 1.

Balance Factor :

1. Perbedaan height dari subtree kiri dan kanan.
2. Selisih ketinggian hanya boleh bernilai 1 / 0.

Menyeimbangkan AVL membutuhkan salah satu atau 2 dari 2 proses rotation.

Single Rotation

Double Rotation 

Ada 2 proses dalam AVL yaitu insertion dan deletion.

INSERTION

Insert biasa seperti binary tree namun selalu cek balance factornya setiap kali insert, jika tidak memenuhi ketentuan AVL, maka lakukan penyeimbangan dengan single atau double rotation tergantung kondisi.

DELETION

Delete biasa seperti binary tree dengan 3 kondisi, delete leaf, delete parent 1 anak, delete parent 2 anak, lalu cek balance factornya, jika tidak memenuhi ketentuan AVL, maka lakukan penyeimbangan dengan single atau double rotation tergantung kondisi.

---

---

 

No Comments »

No comments yet.

RSS feed for comments on this post. TrackBack URL

Leave a comment

Name (required)

Mail (will not be published) (required)

Website