AVL Tree

-

AVL Tree

Nama saya Raymond Andilsim, dan pada blog ini saya akan menulis rangkuman tentang AVL Tree. AVL Tree adalah subtipe dari Binary Search Tree. Pohon AVL memiliki properti penyeimbangan mandiri dinamis selain semua properti yang digunakan oleh Binary Search Tree. AVL Tree adalah sebuah upgrade dari Binary Search Tree. Tambahan/Upgraden dari BST adalah :

BST memiliki aturan seperti :

  1. Setiap pohon memiliki root (di atas).
  2. Root memiliki nol, satu atau dua node anak.
  3. Setiap node memiliki nol, satu atau dua node anak, dan seterusnya.
  4. Setiap node memiliki hingga dua anak.
  5. Untuk setiap node, turunan/node kirinya lebih kecil dari node di atasnya, yang lebih kecil dari turunan kanan.



 Dan di AVL Tree terdapat tambahan yaitu perbedaan antara kedalaman subtrees kanan dan kiri tidak boleh lebih dari satu. Untuk mengimplementasikan ini, implementasi AVL akan menyertakan algoritma untuk menyeimbangkan kembali pohon saat menambahkan elemen tambahan yaitu single rotation dan double rotation. Dengan proses seperti ini :

  1. Jika ada ketidakseimbangan pada anak kiri subtree kanan, maka kita akan melakukan rotasi kiri-kanan.
  2. Jika ada ketidakseimbangan pada anak kiri subtree kiri, maka kita akan melakukan rotasi kanan.
  3. Jika ada ketidakseimbangan pada anak kanan subtree kanan, maka kita akan melakukan rotasi kiri.
  4. Jika ada ketidakseimbangan pada anak kanan subtree kiri, maka kita akan melakukan rotasi kanan-kiri.

Contoh Single Rotation

Node 37 dan 40 tidak seimbang karena terdapat 45 di paling bawah kanan dan beda nodenya itu sudah 2, maka itu di rotate menjadi :



Contoh Double Rotation

Terjadi tidak keseimbangan karena ada 5 di paling bawah sebelah kiri dan sudah terjadi perbedaan 2 node, sehingga dilakukan rotasi pertama di 11 :


11 sudah terotasi dan 8 naik ke atas, tetapi masih belum seimbang, maka itu dilakukan lagi rotasi kedua di 3 dan 8 bisa naik lagi ke node atas : 


Tree sudah seimbang karena perbedaan nodneya sekarang hanya 1.


Sekian rangkuman AVL Tree dari saya, mohon maaf jika ada kesalahan.

Nama : Raymond Andilsim
NIM   : 2301906533



Comments

Post a Comment

Popular posts from this blog

Semester 2 Review / Summary

-
Image
Review / Summary Semester 2 1. Linked List Circular Single Linked List     Circular linked list adalah variasi dari linked list dimana setiap node tidak memiliki ruang NULL dan diganti oleh ruang untuk menunjuk node selanjutnya dan node paling terakhir akan menunjuk node yang pertama dan seterusnya, sehingga terbentuk sebuah siklus. Double Linked List      Double Linked List adalah variasi dari linked list yang bisa bergerak bolak-balik dimana setiap node memiliki 3 ruang, perbedaan node pertama, node tengah dan node terakhir adalah di node pertama, di ruang pertama adalah NULL dan ruang ketiga untuk menunjuk node selanjutnya, untuk node di tengah, ruang pertama untuk menunjuk node sebelumnya dan ruang ketiga untuk menunjuk node selanjutnya, dan di node terakhir, ruang pertama untuk menunjuk node sebelumnya dan ruang ketiga adalah NULL. Circular Doubly Linked List      Circular Doubly Linked List adalah linked list gabungan dari circular single linked list dan double l
Read more

Application Code

-
Application Code Raymond Andilsim 2301906533 #include <stdio.h> #include <stdlib.h> #include <string.h> struct product{ char productName[31]; int qty; int price; struct product *next, *prev; } *head = NULL, *tail = NULL, *curr; void addProduct(char *productName, int qty){ curr = (struct product*)malloc(sizeof(struct product)); strcpy(curr->productName, productName); curr->qty = qty; curr->price = rand() % 1000000; if(curr->price == 0) curr->price = curr->price + 1000; else if(curr->price < 10) curr->price = curr->price * 1000; else if(curr->price < 100) curr->price = curr->price * 100; else if(curr->price < 1000) curr->price = curr->price * 10; curr->next = curr->prev = NULL; if(head == NULL){ head = tail = curr; } else if (strcmp(productName, head->productName) < 0){ curr->next = head; head->prev
Read more