DaniWeb Forum Index > Software Development > C++

C++ RSS

Data Structure question

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Mar 2006

Posts: 131

Reputation: degamer106 is an unknown quantity at this point

Solved Threads: 0

degamer106 degamer106 is offline

Offline

Junior Poster

Data Structure question

Dec 6th, 2006

I've been asked to create a movie data baseusing a hash table (w/ linked-list collision resolution) and a BST. Both of them contain a field that points a given structure (we'll call it *pMovie and its of type MOVIE) in memory. For example, if i'm going to insert "The Matrix" into the MOVIE structure and intend to insert MOVIE into the BST and Hash, both of their pMovie fields will point to that structure. So far, I've been able to do all of the project's requirements except for the deletion. For the hash table, it's no problem. However, come deletion for the BST, I'm a at a loss for ideas.

A few of my classmates have thought of creating a flag field to implement what they call "lazy deletion" so they can simply leave the nodes in the tree where they are w/o even physically deleting them. Unfortunately, my teacher didn't approve of that, stating that she wanted the nodes to be physically deleted. That idea is definitely out. :cry:

Besides rotation, which I'm not wholly familiar with, I don't see any other way of doing this. Any ideas you guys could fish out would be most helpful.

Last edited by degamer106; Dec 6th, 2006 at 2:52 am.

•

Join Date: Mar 2006

Posts: 131

Reputation: degamer106 is an unknown quantity at this point

Solved Threads: 0

degamer106 degamer106 is offline

Offline

Junior Poster

Re: Data Structure question

Dec 6th, 2006

I forgot to mention that part of the problem occurs when I try to print the list after I delete a node. I know why I can't print, but I'm not sure how to fix the tree.

•

Join Date: May 2006

Posts: 1,580

Reputation: Infarction has a spectacular aura about

Solved Threads: 52

Infarction Infarction is offline

Offline

Battle Programmer

Re: Data Structure question

Dec 6th, 2006

I'm surprised your teacher isn't allowing for lazy deletion. That said, here's one method (I don't remember the best way though) for deleting from a BST:

Find the node to be deleted. From there you have two ways to get it's replacement:
- go left one node, then right all the way to the rightmost leaf of that subtree. That node will have the property of being greater than everything above or to the left of it, up until the deleted node. It is also less than everything to the right of the deleted node. Hence, a suitable replacement. Remove it from its leaf position and put it in the deleted node's place.
- similarly, you can go right one node, then left recursively to a leaf. Same properties will apply, though mirrored.

This might end up a little messy moving all the pointers around, but it's a conceptually easy way to find a replacement for the deleted node... HTH

•

Join Date: Mar 2006

Posts: 131

Reputation: degamer106 is an unknown quantity at this point

Solved Threads: 0

degamer106 degamer106 is offline

Offline

Junior Poster

Re: Data Structure question

Dec 6th, 2006

wow thank you for the reply. I have two questions though:

1) This is similar to rotation, right?

2) Is there a specific case where I would use each on of these? I think I can see that I would use your first method for deleting something in the left subtree and your second one for something in the right subtree. I'm not entirely sure though.

•

Join Date: Jun 2006

Posts: 7,609

Reputation: ~s.o.s~ has much to be proud of

Solved Threads: 464

~s.o.s~

Offline

Failure as a human

Re: Data Structure question

Dec 6th, 2006

Naa..this is not similar to rotation. Rotation is used for balancing the binary tree which becomes unbalanced after repeated deletions from the BST, and for the purpose of balancing we use AVL trees, Red Black tree and many others -- but I don't think you should complicate matters by taking these things into consideration for the time being.

And now for the deletion part -- there are actually three cases:
1. The node has no children : In this case you can directly remove the node.

2. The node has one child: In this case you just replace the node with the child.

3. The node has two children: This is a bit tricky to handle and toughest among all. In this case you need to delete the node keeping in mind the nature or property of BST is maintained.

Suppose if the node is N then we replace the value of N with either its in-order successor (the left-most child of the right subtree) or the in-order predecessor (the right-most child of the left subtree).

For an excellent simulation you can look here.

