Video game tester jobs online

The deletion of a data item from a data structure has always been difficult whatever data structure we use. The deletion is the inverse of insertion. In deletion there is a given value x and an AVL tree T. We delete the node containing the value x and rebalance the tree if it becomes unbalance after deleting the node. We will see that the deletion of a node is considerably more complex than the insertion of a node. It is complex in the sense that we may have to do more than one rotations to rebalance the tree after deleting a node. We will discuss the deletion case by case and will see that about what points we have to take care in the deletion process.

We are not going to write the code for deletion here. If we have to use AVL tree routines or class, the deletion and insertion routines of AVL tree are available in standard library. We can use these routines in our program. We have no need to write these routines. But here we discuss these to understand their functionality.

We know that insertion in a height-balanced tree requires at most one single rotation or one double rotation. We do this rotation at the node whose balance violates the AVL condition. We can use rotations to restore the balance when we do a deletion. If the tree becomes unbalance after deleting a node then we use rotations to rebalance it. We may have to do a rotation at every level of the tree. Thus in the worst case of deletion we have to do log₂ N rotations. As log₂ N is the number of levels of a tree of N nodes.

Let�s consider an example of deleting a node from a tree. In this example, we will discuss the worst case of deletion that is we have to do rotation at each level after deleting a node. Look at the following figure i.e. Fig 23.8. In this figure the root of the tree is node N and we have expanded only the left subtree of this node. The right subtree of it is indicated by a triangle. We focus on the left subtree of N. The balance of each non-leaf node of the left subtree of N is �1. This means that at every non-leaf node the depth/height of left subtree is one shorter than the height of right subtree. For example look at the node C. The left subtree of C is one level deep where as it�s right subtree is two levels deep. So balance of it is 1 � 2 = -1. If we look at node I its left subtree has height 2 as there are two levels where nodes G and H exists. The right subtree of I has number of levels (i.e. height) 3 where exists the nodes K, L and M respectively. Thus the balance of I is 2 � 3 = -1. Similarly we can see that other nodes also have the balance �1. This tree is shown in the following figure.

Here in this tree, the deletion of node A from the left subtree causes the worst case of deletion in the sense that we have to do a large number of rotations. Now we delete the node A from the tree. The effect of this deletion is that if we consider the node C the height of its left subtree is zero now. The height of the right subtree of C is 2. Thus the balance of C is 2 now. This makes the tree unbalance. Now we will do a rotation to make the tree balanced. We rotate the right subtree of C that means the link between C and D so that D comes up and C goes down. This is mentioned in the figure below.

After this rotation the tree has transformed into the following figure. Now D becomes the left child of F and C becomes the left child of D.

By looking at the inorder traversal of the tree, we notice that it is preserved. The inorder traversal of the tree before rotation (i.e. fig 23.8) is C D E F G H I J K L M N. Now if we traverse the tree after rotation (i.e. fig 23.9) by inorder traversal we get C D E F G H I J K L M N, which is the same as it was before rotation.

After this rotation we see that the tree having D as root is balanced. But if we see the node F we notice that the height of its left subtree is 2 and height of its right subtree is 4. Thus the balance of F is �2 (or 2 if we take the absolute value) now. Thus the tree becomes unbalance. So we have to do rotation again to balance the tree. The whole left subtree of F is shorter so we do the left rotation on the link of F and I (in the tree in fig 23.9) to bring F down and I up so that the difference of height could be less. After rotation the tree gets the new form that is shown in the figure below.

Here we see that the nodes G and H, which were in the left subtree of I, now become the right subtree of F. We see that the tree with I as root is balanced now. Now we consider the node N. We have not expanded the right subtree of N. Although we have not shown but there may be nodes in the right subtree of N. If the difference of heights of left and right subtree of N is greater than 1 then we have to do rotation on N node to balance the tree.

Thus we see that there may be such a tree that if we delete a node from it we have to do rotation at each level of the tree. We notice that we have to do more rotations in deletion as compared to insertion. In deletion when we delete a node we have to check the balance at each level up to the root. We do rotation if any node at any level violates the AVL condition. If nodes at a level do not violate AVL condition then we do not stop here we check the nodes at each level and go up to the root. We know that a binary tree has log₂ N levels (where N is total number of nodes) thus we have to do log₂ N rotations. We have to identify the required rotations that mean we have to identify that which one rotation out of the four rotations (i.e. single left rotation, single right rotation, double right-left rotation and double left-right rotation) we have to do. We have to identify this at each level.

We can summarize the deletion procedure as under.

Delete the node as in binary search tree. We have seen in the discussion of deleting a node from a BST that we have three cases, which we discussed as follows

