FOR FREE MATERIALS
AVL tree - insertion, search and deletion
Back to ProgrammingDescription
Introduction:
An AVL tree is a self balancing binary search tree where for all nodes the difference between the left sub-tree and right sub-tree cannot be more than one. AVL tree is named after Adelson, Velskii and Landi who developed the technique of balancing the height of the the tree.
An AVL tree has the following characteristics
(a) It can be empty.
It comprises a root which has two sub-trees TR and TL ,with height hR and hLrespectively, where -1<= hR- hL<=1
In order to balance an AVL tree only two operations can be performed
(a) Left Rotation
(b) Right Rotation
Insertion:
New nodes are inserted into the AVL tree by using the standardbinary search tree rules first. Let the newly inserted node be ‘n’. After that a series of operations are performed to make it an AVL tree. The operations are
(a)Start from the newly inserted node‘n’and travel up to find the first unbalanced node (say ‘z’). Let ‘x’ be the child of ‘z’ that comes on the path from ‘n’ to ‘z ’and ‘y’ be the grandchild of ‘z’ that comes on the path ‘n’ to ‘z’.
(b) Rebalancing is done by performing appropriate rotations on the sub-tree with‘z’ as the root. There are four possible cases that need to be handled according to the arrangements of x,y and z.
l Left Left Case(i.e.‘x’ is the left child of ‘z’ and ‘y’ is the left child o f‘x’)
Right Rotate ‘z’ inorder to balance the height.
l Left Right Case(i.e. ‘x’ is the left child of ‘z’ and ‘y’ is the right child of ‘x’)
Left Rotate ‘x’ and then Right Rotate ‘z’ inorder to balance the height.
l Right Right Case(i.e.‘x’ is the right child of ‘z’ and ‘y’ is the right child of ‘x’)
Left Rotate ‘z’ inorder to balance the height.
l Right Left Case(i.e. ‘x’ is the right child of ‘z’ and ‘y’ is the left child of ‘x’)
Right Rotate‘x’and then Left Rotate‘z’ inorder to balance the height.
Search
Whenever a node is to be searched in anAVL tree, the searching starts from the root node. If the value is lesser than the root, then the left sub-tree is searched, else the node is searched in the right sub-tree. This process is continued until the particular node has been found or no nodes are left in the tree.
Deletion:
Nodes are deletedfrom the AVL tree by using the standardbinary search tree rules first. Let the deleted node be ‘n’. After that a series of operations are performed to make it an AVL tree. The operations are
(a)Start from the deleted node‘n’and travel up to find the first unbalanced node (say ‘z’). Let ‘x’ be the larger child of ‘z’ and ‘y’be the larger child of ‘x’.
(b) Rebalancing is done by performing appropriate rotations on the sub-tree with ‘z’ as the root. There are four possible cases that need to be handled according to the arrangements of x,y and z.
l Left Left Case(i.e. ‘x’ is the left child of ‘z’ and ‘y’ is the left child of ‘x’)
Right Rotate ‘z’ in order to balance the height.
l Left Right Case(i.e. ‘x’is the left child of ‘z’ and ‘y’is the right child of ‘x’)
Left Rotate ‘x’ and then Right Rotate ‘z’in order to balance the height.
l Right Right Case(i.e.‘x’ is the right child of ‘z’ and ‘y’ is the right child of ‘x’)
Left Rotate ‘z’ in order to balance the height.
l Right Left Case(i.e. ‘x’ is the right child of ‘z’ and‘y’ is the left child of‘x’)
Right Rotate‘x’and then Left Rotate‘z’ in order to balance the height.
Algorithm
Algorithm:
Input:
root which points to the root of the AVL tree.
Output:
(a) AVL tree creation.
(b) Printing the AVL tree in in-order, post-order and pre-order.
(c)Searching a node in the AVL tree.
(d) Deleting a node from the AVL tree.
Algo:
Step 1: Start.
Step 2:Defining the getMax(x,y) function
l If x > y then,
(a)Return x.
l Else then,
(a)Return y.
Step 3: Defining the getHeight(temp) function
l If temp = NULL then,
(b)Return 0.
l Else then,
(b)Return temp[height].
Step 4: Defining the rightRotate(temp) function
l Set t1<= temp[left].
l Set t2<===t1[right].
l Set t1[right]=<=temp.
l Set temp[left]<=t2.
l Set temp[height]<= getMax(getHeight(temp[left]), getHeight(temp[right]))+1
l Set t1[height]<=getMax(getHeight(t1[left]), getHeight(t1[right]))+1
l Return t1.
Step 5: Defining the leftRotate(temp) function
l Set t1<=temp[right].
l Set t2<=t1[left].
l Set t1[left] <=temp.
l Set temp[right]<=t2.
l Set temp[height]<=getMax(getHeight(temp[left]), getHeight(temp[right]))+1
l Set t1[height] <= getMax(getHeight(t1[left]), getHeight(t1[right]))+1
l Return t1.
Step 6: Defining the getBalanceFactor(temp) function
l If temp = NULL then,
(c)Return 0.
l Else then,
(c)Return getHeight(temp[left])-getHeight(temp[right]).
Step 7: Defining the insert(temp,value) function
● If temp = NULL then,
(a)Set newNode[data]<= value.
(b)Set newNode[height] <=1.
(c)Return newNode.
● If value <=temp[data] then,
(a) temp[left] <= insert(temp[left],value)
● Else then,
(a) temp[right]<=insert(temp[right],value)
l Set temp[height] <= 1+getMax(getHeight(temp[left), getHeight(temp[right]).
l Set balance <= getBalanceFactor(temp).
l If balance>1 and value <= temp[left][data] then,
(a) Return rightRotate(temp).
l If balance<=1 and value > temp[right][data] then,
(a) Return leftRotate(temp).
l If balance>1 and value > temp[left][data] then,
(a) Set temp[left] leftRotate(temp[left])
(b) Return rightRotate(temp).
l If balance<=1 and value <= temp[right][data] then,
(a) Set temp[right] <= rightRotate(temp[right]).
(b)Return leftRotate(temp).
l Return temp.
Step 8: Defining the create() function
● Set root <= NULL.
● Set n<=number of elements
● Repeat for i =0 to n-1,
(a) Set value <= the value to be inserted.
(b)Set root <= insert(root,value).
● Return root.
Step 9: Defining the preorder(temp) function
● If temp != NULL then,
(a)Display temp[data].
(b) Call preorder(temp[left]).
(c) Call preorder(temp[right]).
Step 10: Defining the inorder(temp) function
● If temp != NULL then,
(a)Call inorder(temp[left]).
(b) Display temp[data].
(c)Call inorder(temp[right]).
Step 11: Defining the postorder(temp) function
● If temp != NULL then,
(a) Call postorder(temp[left]).
(b) Call postorder(temp[right]).
(c) Display temp[data].
Step 12: Defining the search(root,value) function
● Set temp <= root.
● Repeat substeps while temp !=NULL
(a) If temp[data] = value then,
Display “The value exists.”
Return.
(b) Else if value <temp[data] then,
Set temp<=temp[left]
(c) Else then,
Set temp<=temp[right]
● Display “The value does not exist.”
Step 13: Defining the inorderSuccessor(temp) function
l Set t <=temp.
l Repeat substeps while t[left]!=NULL
(a)Set temp<=temp[left].
l Return t.
Step 14: Defining the deleteNode(temp,value) function
● If temp = NULL then,
(a) Display “The value does not exist.”
(b) Return temp.
● If value<temp[data] then,
(a) Set temp[left]<=deleteNode(temp[left],value).
● Else if value>temp[data] then,
(a) Set temp[right]<=deleteNode(temp[right],value).
● Else then,
(a) If temp[left]=NULL or temp[right]=NULL then,
If temp[left]=NULL then,
Set t<= temp[right].
Else if temp[right]=NULL then,
Set t<= temp[left].
If t=NULL then,
Set t<=temp.
Set temp<= NULL.
Else then,
Set temp<=t
(b) Else then,
Set t <= inorderSuccessor(temp[right])i
Set temp[data] <=t[data]
Set temp[right] <=deleteNode(temp[right],t[data]).
● If temp=NULL then,
(a)Return temp.
l Set temp[height]<=1+getMax(getHeight(temp[left), getHeight(temp[right]).
l Set balance<=getBalanceFactor(temp).
l If balance>1 and getBalanceFactor(temp[left])<=0 then,
(a) Return rightRotate(temp).
l If balance<=1 and getBalanceFactor(temp[right])<=0 then,
(a) Return leftRotate(temp).
l If balance>1 and getBalanceFactor(temp[left])<0 then,
(a) Set temp[left]<= leftRotate(temp[left])
(b) Return rightRotate(temp).
l If balance<=1 and getBalanceFactor(temp[right])>0 then,
(a) Set temp[right]<= rightRotate(temp[right]).
(b)Return leftRotate(temp).
l Return temp.
Step 15: Stop.
Code
Application:
AVL tree has application in fields where insertion and deletion of items are not that frequent but searching of items is very frequent.
Advantages:
The AVL tree has various advantages
(a) It allows faster search operations.
(b) Whenever new items are added into the tree, or items are deleted from the tree, the tree balances itself.
Disadvantages:
The AVL tree has various disadvantages
(a) Self balancing makes the insertion and deletion operations much more time consuming.
(b) Performance drops in fast updating systems using AVL tree data structure.
Complexity:
Time Complexity:
In an AVL tree with ‘n’ number of nodes. The time complexity for search, insertion and deletion are given below-
Space Complexity:
In anAVL tree with ‘n’ number of nodes, the space complexity will be O(n).
