Blog untuk Tugas

Nama: Wilson Nursalim
NIM: 1901516495

Rangkuman Pertemuan 6

www.binus.ac.id
www.skyconnectiva.com

Bila height dari suatu Tree makin besar, maka makin lama pula waktu yang diperlukan untuk insertion, searching, dan deletion. Karena itulah kita ingin membuat Tree dengan height sekecil mungkin. Tree yang demikian adalah Balanced Binary Search Tree.

AVL Tree

(ditemukan oleh Adelson-Veleskii and E.M. Landis)

Height dari suatu node:

• Height dari sebuah empty sub tree adalah 0.
• Height dari sebuah leaf adalah 1.
• Height dari node lainnya adalah height paling besar dari anaknya ditambah dengan 1.

Balance Factor:  Selisih height anak sebelah kiri dengan anak sebelah kanan.

<NOTE> : Pada AVL Tree, Nilai  balance factor paling besar yang diperbolehkan adalah 1.

Contoh AVL Tree
(berikut dengan height & balance factor dari tiap nodenya)

Ketika kita memasukkan node baru ke AVL Tree, balance factor dari node lainnya bisa berubah menjadi lebih dari 1. Ketika terjadi violation seperti ini, kita perlu menyeimbangkan kembali Tree dengan melakukan rotasi.

Single Rotation

digunakan ketika:

• Node baru dimasukkan ke left sub-tree of the left child of the node that must be rebalanced (LL rotation)
• Node baru dimasukkan ke right sub tree of the right child of the node that must be rebalanced. (RR rotation)

CONTOH:

   LL rotation

Double Rotation

digunakan ketika:

• Node baru dimasukkan ke right sub tree of the left child of the node that must be rebalanced (LR rotation)
• Node baru dimasukkan ke left sub tree of the right child of the node that must be rebalanced. (RL rotation)

CONTOH:

LR rotation

Deletion dari suatu node pada AVL Tree juga dapat menyebabkan violation (ketika ada node yang balance factornya lebih dari 1). Tree dapat diseimbangkan kembali dengan menggunakan rotation seperti pada insertion.

Lecture tambahan dari dosen tamu

Click the picture to zoom in

 Tabel di atas menunjukkan perbandingan keefektifan dari tiap data structure.
Menurut dosen tamu, secara keseluruhan Tree merupakan data structure yang paling baik.