Case I: The node to be deleted is the leaf node i.e. it has no right or left child. It is very simple to delete such node. We make the pointer in the parent node pointing to this node as NULL. If the memory for the node has been dynamically allocated, we will release it.

Case II: The node to be deleted has either left child (subtree) or right child (subtree).

In this case we bypass the node in such a way that we find the inorder successor of this node and then link the parent of the node to be deleted to this successor node. Thus the node was deleted.

Case III: The node to be deleted has both the left and right children (subtree). This is the most difficult case. In this case we find the inorder successor of the node. The left most node of the right subtree will be the inorder successor of it. We put the value of that inorder successor node into the node to be deleted. After it we delete the inorder successor node recursively.

In deletion in AVL tree, we delete the node as we delete it in a BST. In third case of deletion in BST we note that the node deleted will be either a leaf or have just one subtree (that will be the right subtree as node deleted is the left most subtree so it cannot have a left subtree). Now we are talking about deletion in an AVL tree. Since this is an AVL tree so if the deleted node has one subtree that subtree contains only one node. Why it is so? Think about its reason and answer.

After deleting the node we traverse up the tree from the deleted node checking the balance of each node at each level up to the root. Thus the deletion in AVL tree is like the deletion in BST except that here in AVL tree we have to rebalance the tree using rotations.

Now let�s consider the cases of deletion that will help to identify what rotation will be applied at what point.

There are 5 cases to consider. Let�s go through the cases graphically and determine what actions are needed to be taken. We will not develop the C++ code for deleteNode in AVL tree. This is left as an exercise.

Case 1a:

The first case is that the parent of the deleted node had a balance of 0 and the node was deleted in the parent�s left subtree.

In the following figure (Fig 23.12) the left portion shows the parent node with a horizontal line in it. This horizontal line indicates that the left and right subtrees of this node have the same heights and thus the balance of this node is 0. When we delete a node from its left subtree then height of its right subtree becomes larger than the left subtree. The right portion in the figure shows this. We are showing a symbol instead of balance of node inside the node. The notation (symbol) in the node indicates that the height of left subtree is shorter than the height of right subtree of the node.

Now the action that will be taken in this case is that, change the balance of the parent node and stop. No further effect on balance of any higher node. There is no need of rotation in this case. Thus it is the easiest case of deletion.

Let�s consider an example to demonstrate the above case.

Consider the tree shown in the following figure i.e. Fig 23.13. This is a perfectly balanced tree. The root of this tree is 4 and nodes 1, 2 and 3 are in its left subtree. The nodes 5, 6 and 7 are in the right subtree.

Consider the node 2. We have shown the balance of this node with a horizontal line, which indicates that the height of its left subtree is equal to that of its right subtree. Similarly we have shown the balance of node 4.

Now we remove the node 1 which is the left subtree of node 2. After removing the left child (subtree) of 2 the height of left subtree of 2 is 0. The height of right subtree of 2 is 1 so the balance of node 2 becomes �1. This is shown in the figure by placing a sign that is down ward to right side, which indicates that height of right subtree is greater than left subtree. Now we check the node 4. Here the height of left subtree of it is still 2. The height of its right subtree is also 2. So balance of the node 4 is 0 that is indicated by the small horizontal line (minus sign) in the figure below. Here we don�t need to change the balance of 4.

Case 1b:

This case is symmetric to case 1a. In this case, the parent of the deleted node had a balance of 0 and the node was deleted in the parent�s right subtree. The following figure shows that the balance of the node was zero as left and right subtree of it have the same heights.

After removing the right child the balance of it changes and it becomes 1, as the height of its left subtree is 1 greater than the height of right subtree. The action performed in this case is the same as that in case 1a. That is change the balance of the parent node and stop. No further effect on balance of any higher node.

The previous example can be done for this case only with the change that remove the right child of node 2 i.e. 3.

Case 2a:

This is the case where the parent of the deleted node had a balance of 1 and the node was deleted in the parent�s left subtree. This means that the height of left subtree of the parent node is 1 greater than the height of its right subtree. It is shown in the left portion of the figure below.

Now if we remove a node from the left subtree of this node then the height of left subtree will decrease by 1 and get equal to the height of right subtree. Thus the balance of this node will be zero. In this case, the action that we will perform to balance the tree is that change the balance of the parent node. This deletion of node may have caused imbalance in higher nodes. So it is advised to continue up to the root of the tree. We will do rotation wherever the balance of the node violates the AVL condition.

There are five cases to consider while deleting a node of an AVL tree. When a node is deleted, the tree can become unbalanced. We calculate the balance factor of each node and perform rotation for unbalanced nodes. But this rotation can prolong to the root node. In case of insertion, only one node�s balance was adjusted as we saw in previous lectures but in case of deletion, this process of rotation may expand to the root node. However, there may also be cases when we delete a node and perform no or one rotation only.

