Data Structure question

[degamer106]

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.

[degamer106]

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.

[Infarction]

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 ;)

[degamer106]

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.

[~s.o.s~]

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.

[degamer106]

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?

[~s.o.s~]

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:

// 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.

[degamer106]

wow thx :mrgreen:

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

[~s.o.s~]

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

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.

[Infarction]

& 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.

[Narue]

>Any ideas you guys could fish out would be most helpful.
Lazy deletion is definitely the easiest to implement, but it gets tricky when you want to clean the data structure by physically removing "deleted" nodes. So it really just defers the problem until later, where it becomes a bigger problem. :) The only reall reason for using lazy deletion is when the expense of removing a node is too great at the time.

Since you're storing references and not actual data, a deletion by copying scheme is probably much better for you. It's easier to wrap your head around because you only adjust links for a leaf node. You can find a couple of implementations and a description here.