Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > problem adding into a tree

Reply
Thread Tools

problem adding into a tree

 
 
New
Guest
Posts: n/a
 
      09-20-2004
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;
}


 
Reply With Quote
 
 
 
 
Richard Bos
Guest
Posts: n/a
 
      09-20-2004
"New" <(E-Mail Removed)> wrote:

> 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
 
Reply With Quote
 
 
 
 
Jonathan Adams
Guest
Posts: n/a
 
      09-20-2004
In article <(E-Mail Removed)>, "New" <(E-Mail Removed)> wrote:

> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
B+ Tree versus Ternary Search Tree Ramkumar Menon Java 2 08-16-2005 08:13 PM
B+ Tree versus Ternary Search Tree Ramkumar Menon Java 1 08-16-2005 09:46 AM
B+ Tree versus Ternary Search Tree Ramkumar Menon Java 0 08-16-2005 09:01 AM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM
Spanning Tree And Per Vlan Spanning Tree Amy L. Cisco 0 07-24-2003 10:01 PM



Advertisments