AVL TREE


AVL Tree ditemukan oleh Adelson-Velskii dan Landis. AVL Tree merupakan salah satu jenis BST (binary Search Tree). BST digunakan dengan tujuan untuk mempercepat pencarian data. Apabila BST yg terbentuk cukup seimbang (mendekati complete binary tree) maka waktu pencarian data tidak lebih dari log2n langkah.

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

INSERTION
Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan single rotation dan double rotation.

KASUS INSERTION PADA AVL TREE
*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)


Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
  •  Kasus 1 dan 2 dengan single rotation
  • Kasus 3 dan 4 dengan double rotation


Contoh – Single Rotation: Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root

Contoh – Double Rotation : Jika terdapat sebuah tree yang kemudian dilakukan insert node 26. Maka akan terjadi ketidak seimbangan, sehingga terlihat dari bentuknya dapat diselesaikan dengan kasus 4.

DELETE
Proses menghapus sebuah node di AVL tree hampir sama dengan BST. Penghapusan sebuah node dapat menyebabkan tree tidak imbang Setelah menghapus sebuah node, lakukan pengecekan dari node yang dihapus → root. Gunakan single atau double rotation untuk menyeimbangkan node yang tidak imbang. Pencarian node yang imbalance diteruskan sampai root.





Sumber :
-          https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/
-          http://dinda-dinho.blogspot.com/2013/06/pengertian-dan-konsep-avl-tree.html


Comments

Post a Comment

Popular posts from this blog

Binary Search Tree (BST)

  Binary Search Tree (BST) adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Jika struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat. Aturan main Binary Search Tree : -           Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya. -           Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya. Lalu, ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST : -           PreOrder : Print data, telusur ke kiri, telusur ke kanan -      ...
Read more

Rangkuman Data Structure

Image
Nama: Melody Effendi NIM: 2301925854 Kelas: CB01 Lecturer: Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460) LINKED LIST Linked list atau senarai berantai merupakan suatu kumpulan elemen bertipe sama yang berurutan sesuai dengan ketentuan tertentu. Setiap elemennya dihubungkan melalui pointer. Struktur data pada linked list ini terdiri dari urutan record data, yang masing-masingnya memiliki field untuk menyimpan alamat atau referensi dari record selanjutnya (dalam urutan). Pada linked list, ada istilah node yang berarti elemen data yang dihubungkan dengan link pada linked list. Selain node, ada juga istilah head dan tail. Head adalah elemen yang berada di posisi pertama dalam linked list tersebut, sedangkan tail adalah elemen yang berada di posisi terakhir dalam linked list tersebut. Selain itu, istilah pointer berarti alamat elemen. Macam-macam linked list yaitu sebagai berikut. 1. Circular Single Linked List Arti dari single linked list sendiri adalah suatu kump...
Read more