Thread: BinaerTree Sorting....How to delete ?

  1. #1
    Registered User
    Join Date
    Mar 2002
    Posts
    64

    BinaerTree Sorting....How to delete ?

    I have made a Bintree, where I sort numbers.
    It can fx be phonenumbers.
    But how do I delete on in the memorystack,
    fx if a numbers is is in the stack and the number is drawn again It has to delete it self, or actually the numbers has to be deleted from the tree.

    code snip---------------

    typedef struct TreeCell *Treeptr;
    struct TreeCell
    {
    double number;
    Treeptr left, right;
    };

    // function made.. talloc..!!
    Treeptr talloc(void)
    {
    return (Treeptr) malloc (sizeof(struct TreeCell));
    }

    Treeptr AddCell(Treeptr p, double number)
    {
    if(p == NULL)
    {
    p = talloc();
    p->number = number;
    p->right = p->left = NULL;
    }
    else
    {
    if(number == p->number)
    {
    FUNCTIONCALL (has to delete the number..????)
    }
    else
    {
    if(number < p->number)
    p->left = AddCell(p->left, number);
    else
    p->right = AddCell(p->right, number);
    }
    }
    return p;
    }


    The problem is to delete a number in the stack.
    A lot of rearranging has to be done...

    Tx hoping to get some help..

    tx

    !G!
    !G!

  2. #2
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    a lot of rearranging has to be done
    You got that right (grin). I've rearranged it slightly to make it easier to view and think about (atleast to me).

    Code:
     
    typedef struct TreeStruc
       {
       struct TreeStruc    *left;
       struct TreeStruc    *right;
       double                  number; 
       }TreeCell,*TreePtr;
    
    // function made.. talloc..!!
    TreePtr talloc(void)
       {
       TreePtr  theP;
    
       theP = 0L;
       theP = (TreePtr)malloc(sizeof(TreeCell));
       if(!theP)
          ErrHandler();             /* <-- normally, you'd write this */
       
       return(theP);
       }
    
    TreePtr AddCell(TreePtr p, double number)
       {
       if(!p)                                /* create root node */
          {
          p = talloc();
    
          /* check allocation of 'p' here */
    
          p->number = number;
          p->right = p->left = NULL; 
          }
       else
          {
          if(number == p->number)
             {
             /*****
              *
              *  Found duplicate number.  Want to replace it
              *  How do I delete existing number?
              *
              *****/
             }
          else
             {
             if(number < p->number)
                p->left = AddCell(p->left, number);
             else
                p->right = AddCell(p->right, number);
             }
          }
       return p;
       }
    ---

    Okay, I took a look at your algorithm and in your case you don't need to do anything. You don't have to delete the existing node, because the value is in 'number' is already the same. Just discard the duplicate (ignore it and move on).

    If you were really sorting a database and this happened, then you would created a hash-table that would let you distinguish between the two, and you'd add another node to hold the duplicate.

    If you were really interested in deleting an entire node, then you must delete that node, but KEEP it's child (left & right) branches as well as the parent node's other branch together and resort them. Then rehang them off the parent.

    Rather than walking the list to find the parent, add another field to your structure:

    Code:
    typedef struct TreeStruc
       {
       struct TreeStruc    *parent;
       struct TreeStruc    *left;
       struct TreeStruc    *right;
       double                  number; 
       }TreeCell,*TreePtr;
    Also, it's a good idea to get into the habit of putting your link pointers as the FIRST fields in a structure. that way, for future exandability, you always know where the pointers are, even if the rest of the format of the structure changes-- it wouldn't break a program.
    It is not the spoon that bends, it is you who bends around the spoon.

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    64
    Tx for answering, but I not sure I understand .

    I do need to delete a number second time it is comming in..

    This is how it works.
    A software is counting which phonenumbers is calling a central.
    First time the number is called a bintree is sorting the numbers.
    Second time the same phonenumber is calling in, the program is finding the number in the Tree, and deleting the number, because now the number is to be used in some other way..

    So the number has to be gone from the Tree, because if the same number will call one more time, It will go the routine again allover..

    So I need to make a function, which can move the (left & right) child branches to another position.

    So I'm a bit confused how to do this...

    !G!

    ps: BTW, how do I write the good cod inhere.
    IS there something I need to turn on, so the code is standing correctly.
    !G!

  4. #4
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    Alright, then you must delete that node, but KEEP it's child (left & right) branches as well as the parent node's other branch together and resort them. Then rehang them off the parent.

    Rather than walking the list to find the parent, add another field to your structure:


    Code:
    typedef struct TreeStruc
       {
       struct TreeStruc    *parent;
       struct TreeStruc    *left;
       struct TreeStruc    *right;
       double                  number; 
       }TreeCell,*TreePtr;
    ---

    Let's say that the duplicate node is a leftchild of a grand-parent, making it a PARENT with child nodes. We're going to call the grandparent 'G', the left-parent 'LP', the right-parent 'RP', the left child 'L', and the right child 'R'.

    Code:
         G
      LP   RP
    L   R
    Because of this arrangement, there are some _knowns_. For example, we KNOW that LP, L, and R, are all less than RP. Thus, when LP is deleted, we know that L, and R, are less than RP.

    If all you had was L and R to worry about, it is simple to attach L as R's left-child, and then attach R as G's left-child.

    The problem comes if L and R have child nodes as well. It means you have to start rearranging that entire branch of the tree (that was under LP).

    It is a difficult problem if you try to do it on the tree itself. Approach 1 is usually used for performance. Approach 2 is somewhat more bruteforce, and doesn't take height-balancing into account.

    Approach 1:
    ---------------
    Hash Table of indexes to the nodes. It is fast and easy to manage the hash-table. If a node needs deleted, just mark it as dead and proceed as normal.

    Approach 2:
    ---------------
    Take all the affected nodes (L, and R, and their children), and re-sort them into their own tree. Reattach that tree as G's left-child.
    It is not the spoon that bends, it is you who bends around the spoon.

  5. #5
    Registered User
    Join Date
    Jun 2002
    Posts
    151
    To elaborate on Sayeh's second method a little, you can take advantage of a BST property to make the re-sorting a little easier.

    - If your node to be deleted has zero children, just delete it.

    - If your node has only one child, promote that child into the position of the node to be deleted.

    - If your node to be deleted has two children, either remove the furthest right node in the left sub-tree, or the furthest left node in the right subtree (either of these will have either zero or only one child making the removal fairly easy). Then replace the node to be deleted with this removed node. The furthest right node in the left sub-tree is guaranteed to have a greater value (assuming you tree sorts in ascending order) than anything else in the left sub-tree but will still have a lesser value than anything in the right sub-tree (the same is true of the furthest left node in the right sub-tree). Therefore moving this node ensures that the tree remains sorted.

  6. #6
    Gugge
    Guest
    I can easily se how is has to be done.
    With rehaning the parent and Left/right child.
    But the problem is comming when I have to make it into code..

    How to rearrange it with code is trouble to me..

    Another thing, if I have the heap filled up, fx 640 K.
    How can I rearrange a whole branch with numbers if there is no more memory for at temporary perant to hang anything on..?

  7. #7
    Registered User
    Join Date
    Mar 2002
    Posts
    64
    OK to start out with I got:
    Code:
    typedef struct TreeCell *Treeptr; 
    struct TreeCell
    {
         struct TreeCell *parent; 
         struct TreeCell *left;
         struct TreeCell *right;
    
         double tlfnumber;   
    };
    And starting on the function:

    Code:
    Treeptr DeleteCell(Treeptr p, double tlfnumber)
    {
         p->tlfnumber->parent->left = p->tlfnumber->left;
         p->tlfnumber->parent->right = p->tlfnumber->right;
         
         free(p->tlfnumber);
    
    // Something is comming here......
    
         return 0;
    }
    Now I shold have put left and right on the parent, right ?
    And it's possible to Kill/delete p->tlfnumber.
    Now the rest of the branch is hanging from the parent..

    But how do I get intouch with the GrandParent, if we go about the example you gave:
    Code:
             G
        LP      RP
     L     R  L     R
    I guess the only thing left is to hang the branch on the G's left or right side..

    But How can I rearrange the branch, 'cause someone has to be at top,
    Is it L or R. ?? (if it was LP, which had to be deleted.)

    And like I wrote above, how can I use memory to make a temp arrangement if the heap and memory is fully loaded...??

    This is really a touch problem I think, I very glad that you share the interest aswell.
    !G!

  8. #8
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    Enmeduranki's additional advice is excellent, and well said. He outlined the algorithm for you.

    Another thing, if I have the heap filled up, fx 640 K.
    How can I rearrange a whole branch with numbers
    If you run out of memory, it won't really matter. It is (sorry to say) beyond the scope of this thread to solve a out of memory condition- this would require writing a virtual memory manager, and it sounds like you're working in DOS. However, If you don't resort the loose branch, but simply use Enmeduranki's algorithm, it doesn't cost you any additional RAM.

    You have to figure out the code part- that's how you learn. It isn't very hard at all. It's a well-defined problem, and there are answers online.

    Here is a little pseudo-code (to help):

    Code:
    void DeleteNode(node) 
       {
       if(node has no children)
          {
          reset parent's left/right link to NULL 
          free up node
          }
       else
          {
          if(node has one child)
             {
             reset parent's link to point to child 
             reset child's link to point to parent 
             free up node
             }
          else
             {
             replacement = SuccessorNode(node); 
             swap items between node and replacement 
             DeleteNode(replacement)
             };
          };
       }
    SuccessorNode() merely starts at the 'node' first passed to DeleteNode(), and walks down its right child to find a successor node. I arbitrarily chose to look for a successor node, rather than a predecessor node.

    Successor = Smallest Node that is Greater than 'node'.
    Predecessor = Greatest Node that is Smaller than node.
    It is not the spoon that bends, it is you who bends around the spoon.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BST delete again, but this time I think I'm close
    By tms43 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2006, 06:24 PM
  2. delete and delete []
    By Lionel in forum C++ Programming
    Replies: 8
    Last Post: 05-19-2005, 01:52 PM
  3. why is this prog crashing on delete?
    By Waldo2k2 in forum Windows Programming
    Replies: 2
    Last Post: 12-04-2002, 11:17 PM
  4. Problem need help
    By Srpurdy in forum C++ Programming
    Replies: 1
    Last Post: 07-24-2002, 12:45 PM
  5. memory management...
    By master5001 in forum Game Programming
    Replies: 24
    Last Post: 01-07-2002, 05:50 PM