-

AVL TREE

AVL Tree hampir sama dengan BST atau yang sering kita sebut Binary Search Tree. Dalam AVL Tree memiliki syarat atau ciri khas yaitu memiliki perbedaan tinggi/ level maksimal 1 antara anak kiri dan anak kanan. AVL Tree digunakan untuk membuat balance saat sedang lakukan penambahan node baru atau menghapus sebuah node. Kita dapat mencari balance factor dengan cara menghitung selisih panjang anak kiri dikurang dengan panjang anak kanan. Apabila tidak memiliki anak dianggap 0.

Insert node

Untuk menambahkan sebuah node baru ke dalam tree harus dilakukan pengecekan dimulai dari ujung leaf hingga root. Node pertama yang merusak atau memiliki balance factor lebih dari 1 maka akan diseimbangkan dengan Single Rotation atau Double rotation.

Single rotation

Single rotation dilakukan sekali ketika kondisi AVL Tree saat ditambahkan node baru dan posisi node tersebut seperti gambar dibawah ini:
Gambar yang kiri tidak balance karena balance factor dari 30 lebih dari 1 sehingga kita harus melakukan pemeriksaan dari bawah atau leaf yang tidak sesuai kriteria AVL Tree. Gambar yang kanan sudah balance dengan melakukan right rotation. Balance factor boleh =0.


Double rotation 

Double rotation yaitu rotasi yang dilakukan 2 kali karena rotasi yang pertama belum sepenuhnya sesuai dengan kriteria AVL Tree.


Rotasi pertama dilakukan karena balance factor yang mengarah ke node baru lebih dari 1 yaitu 2. Sehingga melakukan pemeriksaan terhadap node yang merusak dan dilakukan rotasi pertama.




Rotas kedua dilakukan karena balance factor yang mengarah ke node baru lebih dari 1 yaitu masih 2. Sehingga melakukan pemeriksaan terhadap node yang merusak dan tree secara keseluruhan menjadi balance.

Delete node 

Delete node dalam AVL Tree hampir sama dengan BST. Dengan menghapus sebuah node dapat membuat tree menjadi tidak balance sehingga harus dilakukan pengecekan dari node yang dihapus hingga ke root. Untuk membalance kembali dapat menggunakan single rotation atau double rotation. Contoh: ( menghaput node 60 )




Dilakukan rotasi pertama karena balance factor yang mengarah ke leaf 42 lebih dari 1 yaitu 2. Agar tree balance makan dilakukan left rotation terlebih dahulu.



Dilakukan rotasi kedua karena balance factor yang mengarah ke leaf 10 lebih dari 1 yaitu 2. Sehingga dilakukan right rotation agar secara keseluruhan tree seimbang atau balance.

Nama : Dewi Mutiara
NIM : 2301887830
Kelas : CB01

Komentar

Posting Komentar

Postingan populer dari blog ini

-
Gambar
Hashing table & Binary Tree Hashing Hash Table Hash Function Collision  Tree Concept Binary Tree Concept Type of Binary Tree Property of Binary Tree Expression Tree Concept Threaded Binary Tree Concept 1. Hashing Hashing adalah proses menghasilkan data keluaran (output data) yang panjangnya tetap dan sama, dari data masukan (input data) yang panjangnya berbeda-beda. Hashing adalah bentuk akses data yang efisien secara komputasi dan ruang penyimpanan yang menghindari waktu akses non-linear dari daftar dan pohon terstruktur yang dipesan dan tidak tersusun, dan persyaratan penyimpanan yang sering eksponensial untuk akses langsung ruang negara dari kunci besar atau panjang variabel. 2. Hash Table Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.  Keunggulan dari struktur hash ta...
Baca selengkapnya
-
Gambar
Linked list dalam Data Structure Linked List saling terhubung dengan bantuan variabel pointer. Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field. Single  : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL. Linked List  : artinya node-node tersebut saling terhubung satu sama lain. Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list. J enis Single LinkList : Single linked list dengan HEAD Single linked list dengan HEAD dan TAIL  Pembuatan Single Linked List  Keyword new gunanya untuk mempersiapkan sebuah node baru berserta alokasi memorinya, kemudian node t...
Baca selengkapnya