AVL Tree operations

There are three operations that can be performed on AVL trees

  1. Search operation
  2. Insertion operation
  3. Deletion operation

The search operation for AVL Tree

In an AVL Tree, the search operation is performed with o(logn) time complexity. the search operation is similar to search operation of binary search tree .we use the following steps to search an element in AVL tree

  1. read the search element from the user
  2. compare the search element with the value of root in the root node in the tree
  3. if both are matched then the display “given node is found” and terminate the function
  4. If both are not matched then check whether the search element is smaller or larger than the search element is smaller or larger than the search value
  5. If the search element is smaller , then continue the search process in LST
  6. If the search element is larger, then continue the search process in RST
  7. Repeat the same until we find the exact element until the leaf node occurs
  8. if we reach to the leaf node having the value equal to the search value the display “element is found “and terminate the function
  9. if we reach to the leaf node and it is not matched then display “element not found” and terminate

Insertion operation for AVL Tree

In an AVL Tree, the insertion operation is performed with o(logn) time complexity In AVL trees a new node is always inserted as a leaf node. the insertion operation is as follows

  1. Insert the new elements into the tree using binary search tree insertion login
  2. After insertion check the balance factor of every node
  3. if the balance factor of every node is 0,-1,1 then go to next operation
  4. If the balance factor of every node is other then 0,-1,1 than that tree is said to be imbalanced, in this case, perform suitable rotations to make the tree balanced and go for the next operation

Deletion operation for AVL tree

Delete operations for AVL Trees are same as the Binary search tree deletion,so check the below link for deletion operation of node in both AVL and binary search tree

Last updated on by vishal devxo