Data Structures: AVL tree

Materi Data Structure 28 April 2020

Hal yang akan dibahas pada pertemuan kali ini :
1. AVL tree concept
2. Rebalance AVL Tree

1. AVL tree concept

Pada AVL tree kita harus memperhatikan balance factor tiap node yang ada pada tree tersebut. Balance factor pada tiap node di dalam tree tidak boleh kurang dari -1 dan tidak boleh lebih dari 1. Cara untuk mendapatkan balance factor yaitu dengan menggunakan rumus

balance factor = jumlah path terpanjang anak kiri - jumlah path terpanjang anak kanan.

Cara untuk menginsert data dan untuk mendelete data pada AVL tree ini sama seperti cara untuk menginsert data dan mendelete data pada Binary Search Tree. Akan tetapi dikarenakan tree pada Binary Search Tree memungkinkan terjadinya suatu ketidak seimbangan tree, maka diciptakannyalah AVL tree, yang bertujuan untuk menyeimbangkan tree pada Binary Search Tree.

2. Rebalance AVL tree
Dikarenakan Binary Search Tree memiliki kemungkinan terjadi ketidak seimbangan pada tree, maka setiap kali kita menginsert data ataupun kita mendelete suatu data, kita harus seimbangkan treenya dengan menggunakan AVL tree, dengan cara menggunakan rumus balance factor.

Terdapat 2 kasus pada saat kita merebalance avl tree yaitu :
1. single rotation
ada 2 kemungkinan kasus yang harus diselesaikan dengan single rotation yaitu:
1. the deepest node is located at the left sub tree of the child of T
contoh :

pada tree seperti itu kita harus melakukan rebalancing dengan cara LL rotation

2. the deepest node is located at the right sub tree of the child of T

contoh:

pada tree seperti itu kita harus melakukan rebalancing dengan cara RR rotation

2. double rotation
ada 2 kemungkinan kasus yang harus diselesaikan dengan double rotation
1. the deepest node is located at the right sub tree of the left child of T
contoh :