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

1. ## 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;
};

Treeptr talloc(void)
{
return (Treeptr) malloc (sizeof(struct TreeCell));
}

{
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)
else
}
}
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!

2. 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;

TreePtr talloc(void)
{
TreePtr  theP;

theP = 0L;
theP = (TreePtr)malloc(sizeof(TreeCell));
if(!theP)
ErrHandler();             /* <-- normally, you'd write this */

return(theP);
}

{
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)
else
}
}
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.

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

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

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

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