2 Replies - 1519 Views - Last Post: 12 December 2012 - 11:25 PM Rate Topic: -----

#1 deepecstasy  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • 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  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1396
  • View blog
  • Posts: 4,872
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 deepecstasy  Icon User is offline

  • New D.I.C Head

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

Re: AvL Tree Deletion ISSUE

Posted 12 December 2012 - 11:25 PM

View Post#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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1