Now, we will see the five cases of deletion. A side note is that we are not going to implement these cases in C++ in this lecture, you can do it yourself as an exercise with the help of the code given inside your text book. In this lecture, the emphasis will be on the deletion process and what necessary actions we take when a node is required to be deleted from an AVL tree. Actually, there are two kinds of actions taken here, one is deletion and the other one is the rotation of the nodes.

Case 1a: The parent of the deleted node had a balance of 0 and a node was deleted in the parent�s left subtree.

In the left tree in the Fig 24.1, the horizontal line inside the tree node indicates that the balance is 0, the right and left subtrees of the node are of equal levels. Now, when a node is deleted from the left subtree of this node, this may reduce by one level and cause the balance of the right subtree of the node to increase by 1 relatively. The balance of the node in favor of the right subtree is shown by a triangular knob tilted towards right. Now, the action required in this case to make the tree balanced again is:

Change the balance of the parent node and stop. There is no further effect on balance of any higher node.

In this case, the balance of the tree is changed from 0 to �1, which is within the defined limits of AVL tree, therefore, no rotation is performed in this case.

Below is a tree in which the height of the left subtree does not change after deleting one node from it.

The node 4 is the root node, nodes 2 and 6 are on level 1 and nodes 1, 3, 5, 7 are shown on level 2. Now, if we delete the node 1, the balance of the node 2 is tilted towards right, it is �1. The balance of the root node 4 is unchanged as there is no change in the number of levels within right and left subtrees of it. Similarly, there is no change in the balances of other nodes. So we don�t need to perform any rotation operation in this case.

Let�s see the second case.

Case 1b: the parent of the deleted node had a balance of 0 and the node was deleted in the parent�s right subtree.

On the left of Fig 24.3, the tree is within the balance limits of AVL. After a node is deleted from the right subtree of it. The balance of the tree is tilted towards left as shown in the right tree show in the Fig 24.3. Now, we see what action will be required to make the tree balanced again.

Change the balance of the parent node and stop. No further effect on balance of any higher node (same as 1a).

So in this case also, we don�t need to perform rotation as the tree is still an AVL (as we saw in the Case 1a). It is important to note that in both of the cases above, the balance of the parent node was 0. Now, we will see the cases when the balance of the parent node is not 0 previously.

Case 2a: The parent of the deleted node had a balance of 1 and the node was deleted in the parent�s left subtree.

In the Fig 24.4 above, the tree on the left contains the balance factor as 1, which means that the left subtree of the parent node is one level more than the number of levels in the right subtree of it. When we delete one node from the left subtree of the node, the height of the left subtree is changed and the balance becomes 0 as shown in the right side tree of Fig 24.4. But it is very important understand that this change of levels may cause the change of balance of higher nodes in the tree i.e.

Change the balance of the parent node. May have caused imbalance in higher nodes so continue up the tree.

So in order to ensure that the upper nodes are balanced, we calculate their balance factors for all nodes in higher levels and rotate them when required.

Case 2b: The parent of the deleted node had a balance of -1 and the node was deleted in the parent�s right subtree.

Similar to the Case 2a, we will do the following action:

Now, we see another case.

Case 3a:The parent had balance of -1 and the node was deleted in the parent�s left subtree, right subtree was balanced.

As shown in the left tree in Fig 24.5, the node A is tilted towards right but the right subtree of A (node B above) is balanced. The deleted node lies in the left subtree of the node A. After deletion, the height of the left subtree is changed to h-1 as depicted in the right tree of above figure. In this situation, we will do the following action:

Perform single rotation, adjust balance. No effect on balance of higher nodes so stop here.

After single left rotation, we have the tree as shown in the figure below.

Node A has become the left subtree of node B and node 2 left subtree of node B has become the right subtree of node A. The balance of node B is tiled towards left and balance of node A is tilted towards right but somehow, both are within AVL limits. Hence, after a single rotation, the balance of the tree is restored in this case.

Case 4a: Parent had balance of -1 and the node was deleted in the parent�s left subtree, right subtree was unbalanced.

In the last case 3a, the right subtree of node A was balanced. But in this case, as shown in the figure above, the node C is tilted towards left. The node to be deleted lies in the left subtree of node A. After deleting the node the height of the left subtree of node A has become h-1. The balance of the node A is shown tilted towards right by showing two triangular knobs inside node A. So what is the action here.

Double rotation at B. May have affected the balance of higher nodes, so continue up the tree.

By performing double rotation in the tree above, we have the following tree.