# AvL Tree Deletion ISSUE

Page 1 of 1

## 2 Replies - 2578 Views - Last Post: 12 December 2012 - 11:25 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=303634&amp;s=c62cc67ad65039f83887d7ec0f9fe5d0&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 deepecstasy

Reputation: 1
• Posts: 6
• Joined: 03-November 12

# AvL Tree Deletion ISSUE

Posted 11 December 2012 - 01:43 PM

As you know how avl should be balanced after deletion of a node, I'll get to point. For starting, Im considering deleteing a node with no children.

For Example a Tree:
```		10
/		\
5		17
/  \    /  \
2  9   12  20
\           \
3          50
```

Lets say deletevalue(12);

Then Tree should be after deletion:
```		10
/		\
5		17
/  \       \
2  9       20
\           \
3          50
```

Now, we see tree is balanced at node 17, because by formula, its Balance Factor = height( left subtree [left tree is null so -1] ) - height (right subtree) = -2

So we balance the tree by checking if its right-right case or right-left case.

```If BalanceFactor(17's right) = -1
perform SingleLeftRotation(17);
else if BalanceFactor(17's right) = -1
perform DoubleRightLeftRotation(17);
```

Similar is case if Balance Factor of 17 is 2, i.e. it is left high, then its respective rotations.
//for bF(17) = 2

```If BalanceFactor(17's left) = 1
perform SingleLeftRotation(17);
else if BalanceFactor(17's left) = -1
perform DoubleLeftRightRotation(17);
```

After balancing, tree should become this:

```		10
/		\
5		20
/  \    /  \
2  9   17  50
\
3

```

This is deletion I have designed.

From main function, I call

```bool deletevalue(WA value)
{
AvLNode<WA> *temp = search(root, value);	//calling search function to find node which has user-specified data & stored its address in temp pointer
if(temp!=0)	//if temp node is not null then
{
if(temp->left==0 && temp->right==0)	//if temp node don't have any children
{	deletewithNochild(root, value);	}	//call to respective function
else if( (temp->left!=0 && temp->right==0) || (temp->left==0 && temp->right!=0) )	//if temp node has any 1 child, left or right
{	deletewithOneChild(temp);	}	//call to respective function
else if(temp->left!=0 && temp->right!=0)	//if temp node has 2 children
{	deletewith2Child(temp);		}	//call to respective function

return true;	//for prompting respective output message
}
else
return false;	//for prompting respective output message
}
```

as our required node has no child so, following function is envoked.

```void deletewithNochild(AvLNode<WA> *temp, WA value)	//temp is node which is to be deleted
{
if(value == root->key)	//if temp is root node then
{
delete root;	//free memory of root node
root = 0;	//nullify root
}
else	//if temp is some other node
{
if (value < temp->key)
{
deletewithNochild(temp->left, value);
}
else if (value > temp->key)
{
deletewithNochild(temp->right, value);
}
else if (value == temp->key)
{
AvLNode<WA> *father = findfather(temp, root);	//calling findfather func to find father of temp node & store its address in father node pointer

if(father->left==temp)	//if temp is left child of its father
{
delete temp;	//free memory of temp node
father->left=0;	//nullify father's left
}
else if(father->right==temp)	//if temp is right child of its father
{
delete temp;	//free memory of temp node
father->right=0;//nullify father's right
}
return;
}
cout<<"\nBalancing";
if ( balancefactor(temp) == 2)	//if temp is left higher, ie. temp's Balance Factor = 2, then
{
cout<<"\t2 ";
if ( balancefactor(temp->left) == 1 ) //if temp's left node has Balance Factor 1 then
{
SingleRightRotation(temp);	//send temp node for rotation because temp is unbalance
}
else if ( balancefactor(temp->left) == -1 )	//if temp's left node has Balance Factor -1, then
{
DoubleLeftRightRotation(temp);	//send temp for double rotation because temp is unbalance
}
}
else if ( balancefactor(temp) == -2 )	//if temp is right higher, ie. temp's Balance Factor = -2, then
{
cout<<"\t-2 ";
if ( balancefactor(temp->right) == -1 )	//if temp's left node has Balance Factor -1 then
{
SingleLeftRotation(temp);	//send temp node for rotation because temp is unbalance
}
else if ( balancefactor(temp->right) == 1 )	//if temp's right node has Balance Factor 1, then
{
DoubleRightLeftRotation(temp);	//send temp for double rotation because temp is unbalance
}
}

}
}
```

Here are two utility functions of HEIGHT of node & BALANCE FACTOR of node

```int heightofnode(AvLNode<WA> *temp) const
{
return temp==NULL ? -1 : temp->height;
}

int balancefactor(AvLNode<WA> *temp) const
{
return ( heightofnode(temp->left) - heightofnode(temp->right) );
}
```

My output, when I delete 12 becomes
(Breadth First Travers) -->> [10] [9] [17]

Kindly help me out, is there any problem with recursion? I have dry-runned again & again but can't understand. Deleteion must be done through recursion otherwise balancing tree would be a bigger hell.
Thanks in advance for giving time. :-)

Is This A Good Question/Topic? 0

## Replies To: AvL Tree Deletion ISSUE

### #2 #define

• Duke of Err

Reputation: 1744
• Posts: 6,205
• Joined: 19-February 09

## Re: AvL Tree Deletion ISSUE

Posted 12 December 2012 - 10:45 PM

Is the temp->height valid?

```temp->height;

```

You could try printing some of the height values.

### #3 deepecstasy

Reputation: 1
• Posts: 6
• Joined: 03-November 12

## Re: AvL Tree Deletion ISSUE

Posted 12 December 2012 - 11:25 PM

#define, on 12 December 2012 - 10:45 PM, said:

Is the temp->height valid?

```temp->height;

```

You could try printing some of the height values.

Yes it is valid. height is data member of all nodes. so it is accessible. I've checked it, it works fine, anyway I have change my code, & it seems to work partially. Im gonna edit & add it in original post.