deleting from a bst 
Author Message
 deleting from a bst

I wrote a code to delete from a binary search tree, and I am not sure why,
but when I call it in the main program, it does not always delete my target.
Then I try to delete the next number, which it deletes. Finally when I am
almost finished deleting the tree, then I can also delete the ones I could
not at the beginning. Can you please have a look at the code below and maybe
you can spot what I could not?
Thanks a lot.
K.

Procedure deletenode(var bst: tree; target: longint);
var q: tree;
Begin
searchnode(bst, target);
if target <> bst^.id then
writeln('Target not found')
else
begin
 if bst = nil then
 writeln('Empty tree')
 else
  if bst^.right = nil then
   begin
     q := bst;
     bst := bst^.left;
     dispose(q);
   end
  else
   if bst^.left = nil then
    begin
     q:= bst;
     bst := bst^.right;
     dispose(q);
    end
  else
   begin
    q:= bst^.right;
    while q^.left <> nil do
     q:= q^.left;
    q^.left := bst^.left;
    q := bst;
    bst := bst^.right;
    dispose(q);
   end;
 end;
end;

And this is how I call it in the main program:
...
readln(target);
    while target <> 0 do
       begin
         deletenode(root, target);
         writeln('Enter a number to delete or 0 to stop');
         readln(target);
       end;



Wed, 29 Oct 2003 03:52:54 GMT  
 deleting from a bst

Quote:

> I wrote a code to delete from a binary search tree, and I am not sure why,
> but when I call it in the main program, it does not always delete my target.
> Then I try to delete the next number, which it deletes. Finally when I am
> almost finished deleting the tree, then I can also delete the ones I could
> not at the beginning. Can you please have a look at the code below and maybe
> you can spot what I could not?
> Thanks a lot.
>      q := bst;
>      bst := bst^.left;

I just quickly checked, but shouldn't this be:

bst^:=bst^.left^;

???



Wed, 29 Oct 2003 03:53:31 GMT  
 deleting from a bst

Quote:

>I wrote a code to delete from a binary search tree, and I am not sure why,
>but when I call it in the main program, it does not always delete my target.
>Then I try to delete the next number, which it deletes. Finally when I am
>almost finished deleting the tree, then I can also delete the ones I could
>not at the beginning. Can you please have a look at the code below and maybe
>you can spot what I could not?
>Thanks a lot.
>K.

>Procedure deletenode(var bst: tree; target: longint);
>var q: tree;
>Begin
>searchnode(bst, target);
>if target <> bst^.id then

Here you reference bst which means it must never be nil

Quote:
>writeln('Target not found')
>else
>begin
> if bst = nil then

Here you check if it is nil. WTF?

Quote:
> writeln('Empty tree')
> else
>  if bst^.right = nil then
>   begin
>     q := bst;
>     bst := bst^.left;
>     dispose(q);
>   end

To delete a node, you must get the parent of the node to be deleted.
After all, it is the links in that which you have to modify. So you need
to modify the searchnode that it also returns the parent.

Alternatively you could move the entire node in place of what you
delete. I wonder is that what you attempt? (please use comments)

You would probably do:;

q:=bst^.left;
bst^:=q^;
bst^.right:=q^.right;
bst^.left:=q^.left;
dispose(q);

However, you should rather check:

if  bst^.left<>nil then...

If the node is a leaf, then you really cannot proceed that way, you need
to either find the father or mark it as deleted. (see next paragraph)

The simplest thing might just be to use a field that tells the node is
deleted. Then you can write a garbage collection routine or you can just
let the IO to handle the garbage collection (i.e. when you write the
data to disk, skip the deleted nodes),

Quote:
>  else
>   if bst^.left = nil then
>    begin
>     q:= bst;
>     bst := bst^.right;
>     dispose(q);
>    end
>  else
>   begin
>    q:= bst^.right;
>    while q^.left <> nil do
>     q:= q^.left;
>    q^.left := bst^.left;
>    q := bst;
>    bst := bst^.right;
>    dispose(q);
>   end;
> end;
>end;

>And this is how I call it in the main program:
>...

Osmo


Wed, 29 Oct 2003 06:19:21 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. need help in BST - ap.pas (0/1)

2. Copying BST

3. Trouble printing a BST line by line

4. deleting ok unless the first one to be deleted

5. DBASE: permanently deleting deleted records

6. I'm stuck and need advise - cannot fix Record/Key Deleted

7. data aware grid and table - record/key deleted

8. how to delete a database in SQL editor

9. I CAN'T DELETE A TABLE

10. How to delete record without prompt message?

11. Add and delete items from arrays

12. Session.FindDatabase finding deleted alias

 

 
Powered by phpBB® Forum Software