Rangkuman Data Structure Week 6

Rangkuman AVL TREE

Nama : Julian Andhika Diputra

NIM : 2301858023

 AVL Tree adalah sebuah self-balancing binary tree yang pertama kali dibuat. Self-balancing binary tree adalah salah binary tree yang bisa membalance dirinya sendiri. Sebuah binary tree yang balanced tidak boleh memiliki subtree yang lebih besar daripada subtree yang lain lebih dari 1. Dalam binary tree ada yang disebut balanced factor. Balanced factor adalah hal yang menunjukkan berapa perbedaan antara subtree kiri dan subtree kanan.

Berikut dapat dilihat bahwa pada node 17, AVL mengalami kesalahan karena di subtree kanan terdapat 2 depth, sedangkan di subtree kiri terdapat 1 depth yang menyebabkan ketidak-seimbangan. Hal ini dapat kita benarkan dengan melakukan rotation.

Single Rotation

Single rotation adalah aksi melakukan rotasi di salah satu node sehingga node tersebut dapat menjadi seimbang.

Dari contoh tersebut, kita dapat melihat ketika kita ingin menambah node 12, terdapat ketidak-seimbangan. Oleh sebab itu kita melakukan rotation terhadap node ke 30 dan node ke 22. Hal ini menyebabkan node ke 30 menjadi subtree kanan dan node ke 22 menjadi root. Anak dari node ke 30 pun tetap menjadi subtree di kanan, sedangkan anak kanan dari node ke 22 menjadi anak dari 30 subtree kiri.

Double Rotation

Double rotation dilakukan ketika ketidak-seimbangan terjadi tetapi bukan garis lurus dari root. 

Contohnya disini terdapat ketidak seimbangan dari subtree kiri dan subtree kanan, tetapi ketidakseimbangannya tidak lurus. Oleh sebab itu, kita dapat melakukan single rotation dulu pada node ke 22, sehingga node ke 27 menjadi root dari subtree kiri. Setelah itu lakukan rotation lagi dari node 27 dan 30 sehingga seimbang.

Deletion

Deletion dilakukan seperti biasa, yaitu adalah melakukan pergantian dengan node paling kiri yang paling kanan atau anak kanan yang paling di kiri, tetapi jika setelah didelete terdapat ketidak-seimbangan maka harus dilakukan rotasi.