Data Structure - AVL Tree

Data Structure

Pada pertemuan ini, kami membahas Balanced Binary Search Tree. Balanced Binary Search Tree adalah sebuah BST yang diminimalisasi height atau levelnya , untuk memudahkan pencarian dan menghemat waktu saat mencari node yang dicari . Balanced Binary Search Tree terdapat 2 macam (dalam matkul ini), yaitu AVL dan Red Black Tree . Pada pertemuan ini, kami hanya membahas AVL dan kami kedatangan Guest Lecture, Selvakumar Manickam, Senior Lecture of University Science of Malaysia .

AVL

AVL merupakan Balanced Binary Search Tree pertama yang ada . AVL merupakan sebuah singkatan dari penemu Balanced Binary Search Tree ini .

Contoh:

Note:

·         h-n merupakan height dari tree tersebut ke n

·         b-n merupakan balanced tree tersebut , dimana kita dapat menghitung dengan cara :

Height anak kiri – Height anak kanan

Hasilnya hanya ada 3 kemungkinan , yaitu -1, 0, 1

Jika hasilnya:

-1: Maka tree tersebut lebih berat ke kiri, tetapi masih balanced

 0: Maka tree tersebut balanced

 1: Maka tree tersebut lebih berat ke kanan, tetapi masih balanced

Dalam AVL tree terdapat 2 jenis , yaitu :

1.       Single Rotation

Contoh :

Right-Right

Left-Left

2.       Double Rotation

Contoh:

Operation dalam AVL ada 3 , yaitu Insertion,Deletion, dan Searching . tetapi searching sudah termasuk dalam 2 operation lainnya . Sekarang kita akan membahas mengenai Insertion.

Insertion dalam AVL tree sama seperti BST, namun setiap stepnya kita harus mengecek dan menghitung kembali height dan balanced factornya . Jika balanced factornya tidak memenuhi persyaratan maka disebut violation. Setiap ada violation maka kita harus membuat tree tersebut itu blanced kembali .

Contoh:

Deletion

Dalam sesi Guest Lecture, kami membahas materi yang saya pernah tulis di blog ini, silahkan cek ya. Sesi 1 Sesi 4 Sesi 5 .