problem adding into a tree

Discussion in 'C Programming' started by New, Sep 20, 2004.

  1. New

    New Guest

    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;
    }
    New, Sep 20, 2004
    #1
    1. Advertising

  2. New

    Richard Bos Guest

    "New" <> 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
    Richard Bos, Sep 20, 2004
    #2
    1. Advertising

  3. In article <>, "New" <> 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
    Jonathan Adams, Sep 20, 2004
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ramkumar Menon

    B+ Tree versus Ternary Search Tree

    Ramkumar Menon, Aug 16, 2005, in forum: Java
    Replies:
    2
    Views:
    1,585
    Roedy Green
    Aug 16, 2005
  2. Ramkumar Menon

    B+ Tree versus Ternary Search Tree

    Ramkumar Menon, Aug 16, 2005, in forum: Java
    Replies:
    0
    Views:
    425
    Ramkumar Menon
    Aug 16, 2005
  3. Ramkumar Menon

    B+ Tree versus Ternary Search Tree

    Ramkumar Menon, Aug 16, 2005, in forum: Java
    Replies:
    1
    Views:
    442
    Andrew Thompson
    Aug 16, 2005
  4. Joris Gillis
    Replies:
    2
    Views:
    1,526
    Joris Gillis
    Jun 16, 2006
  5. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,097
Loading...

Share This Page