HOpe it solved your problem.

I don't accept change; I don't deserve to live.

•

Join Date: Mar 2006

Posts: 131

Reputation: degamer106 is an unknown quantity at this point

Solved Threads: 0

degamer106 degamer106 is offline

Offline

Junior Poster

Re: Data Structure question

Dec 6th, 2006

thx for the reply.

I used that applet before when we were learning AVL trees. Correct me if I'm wrong, but an AVL tree must be balanced and it does use rotations. If I'm just trying to maintain the relative order in a BST (larger items to the right and smaller items to the left) I could just simply use the deletes you guys mentioned without having to do all that complicated stuff, right?

Another concern I have is with the third case that s.o.s mentioned, which I feel hasn't been answered yet (unless you intended to have the applet as the solution). Again, how would I know which way to go when I delete an item?

•

Join Date: Jun 2006

Posts: 7,609

Reputation: ~s.o.s~ has much to be proud of

Solved Threads: 464

~s.o.s~

Offline

Failure as a human

Re: Data Structure question

Dec 6th, 2006

Yes -- like I mentioned in my previous post, you can leave out the complicated stuff of balancing the tree since the it doesn't seem to be the focus of your project.

As far as the third case is concerned, assuming you have the pointer to the node to be deleted with you:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
// here we accept a reference to the node pointer type
// this relieves you from passing the function a pointer to pointer
// thereby making the deletion easy.
void delete_node( Node*& node )
{
    Node*& tmp = node ;
 
    if( node->left == NULL )
    {
         node = node->right ;
         delete tmp ;
    }
    else if ( node->right == NULL )
    {
         node = node->left ;
         delete tmp ;
    }
    else
    {
         // here comes the third case          
         tmp = node->left ;
         while( tmp->right != NULL )
         {
              tmp = tmp->right ;
         }
          node->value = tmp->value ;
          delete_node( tmp ) ;
}
// here we accept a reference to the node pointer type
// this relieves you from passing the function a pointer to pointer
// thereby making the deletion easy.
void delete_node( Node*& node )
{
    Node*& tmp = node ;
    
    if( node->left == NULL )
    {
         node = node->right ;
         delete tmp ;
    }
    else if ( node->right == NULL )
    {
         node = node->left ;
         delete tmp ;
    }
    else
    {
         // here comes the third case          
         tmp = node->left ;
         while( tmp->right != NULL )
         {
              tmp = tmp->right ;
         }
          node->value = tmp->value ;
          delete_node( tmp ) ;
}

Hope it helped , bye.

I don't accept change; I don't deserve to live.

•

Join Date: Mar 2006

Posts: 131

Reputation: degamer106 is an unknown quantity at this point

Solved Threads: 0

degamer106 degamer106 is offline

Offline

Junior Poster

Re: Data Structure question

Dec 6th, 2006

wow thx :mrgreen:

Isn't the notation *(&tmp) the same as saying tmp.

•

Join Date: Jun 2006

Posts: 7,609

Reputation: ~s.o.s~ has much to be proud of

Solved Threads: 464

~s.o.s~

Offline

Failure as a human

Re: Data Structure question

Dec 6th, 2006

No, its a reference thingy which belongs to C++.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int a = 10 ;
int& b = 20 ;  // b is a reference or an alias to a
int a = 10 ;
int& b = 20 ;  // b is a reference or an alias to a

If you haven't been taught that, you can just use double pointers to node type and you task will be done.

Hope it helped, bye.

Last edited by ~s.o.s~; Dec 6th, 2006 at 9:48 pm.

I don't accept change; I don't deserve to live.

•

Join Date: May 2006

Posts: 1,580

Reputation: Infarction has a spectacular aura about

Solved Threads: 52

Infarction Infarction is offline

Offline

Battle Programmer

Re: Data Structure question

#10

Dec 6th, 2006

& can be used to denote a reference or to get the address of a variable, (and also as a bitwise operator). When used at the declaration (e.g. as Node*&) it is the first, and when used in a non-declaration and preceeding a single variable, it is to get the address. When it is between two vars, e.g. a & b it is performing a bitwise-and operation between the two.