Langsung ke konten utama

Struktur Data: AVL Tree

Struktur Data: AVL Tree

Apa itu AVL Tree? AVL Tree merupakan sebuah BST yang bisa menyeimbangkan dirinya sendiri antara kanan dan kiri. Seimbang di sini maksudnya perbedaan panjang antara kaki kanan dan kaki kiri tree nya tidak lebih dari 1. Contoh gambarnya seperti ini:


 Nah bisa diliat dari contoh gambar di atas kalo panjang kaki kiri dan kanan nya sama (sejajar). Itu yang disebut AVL Tree.


 Nah kalo gambar yang itu bukan AVL, kenapa? Karena kaki kiri nya kepanjangan!

 Terus kalo gitu gimana caranya AVL menyeimbangkan dirinya sendiri? Hayo gimana, kepo ya?

Jadi gini, si AVL itu bisa nyeimbangin dirinya sendiri dengan cara melakukan perputaran node di kaki yang terpanjang. Perputarannya sendiri terdiri dari 2 jenis, yaitu single rotation dan heavy double rotation.

Single Rotation

Single rotation akan dilakukan ketika kaki yang terpanjangnya memiliki arah yang lurus. Maksudnya gimana tuh? Jadi gini, liat gambar di bawah ini:


 Bisa diliat dari gambar di atas, kaki terpanjangnya ada di sebelah kiri. Nah dari root ke kaki paling bawah (angka 2) itu lurus aja garisnya, ga ada belokan sama sekali. Untuk menyeimbangkannya maka akan dilakukan single rotation dengan cara "menarik" node 8 ke kanan (seperti katrol) lalu memindahkan node 7 ke kirinya node 8. Jadinya ntar kaya gini pohonnya:

Double Rotation

Cara yang kedua ini dilakukan jika kaki terpanjang dari treenya belok kaya gambar kedua dari atas tadi yang node nya warna biru. Gimana caranya? Kalo ngikutin gambar itu, yang pertama dilakukan ialah dengan menukar posisi node 8 dengan node 9 (biar jadi lurus), terus akan dilakukan rotasi kedua sama di node 13. Jadinya kaya gini nanti hasil akhirnya:

Referensi


  • https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
  • http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html
  • https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
Label:

Komentar

Posting Komentar

Postingan populer dari blog ini

Struktur Data: Hash Table dan Binary Trees

Struktur Data: Hash Table dan Binary Trees Keduanya merupakan jenis-jenis struktur data yang dapat dibuat. Lalu, apa itu hash table dan binary trees ? 1. Hashing dan Hash Table Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data ( insertions ), penghapusan data ( deletions ), dan pencarian data ( searching ) relatif sama dibanding struktur data atau algoritma yang lain. Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value tersebut didapat hash value . Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan
2 komentar
Baca selengkapnya

Struktur Data: Stack dan Queue

Struktur Data: Stack dan Queue Selain linked list , di dalam struktur data juga terdapat teknik lain. Antaranya adalah stack dan queue . Lalu, apa itu sebenarnya stack dan queue ? 1. Stack Stack , atau dalam Bahasa Indonesianya disebut tumpukan , merupakan salah satu teknik struktur data yang bersifat LIFO ( last in first out ). Data yang terakhir masuk ke stack merupakan data yang akan keluar pertama (namanya juga tumpukan). Misalnya terdapat data A, B, C, D, E, dan F. Jika urutan data yang masuk adalah A-B-C-D-E-F, maka untuk mengeluarkan data C, harus dilakukan pengeluaran data F-E-D terlebih dahulu. Algoritma Stack Seperti contoh yang telah dibahas di atas, algoritma dalam stack dilakukan dengan menguji apakah stack sudah penuh jika sedang memasukkan data ( push ). Jika sudah, maka data baru tidak dapat masuk. Jika belum, maka data yang terakhir dimasukkan merupakan data paling atas dari stack tersebut. Untuk mengeluarkan data ( pop ), maka dilakukan uji apaka
2 komentar
Baca selengkapnya