AVL Tree

-

In today’s topic, I will be talking about AVL Tree. So what is AVL Tree? AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be greater than one for all nodes in which we usually call balance factor, maintaining an O(log N) search time. AVL Tree was made to prevent BST worst-case scenario in which the performance is closest to linear search algorithms like in skewed BST. For example,  if the input to BST comes in a sorted (ascending or descending) manner.



AVL trees has the following guarantees:
1.      Each tree has a root node (at the top).
2.      The root node has zero, one, or two child nodes.
3.      Each child node has zero, one or two child nodes, and so on.
4.      Each node has up to two children.
5.      For each node, its left descendants are less than the current node, which is less than the right descendants.
6.      The difference between the depth of right and left subtrees cannot be more than one. To maintain this guarantee, and implementation of an AVL will include an algorithm to rebalance the tree when adding element would upset this guarantee.

Insertion Operation
1.      Insert the new Node using recursion so while backtracking we will check all of the parents' nodes whether they are still balanced or not.
2.      Every node has a field called height with default value as 1.
3.      When a new node is added, its parent’s node height gets increased by 1.
4.      So as mentioned in step 1, every ancestor's height will get updated while backtracking to the root.
5.      At every node, the balance factor will also be checked. Balance factor = (height of left Subtree – height of right Subtree).
6.      If balance factor == 1 means the tree is balanced at that node.
7.      If balance factor > 1 means tree is not balanced at that node, left height has greater value than the right height and if balance factor < -1 it means the tree is not balanced at that node, right height has greater value than the left height. In either case, it means we need to do rotation. 

Deletion Operation
1.      Find the node of the value we want to delete.
2.      Delete the node. There are three possible cases: 
a.      When x has no children then, we can simply delete x
b.      When x has one child, let x' becomes the child of x.
Notice: x' cannot have a child, since subtrees of T can differ in height by at most one :
•    Then replace the contents of x with the contents of x'
•    Then delete x' 
c.    When x has two children.
•    Then find x's successor z (which has no left child)
•    Then replace x's contents with z's contents and delete z

AVL Tree Rotations


In AVL tree, after performing every operation like insertion and deletion we need to check the balance factor of every node in the tree. If every node satisfies the balance factor condition then we conclude the operation otherwise we must make it balanced. We use rotation operations to make the tree balanced whenever the tree is becoming imbalanced due to any operation.

Rotation operations are used to make a tree balanced. There are four rotations and they are classified into two types: 

Single Rotation
Single Left Rotation (LL Rotation) 
In LL Rotation every node moves one position to left from the current position. 


Single Right Rotation (RR Rotation) 
In RR Rotation every node moves one position to the right from the current position. 




Double Rotation:
Left Right Rotation (LR Rotation)
The LR Rotation is a combination of single left rotation followed by a single right rotation. In LR Rotation, first, every node moves one position to the left then one position to the right from the current position. 


Right Left Rotation (RL Rotation)
The RL Rotation is a combination of single right rotation followed by a single left rotation. In RL Rotation, first, every node moves one position to right then one position to left from the current position.




That's it for AVL Tree. Have A Good Day.
Bitter or Sweet

Sources :
https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/
https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm
https://algorithms.tutorialhorizon.com/avl-tree-insertion/
https://www.w3schools.in/data-structures-tutorial/avl-trees/


Comments

Post a Comment

Popular posts from this blog

Even Semester Full Summary

-
Image
Nama: Aisyah Amalia NIM: 2301904370 Kelas: CB01-CL Hari: June 10th, 2020 Lecturer: Ferdinand Ariandy Luwinda (D4522), Henry Chong (D4460) First Part of Even Semester For the first meeting, I've learned about LINKED LIST. So what is linked list? Linked list is a dynamic data structure, where each element is a separate object. If in array we can easily access the elements in it by the index--because it stores the value in a consecutive memory location, in linked list we can’t do that because in linked list it uses random memory location. Now if you think “Then, isn't array better than?” well in array you can’t easily do insertions and deletions, but in linked list you can easily do push(for insertion) or pop(for deletion). Other than that, if in array you have to give a fixed memory to use in your program, in linked list the number of nodes is not fixed and can grow or shrink on demand, hence it’s called a dynamic data structure. This feature is very use...
Read more

Linked List and Stack and Queue

-
Image
LINKED LIST For the first meeting, I've learned about LINKED LIST. So what is linked list? Linked list is a dynamic data structure, where each element is a separate object. If in array we can easily access the elements in it by the index--because it stores the value in a consecutive memory location, in linked list we can’t do that because in linked list it uses random memory location. Now if you think “Then, isn't array better than?” well in array you can’t easily do insertions and deletions, but in linked list you can easily do push(for insertion) or pop(for deletion). Other than that, if in array you have to give a fixed memory to use in your program, in linked list the number of nodes is not fixed and can grow or shrink on demand, hence it’s called a dynamic data structure. This feature is very useful when you have to deal with an unknown number of objects. One of the disadvantage of linked list is that it uses more memory compares with an array, it adds an extra 4 b...
Read more

First Part of Even Semester

-
Image
For the first meeting, I've learned about LINKED LIST. So what is linked list? Linked list is a dynamic data structure, where each element is a separate object. If in array we can easily access the elements in it by the index--because it stores the value in a consecutive memory location, in linked list we can’t do that because in linked list it uses random memory location. Now if you think “Then, isn't array better than?” well in array you can’t easily do insertions and deletions, but in linked list you can easily do push(for insertion) or pop(for deletion). Other than that, if in array you have to give a fixed memory to use in your program, in linked list the number of nodes is not fixed and can grow or shrink on demand, hence it’s called a dynamic data structure. This feature is very useful when you have to deal with an unknown number of objects. One of the disadvantage of linked list is that it uses more memory compares with an array, it adds an extra 4 bytes (on 3...
Read more