Pada pertemuan ke-6, kelas Data Structure kami menjadi 2 shift, karena kedatangan guest lecturer dari malaysia, yaitu Mr. Selvakumar Manickam.

Ada 2 jenis balanced binary tree yang lebih dikenal, yaitu:

–>AVL Tree

–>Red Black Tree

AVL TREE

AVL merupakan kependekan dari nama penemu AVL Tree, yaitu G.M Adelson-Veleskii dan E.M Landis pada tahun 1962.

Konsep dari AVL Tree ada 4, yaitu:

1. Height dari sub-tree yang kosong adalah 0.
2. Height dari leaf adalah 1.
3. Height dari internal node (node yang ada di bagian dalam tree) adalah height maksimum dari anaknya ditambah 1.
4. Balance factor (selisih dari height sub tree kiri dan height sub tree kanan) tiap node maksimum adalah 1.

Gambar di atas bukan termasuk AVL Tree karena selisih nya 2, sedangkan AVL Tree Maksimal selisih 1

Terdapat 2 operasi pada AVL Tree, Yaitu :

–> Insertion

–> Deletion

Cara Insertion : Menambahkan node, lalu menghitung height dan balance factor tiap node untuk menemukan AVL Violation. jika trees yang sudah di insertion belum balance, harus me-rebalance tree lagi.

Ada 4 kasus yang biasanya terjadi pada saat insertion AVL Tree, yaitu :

–> Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)

–> Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)

–> Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)

–> Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

*Kasus 1 dan Kasus 2 adalah singel rotation

*Kasus 3 dan Kasus 4 adalah double rotation

Contoh Kasus 1 :

Contoh Kasus 2 :

Contoh Kasus 3 dan 4 :

Cara Deletion : Node yang telah hapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja.

Step 1

Step 2

Step 3

Step 4

Pada Shift ke 2, kami di ajarkan oleh Mr. Selvakumar Manickam dari Malaysia, beliau mengajarkan Kami diajarkan banyak tentang AVL Tree, m-ary trees, binary tree dan binary search tree, kompleksitas pada tiap tree kepada kami.

www.binus.ac.id

www.skyconnectiva.com