Binary-Tree 
Author Message
 Binary-Tree

Quote:

>Hello,
>Can anyone help with a program which is required to remove a node
>from a binary tree while maintaining its integrity.
>The program is emulating a theasaurus.  A user inputs a word which
>the program searches through the binary tree for.  If found the
>word is removed and the nodes adjusted.  Each word has a linked
>list of synonyms attached to it.  The program must search through
>the linked lists for any occurrence of the word input by the user
>and remove the word from the linked list while maintaining its
>integrity.
>Any help would be appreciated.
>Cheers
>Neil Ford


I'm not a expert on this, so what I would do is only my take on this.

You'll have three situations, a deletion at the end of a branch, and a
deletion in the tree (with successors on both nodes), and a deletion
of a node with only one successor.

1) end of branch; delete that record, reset the pointer to it back to
null.  repack whenever you feel like it.  This is generally no
problem.

3) one successor node only.  Go to the parent node, find the pointer
to this node, rewrite it with the pointer to the successor node
(branch of this node).  Delete record.  No problem, repack as needed.

2) this is the tough one, offhand, I can't think of a neat solution,
so I opt for sneaky.  Include in each node a flag that indicates valid
entry.  Go down to node that has a need to be deleted, then set that
flag to "no entry/place marker only".  Now you know that isn't there
any more.  

Every once and a while, you might want to repack the database when the
number of unused nodes exceeds a threshold.

2a) more complicated solution.  Treat as single descendant (3), pick a
branch, and make it the sole descendant.  You now have an orphan
branch.  Read through the entire tree of that branch, _adding_ the
info to the existing binary tree.  Takes longer, perhaps, but should
also work.  

BTW: what do you do for multiple instances of the same word?  I had a
trinary tree, so I could stack words on top of each other (needed it
for Japanese phonetics hiragana/katakana/romaji, happens less with
Kanji)

I'd like to see what others think about this solution, I'm sure there
is a better one for the two descendants case.

Hope this helps, and I'm restricting this to borland Pascal and
pascal.

Harvey

***
  I just read minds,
  I don't explain them
***



Wed, 18 Jun 1902 08:00:00 GMT  
 Binary-Tree

Quote:

>Hello,
>Can anyone help with a program which is required to remove a node
>from a binary tree while maintaining its integrity.

The correct way to delete a node from abinary tree is :

1. If only one of the branches is valid (i.e. contains nodes), replace
   with that node (naturally).

2. If both branches contain nodes, the deleted node should be replaced
   by the "smallest" node in the *RIGHT* subtree. The "smallest" node
   is easily found as it is the "leftmost".

This is the correct way of deleting nodes; the tree will be kept valid.

Hope this helped!

                    Martin K.



Wed, 18 Jun 1902 08:00:00 GMT  
 Binary-Tree

Quote:
>Hello,
>Can anyone help with a program which is required to remove a node
>from a binary tree while maintaining its integrity.

I'm assuming you mean a plain binary tree.

There are three cases to consider.  
Case 1:  The node you want to delete has no children.
  Solution is trivial.
Case 2:  The node you want to delete has one child.
  Solution:  Remove the node and attach the child to the deleted node's
parent, not necessarily in that order.
Case 3:  Node has two children.
  Solution:  Turn it into a Case1  or Case 2 situation by using a method
called the Inorder Successor Method.  Swap the **contents** (in this case
a pointer to a linked list), with the contents of the node's inorder
successor (the next highest value).  The inorder successor can never have
more than one child, leaving you with a Case 1 or Case 2 situation.  The
inorder successor is physically located to the right one node and down as
far left as you can go.

--

  Tim Groner

  http://home.cc.umanitoba.ca/~umgroner        



Wed, 18 Jun 1902 08:00:00 GMT  
 Binary-Tree

Quote:

>The correct way to delete a node from abinary tree is :

>1. If only one of the branches is valid (i.e. contains nodes), replace
>   with that node (naturally).

>2. If both branches contain nodes, the deleted node should be replaced
>   by the "smallest" node in the *RIGHT* subtree. The "smallest" node
>   is easily found as it is the "leftmost".

>This is the correct way of deleting nodes; the tree will be kept valid.

Have you an equally clear explanation of how to add a new node, while
keeping the tree (approximately) balanced?
--
John Stockton, Surrey, UK.  Turnpike v1.12.  MIME.


Wed, 18 Jun 1902 08:00:00 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. The use of coprcessor reals (previously Re: Stack overflow at binary tree balance)

2. Stack overflow at binary tree balance

3. Binary tree problem

4. Binary Tree

5. How to determine the height of a binary tree

6. Recursion and Binary Tree

7. Recursion and Binary Tree

8. Binary tree proof.

9. Showing Binary trees

10. binary tree question

11. Binary Trees

12. binary tree/dictionary

 

 
Powered by phpBB® Forum Software