problem adding into a tree

[New]

Why does this code insert a node into a binary search tree correctly? If I
only inserting going by first digit it works properly but when I try
inserting going by the whole ip and the port number the inserts are totally
out of order.

where
IPAddress is four ints
Node is an IPAddress, portNumber, left pointer and right pointer
Nodeptr is a pointer to a Node

Nodeptr add(Nodeptr tree, IPAddress ip, int portNumber)
{
if(tree==NULL)
{
if((tree = malloc(sizeof(Node)))==NULL )
{
printf("No memory Left\n");
}
else
{
tree->address.digit1 = ip.digit1;
tree->address.digit2 = ip.digit2;
tree->address.digit3 = ip.digit3;
tree->address.digit4 = ip.digit4;
tree->portNo=portNumber;
tree->left = tree->right = NULL;
}
}

else if(ip.digit1 < tree->address.digit1)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
else if(ip.digit1 >= tree->address.digit1)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(ip.digit2 < tree->address.digit2)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
else if(ip.digit2 >= tree->address.digit2)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(ip.digit3 < tree->address.digit3)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
else if(ip.digit3 >= tree->address.digit3)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(ip.digit4 < tree->address.digit4)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
else if(ip.digit4 >= tree->address.digit4)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(portNumber < tree->portNo)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
else if(portNumber >= tree->portNo)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
return tree;
}

 

[Richard Bos]

Why does this code insert a node into a binary search tree correctly? If I
only inserting going by first digit it works properly but when I try
inserting going by the whole ip and the port number the inserts are totally
out of order.

Nodeptr add(Nodeptr tree, IPAddress ip, int portNumber)
{
if(tree==NULL)
{
{
}
else
{
}
}

Your code could do with some more consistent indentation. As for your
error...

else if(ip.digit1 < tree->address.digit1)
{
}
else if(ip.digit1 >= tree->address.digit1)

When, do you think, are _both_ of those ifs going to fail? IOW, when is
the code reached which does the comparison based on digit2 to digit4?

Richard

 

[Jonathan Adams]

Why does this code insert a node into a binary search tree correctly? If I

^
I assume there's a "n't" missing here...

only inserting going by first digit it works properly but when I try
inserting going by the whole ip and the port number the inserts are totally
out of order.

First, I'd recommend re-writing this as:

static int
ipaddr_port_cmp(IPAddress *left_ip, int left_portNumber,
IPAddress *right_ip, int right_portNumber)
{
/*
* put your comparisons here, return -1 if left < right,
* 1 if left > right, and 0 if they are equal.
*/
}

Nodeptr add(Nodeptr tree, IP...)
{
if (tree == NULL) {
...
} else if (ipaddr_port_cmp(&ip, portNumber,
&tree->addr, tree->portNo) < 0)
tree->left = add(tree->left, ip, portNumber);
} else {
tree->right = add(tree->right, ip, portNumber);
}
return (tree);
}

since the ipaddr_port_cmp() function will presumably be useful
elsewhere, and your code will be much less repetitive (and maintainable).


To figure out the problem with your code, consider the case of:

ip matches the root node's addr
portNumber < the root node's port

walk through the code for that case, and the problem should become
clear. You could also try turning on your compiler's warnings, since it
may be able to find the problem.

Cheers,
- jonathan