AVL TREE

AVL Tree adalah binary search tree yang dapat menyeimbangkan dirinya sendiri. Tiap subtree kiri dan kanan memiliki perbedaan tinggi maksimal 1.

Terdapat 2 operation pada AVL Tree, yaitu :

  • Insertion
  • Deletion

Proses insertion pada AVL Tree sama halnya dengan insertion pada Binary Search Tree. Dimana Node baru diposisikan sebagai leaf.


Rebalance pada AVL Tree dapat dilakukan dengan Single Rotation dan Double Rotation.

Terdapat 4 kasus dalam proses rebalance AVL Tree

Yang pertama, node terdalam terletak pada subtree kiri dari anak kiri T.
Yang kedua, node terdalam terletak pada subtree kanan dari anak kanan T.
Yang ketiga, node terdalam terletak pada subtree kanan dari anak kiri T.
Yang keempat, node terdalam terletak pada subtree kiri dari anak kanan T.

Untuk kasus 1&2 dapat diselesaikan dengan Single Rotation. Sedangkan, untuk kasus 3&4 dapat diselesaikan dengan Double Rotation.

Contoh Single Rotation

Contoh Double Rotation


Proses Deletion pada AVL Tree sama halnya dengan Deletion pada Binary Search Tree. Node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan.

Contoh Deletion AVL Tree


Resources :
geeksforgeeks.org
javatpoint.com

Comments

Post a Comment

Popular posts from this blog

LINKED LIST

Image
LINKED LIST Linked list adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis sehingga isi dari daftar dapat dimanipulasi. Linked List terdiri dari berbagai macam, contohnya: - Singly Linked List   Linked list yang pointernya hanya mengarah ke NODE yang menampung. Singly linked list hanya memiliki 1 arah dan tidak bolak-balik.   Contoh: -Doubly Linked List    Linked list yang memiliki pointer penunjuk 2 arah, yakni ke node sebelum dan ke node sesudah.    Contoh:   OPERASI PADA DOUBLY LINKED LIST      - INSERT      Insert bisa dilakukan di depan, tengah, dan di belakang   - DELETE      Sama seperti INSERT, DELETE juga bisa dilakukan di depan, tengah,dan di belakang   - TRAVERSAL      Mengunjungi semua elemen list da...
Read more
Image
REVIEW LINKED LIST Linked list  adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis sehingga isi dari daftar dapat dimanipulasi. Linked List  terdiri dari berbagai macam, contohnya: - Singly Linked List   Linked list yang pointernya hanya mengarah ke NODE yang menampung. Singly linked list hanya memiliki 1 arah dan tidak bolak-balik.   Contoh: -Doubly Linked List    Linked list yang memiliki pointer penunjuk 2 arah, yakni ke node sebelum dan ke node sesudah.    Contoh:    OPERASI PADA DOUBLY LINKED LIST       - INSERT      Insert bisa dilakukan di depan, tengah, dan di belakang   - DELETE      Sama seperti INSERT, DELETE juga bisa dilakukan di depan, tengah,dan di belakang   - TRAVERSAL   ...
Read more

Linked List Review

Image
Pada pertemuan kali ini saya akan me review sedikit tentang push dan pop. Push bisa juga disebut sebagai insert node pada linked list. Push/Insert bisa dilakukan di head (depan), m id(tengah), dan tail( belakang). Pop/Delete juga bisa dilakukan di head (depan), m id(tengah), dan tail( belakang). Fungsi free juga biasa dipakai dalam pembuatan code untuk push maupun pop. Free digunakan untuk menghapus atau melepaskan memory yang telah dipakai dalam malloc. Berikut contoh coding push        Berikut contoh coding pop    Referensi : http://g-emily747.blogspot.com/p/pert2.html
Read more