Rangkuman Struktur Data 6

AVL TREE

AVL Tree adalah BST yang memiliki perbedaan level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree berfungsi untuk menyeimbangkan(balance) BST. Dengan adanya AVL Tree, waktu pencarian dapat dipersingkat dan bentuk tree dapat disederhanakan.

Contoh AVL Tree:

Insertion dalam AVL Tree

Setiap penambahan sebuah node ke AVL Tree harus dilakukan pemeriksaan dari node baru ke root. Node pertama yang memiliki balance factor lebih dari 1 diseimbangkan. Proses penyeimbangan dibagi menjadi 2, yaitu Single Rotation dan Double Rotation.

Single Rotation

• Left Rotation

• Right Rotation

Double Rotation

• Left-Right Rotation

   Sebuah node dimasukkan ke subtree kanan dari subtree kiri.

  Lakukan left rotation pada subtree kiri dari node C. A menjadi subtree kiri dari B.

  Node C masih belum seimbang karena subtree kiri dari subtree kiri.

  Lakukan right rotation sehingga B menjadi root, C menjadi subtree kanan dari subtree kirinya.

 Tree menjadi seimbang.

• Right-Left Rotation

   Sebuah node dimasukkan ke subtree kiri dari subtree kanan.

  Lakukan right rotation pada node C. C menjadi subtree kanan dari subtree kirinya. B menjadi subtree kanan dari A.

   Node a masih belum seimbang.

 Lakukan left rotation sehingga B menjadi root, A menjadi subtree kiri dari subtree kanan nya.

 Tree menjadi seimbang.

Deletion dalam AVL Tree

Deletion dalam AVL Tree mirip dengan BST, hanya perlu diperhatikan keseimbangan tree seperti dalam insertion. Lakukan single atau double rotation setiap ada ketidakseimbangan.

GUEST LECTURE

Guest lecture: Selvakumar Manickam dari University of Science, Malaysia.

Guest lecture menjelaskan tentang Tree, BST, serta keektifannya.