AVL TREE





AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi antara subtree kiri dan subtree kanan. AVL Tree digunakan untuk menyeimbangkan Binary Search Tree, sehingga waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. 

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
anggap T adalah node yang harus diseimbangkan kembali

- 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)

Proses penyeimbangan dalam AVL TREE

1. Single Rotation 
Dilakukan bila kondisi AVL tree ditambahkan node baru. Dimana T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian sama dengan height-nya (≥ 0).  Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image).


 

2. Double Rotation 
Double rotation dilakukan bila kondisi AVL tree  ditambahkan node baru. Dimana T1, T2, T3, dan T4 adalah subtree yang urutannya harus seperti demikian. Tinggi subtree T1 harus sama dengan T4 (≥ 0), tinggi subtree T2 harus sama dengan T3 (≥ 0). Node yang ditambahkan akan menjadi child dari subtree T2 atau T3. Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image).

  

 Deletion AVL

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.
delete node 60

node 55 tidak seimbang, karena anak kiri 0 dan anak kanan 2, selisih 2.
diseimbangkan dengan single rotation (left-left) karena 55 ke 65 kiri dan 65 ke 70 kiri
akan tetapi, node 50 menjadi tidak seimbang, di subtree kiri 4 dan subtree  kanan 2

diseimbangkan dengan double rotation (left-right) karena dari 50 ke 25 kiri dan 25 ke 40 kanan

AVL yang sudah balance



sumber : 
https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/
http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html
http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html

Komentar

Posting Komentar

Postingan populer dari blog ini

Heap and Tries

Gambar
Heap Heap adalah complete binary tree berdasarkan struktur data yang memenuhi properti heap. Tujuan dari heap ini adalah untuk menemukan nilai terkecil pada min heap dan nilai terbesar pada max heap.  mempunyai properties sebagai berikut: Min Heap Setiap node lebih kecil dari masing-masing childnya Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf no         Find-Min Minimum node terletak pada root         Insertion    Insert node selalu berurutan dari level paling rendah dengan urutan left ke right New node selalu menjadi leaf node Sesuikan sesuai heap properties secara rekursif           Deletion-Min pada Min-Heap Node yang dihapus selalu root karena merupakan node paling kecil, lalu diganti dengan node yang paling terakhir di insert Sesuaikan dengan heap properties secara rekursif         Max Heap Setiap node lebih besar dari masing-masing childnya Root merupakan node paling besar, sedangkan node terkecil terletak pa
Baca selengkapnya
Gambar
Stack and Queue 1.  Stack Stack   atau tumpukan dapat diartikan sebagai suatu kumpulan data yang seolah-olah terlihat seperti ada data yang diletakkan di atas data yang lain. Kaidah utama dalam konsep  stack  adalah LIFO yang merupakan singkatan dari  Last In First Out,  artinya adalah data yang terakhir kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan. Operasi pada Stack  : Operasi  push , berfungsi memasukkan sebuah nilai atau data ke dalam  stack . Sebelum itu, nilai atau data dimasukkan ke dalam stack , dengan cara menaikkan posisi  top  satu  level  ke atas. ilustrasi kerja pada operasi  push : Gambar 3.2  Ilustrasi kerja operasi  push Operasi  pop , berfungsi umengeluarkan atau menghapus nilai terakhir (yang berada pada posisi paling atas) dari  stack , dengan cara menurunkan nilai  top  satu  level  ke bawah. Berikut ilustrasi kerja pada operasi  p op : Gambar 3.3  Ilustrasi kerja op
Baca selengkapnya
Gambar
STRUKTUR DATA - Linked List Linked List Linked List (senarai berantai) adalah struktur data yang terdiri dari urutan record data. Dimana setiap recordnya memiliki field untuk menyimpan alamat/referensi dari record selanjutnya. Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.  Head adalah elemen yang berada pada posisi pertama dalam suatu linked list Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list Macam - Macam Linked List      1.  Singly Linked List :      Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya dan juga memiliki field yang             berisi data.  Pembuatan Single Linked List dapat menggunakan 2 metode: ·          LIFO (Last In First Out), aplikasinya : Stack (Tumpukan) ·          FIFO (First In First Out), aplikasinya : Queue (Antrean) 2.  Double Linked List adalah linked list dengan men
Baca selengkapnya