Thread: Issue with tree nodes

  1. #1
    Registered User
    Join Date
    Jun 2013
    Posts
    25

    Issue with tree nodes

    Heya!

    I've got a kd tree which stores the x,y value as struct in every node.

    The issue I have is the following: in addition to my regular nodes, my tree creates a bunch of nodes with 0,0!

    The only thing I can think of being responsible is my struct constructor:

    Code:
    struct Coordinate{
        double x,y;
        Coordinate() : x(0), y(0) {}
        Coordinate(double paramx, double paramy) : x(paramx), y(paramy) {}
    };
    
    struct TreeNode{
        Coordinate coord;
        struct TreeNode* left;
        struct TreeNode* right;
    };
    The thing is, I don't need the Coordinate() constructor, only added it to get rid of error message. I'm only using Coordinate(double x, double y).

    Anyways, I add a node like this in my Tree class:
    Code:
     TreeNode *node = new TreeNode();
            node->coord.x = incCoords[0].x;
            node->coord.y = incCoords[0].y;
            return node;
    The incCoords[0].x and incCoords[0].y value is 100% not 0,0 at this point.


    I will post the rest of my method in case the issue happens to be something else^^
    Code:
    TreeNode* Tree::buildTree(int depth, std::vector<Coordinate>incCoords){
    
        std::vector<Coordinate>coordSet1;
        std::vector<Coordinate>coordSet2;
        coordSet1.clear();
        coordSet2.clear();
    
        if (incCoords.size() == 1)
        {
            TreeNode *node = new TreeNode();
            node->coord.x = incCoords[0].x;
            node->coord.y = incCoords[0].y;
            std::cout << "New root created, coords: " << incCoords[0].x << " x " << incCoords[0].y << std::endl;
            return node;
        } else if (depth % 2 == 0) {
            std::sort(incCoords.begin(), incCoords.end(), sortByX);
        } else if (depth % 2 == 1) {
            std::sort(incCoords.begin(), incCoords.end(), sortByY);
        }
    
        for (unsigned int i=0; i<incCoords.size()/2; i++)
        {
            coordSet1.push_back(incCoords[i]);
        }
    
        for (unsigned int i=incCoords.size()/2; i<incCoords.size(); i++)
        {
            coordSet2.push_back(incCoords[i]);
        }
    
        TreeNode *node = new TreeNode();
    
        node->left = buildTree(depth++, coordSet1);
        node->right = buildTree(depth++, coordSet2);
    
        return node;
    }
    Any suggestion for a workaround is welcome, thx in advance =)

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,748
    Why don't you give your treenode a constructor as well?
    Code:
    struct TreeNode{
        Coordinate coord;
        struct TreeNode* left;
        struct TreeNode* right;
        TreeNode ( Coordinate &c ) : coord(c) { }
    };
    Then you can simply other code with
    TreeNode *node = new TreeNode(incCoords[0]);

    > node->left = buildTree(depth++, coordSet1);
    > node->right = buildTree(depth++, coordSet2);
    I suspect you don't understand post-increment yet.

    Try instead
    Code:
        node->left = buildTree(depth+1, coordSet1);
        node->right = buildTree(depth+2, coordSet2);
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    This is the wrong way to go about it:
    Code:
    TreeNode *node = new TreeNode();
    node->coord.x = incCoords[0].x; 
    node->coord.y = incCoords[0].y;
    return node;
    You should have a constructor for TreeNode which takes the x and y and passes them on to the Coordinate:
    Code:
    struct Coordinate {
        double x,y;
        Coordinate(double x, double y) : x(x), y(y) {}
    };
    
    struct TreeNode {
        Coordinate coord;
        struct TreeNode* left;
        struct TreeNode* right;
        TreeNode(double x, double y) : coord(x, y) {}
    };
    Edit: Too slow, and Salem's suggestion is better.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Jun 2013
    Posts
    25
    Thanks for the input, your suggestions are much better than what I had!

    Btw. I'm an idiot, the 0,0 nodes were created due to
    TreeNode *node = new TreeNode();
    on the very bottom of my code, and they are not "unwanted" either as only the endnodes hold actual values =/

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    You should also separate Tree from TreeNode. A Tree uses TreeNodes to build its tree, which is why they are allocated with new (don't forget to delete, or use smart pointers!). But the Tree itself does not need to be allocated with new. We should expect to be able to do

    Tree MyTree;
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Registered User
    Join Date
    Jun 2013
    Posts
    25
    Hm I have no idea why, but my printMethod leads to a crash with your suggested implementation.

    The print method works perfectly fine however with my previous version as posted on the very top. I can't find the reason though as I didn't change anything else...

    Hm any idea what I did wrong?

    Code:
    struct Coordinate{
        double x,y;
        Coordinate() : x(0), y(0) {}
        Coordinate(double paramx, double paramy) : x(paramx), y(paramy) {}
    };
    
    struct TreeNode{
        Coordinate coord;
        struct TreeNode* left;
        struct TreeNode* right;
        TreeNode (Coordinate &c) : coord(c) { }
        TreeNode () {}
    };
    Code:
    void Tree::printTreeNodes(TreeNode* node)
    {
        if(node->left != NULL)
        {
            printTreeNodes(node->left);
        }
        if(node->right != NULL)
        {
            printTreeNodes(node->right);
        }
    }
    
    
    TreeNode* Tree::buildTree(int depth, std::vector<Coordinate>incCoords){
        std::vector<Coordinate>coordSet1;
        std::vector<Coordinate>coordSet2;
        coordSet1.clear();
        coordSet2.clear();
    
        if (incCoords.size() == 1)
        {
            std::cout << "New root created, coords: " << incCoords[0].x << " x " << incCoords[0].y << std::endl;
            TreeNode *node = new TreeNode(incCoords[0]);
            return node;
    
        } else if (depth % 2 == 0) {
            std::sort(incCoords.begin(), incCoords.end(), sortByX);
        } else if (depth % 2 == 1) {
            std::sort(incCoords.begin(), incCoords.end(), sortByY);
        }
    
        for (unsigned int i=0; i<incCoords.size()/2; i++)
        {
            coordSet1.push_back(incCoords[i]);
        }
    
        for (unsigned int i=incCoords.size()/2; i<incCoords.size(); i++)
        {
            coordSet2.push_back(incCoords[i]);
        }
    
        std::cout << "Adding 0 x 0 node " << std::endl;
        TreeNode *node = new TreeNode();
    
        node->left = buildTree(depth+1, coordSet1);
        node->right = buildTree(depth+1, coordSet2);
    
        return node;
    }
    (if u wondered, my 0x0 nodes are just nodes holding leafs, the actual content is stored in my leafs. I later plan to store the median value in the leafs)

    Anyways any hint is appreciated!!=)

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    >>struct TreeNode* left;
    Delete "struct". You only need that keyword when actually defining your struct. Creating instances of it does not need it.

    >>TreeNode () {}
    I suggest you initialize your nodes to nullptr. That's presumably the reason for the crash. You must be VERY careful about initializing them to nullptr if they aren't valid; else they'll contain garbage.

    >>TreeNode (Coordinate &c) : coord(c) { }
    I suggest you change that to
    TreeNode (Coordinate c) : coord(std::move(c)) { }
    Include <utility> for std::move. Read about rvalue references for more info about std::move. This is recommended practice for C++11 (you can also create a separate move constructor, but this approach saves code, even though it is a little less efficient).

    >>TreeNode* Tree::buildTree(int depth, std::vector<Coordinate>incCoords)
    Take vector by const reference since you are not storing it and not modifying it.

    >> coordSet1.clear();
    >> coordSet2.clear();
    Not necessary. Default-constructed vectors are empty.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    This is recommended practice for C++11.
    O_o

    No. It is not.

    Here the "value" represented by the type is trivial, the parameter references an object that doesn't require mutation, and no templates are involved.

    Here the recommended practice is using a constant reference, and C++11 has not changed the recommendation.

    Such a technique can be appropriate, but it is not appropriate here.

    you can also create a separate move constructor, but this approach saves code, even though it is a little less efficient
    Are you talking about saving code by not writing a new `Coordinate' move constructor? The recommendation of moving a value parameter is pointless without a move constructor of the appropriate type. (Of course, `Coordinate' isn't a resource owning mechanism which can be trivially transferred so the approach is pointless here in any event.) Without a move constructor the use of `std::move' is something of a lie or "red-herring"; you still just call the normal copy-constructor.

    Soma

  9. #9
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Clarification:
    This saves creating a move constructor for TreeNode.
    TreeNode needs to save a copy of the Coordinate arguments passed in to it, so if we compare the different methods:

    Pass by (const) reference:
    Lvalue: One copy is made when copying into coord from c.
    Rvalue: One copy is made when copying into coord from c.

    Pass by value:
    Lvalue: One copy is made when passing parameter. One move is made when moving c into coords.
    Rvalue: One move is made when passing parameter. One move is made when moving c into coords.

    Pass by (const reference) and rvalue reference:
    Lvalue: One copy is made when copying into coord from c.
    Rvalue: One move is made when moving c into coords.

    But the rule of thumb is: moves are cheap. Therefore, you can save code by passing by value at a little extra cost, but you can save a lot over the traditional C++03 way when rvalues are involved.
    (This practice only applies if you need to store a copy of the passed arguments and that the type of the passed argument is cheap to move.)
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    This saves creating a move constructor for TreeNode.
    O_o

    As with your assertion to use sharing pointer to implement a doubly linked list, it would be unusual to treat `TreeNode' as a resource owning object. (The `Tree' owns the resources; the `TreeNode' is the method of ownership.)

    Therefore, you can save code by passing by value at a little extra cost, but you can save a lot over the traditional C++03 way when rvalues are involved.
    Only if a move constructor for the appropriate type exists, and here no such overload exists. (Here, this is actually irrelevant because there is no transferable resource.)

    Let's put it this way, you list of costs is wrong for this case.

    Code:
    Pass by const reference:
    Lvalue: Reference is passed; One copy is made when copying into coord from c.
    Rvalue: Reference is passed; One copy is made when copying into coord from c.
    
    Pass by value:
    Lvalue: One copy is made when passing parameter. One copy is made when moving c into coords.
    Rvalue: One copy is made when passing parameter. One copy is made when moving c into coords.
    
    Pass by rvalue reference:
    Lvalue: Reference is passed; One copy is made when copying into coord from c.
    Rvalue: Reference is passed; One copy is made when copying into coord from c.
    If you want to limit the cost with "move semantics", you have to do the work.

    This practice only applies if you need to store a copy of the passed arguments and that the type of the passed argument is cheap to move.
    There are actually a lot of reasons for using a value parameter instead of a constant reference, even in C++98; you just need to carefully consider everything.

    Soma

  11. #11
    Registered User
    Join Date
    Jun 2013
    Posts
    25
    You guys are a genius, thanks alot for the help!!

    >>TreeNode* Tree::buildTree(int depth, std::vector<Coordinate>incCoords)
    Take vector by const reference since you are not storing it and not modifying it.
    Trying to change my parameters to:
    Code:
    TreeNode* buildTree(int depth, const std::vector<Coordinate>&incCoords);
    Gives me two odd error messages:
    passing 'const Coordinate' as 'this' argument of 'Coordinate& Coordinate:perator=(Coordinate&&)' discards qualifiers [-fpermissive]
    passing 'const Coordinate' as 'this' argument of 'Coordinate& Coordinate:perator=(const Coordinate&)' discards qualifiers [-fpermissive]
    Last edited by coffee_cups; 06-14-2013 at 05:50 PM.

  12. #12
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I can however pass as reference without const though, that sufficient?
    O_o

    He simply missed where you are modifying the parameter.

    If you are okay with the `incCoords' argument, the value passed to `buildTree', being modified, changing to a non-constant reference is fine.

    Soma

  13. #13
    Registered User
    Join Date
    Jun 2013
    Posts
    25
    thanks for the clarification!

    meh I dunno wth is going on, but I for some reason again have 1:1 the same issue I had at the very start, being crash when my print function is called. I thought the nullptr thingie fixed it... ><

    Code:
    struct TreeNode{
        Coordinate coord;
        TreeNode* left;
        TreeNode* right;
        TreeNode (Coordinate c) : coord(std::move(c)) { }
        TreeNode () {left = nullptr; right = nullptr; }
    };
    Code:
    TreeNode* Tree::buildTree(int depth, std::vector<Coordinate>incCoords){
        std::vector<Coordinate>coordSet1;
        std::vector<Coordinate>coordSet2;
        coordSet1.clear();
        coordSet2.clear();
    
        if (incCoords.size() == 1)
        {
            TreeNode *node = new TreeNode(incCoords[0]);
            return node;
        } else if (depth % 2 == 0) {
            std::sort(incCoords.begin(), incCoords.end(), sortByX);
        } else if (depth % 2 == 1) {
            std::sort(incCoords.begin(), incCoords.end(), sortByY);
    
        }
        for (unsigned int i=0; i<incCoords.size()/2; i++)
        {
            coordSet1.push_back(incCoords[i]);
        }
    
        for (unsigned int i=incCoords.size()/2; i<incCoords.size(); i++)
        {
            coordSet2.push_back(incCoords[i]);
        }
    
        TreeNode *node = new TreeNode();
        node->left = buildTree(depth+1, coordSet1);
        node->right = buildTree(depth+1, coordSet2);
    
        return node;
    }

    Now just like before, if I changed
    Code:
            TreeNode *node = new TreeNode(incCoords[0]);
            return node;
    to
    Code:
     TreeNode *node = new TreeNode();         node->coord.x = incCoords[0].x;         node->coord.y = incCoords[0].y;         return node;
    then it all works again :0 meh I guess it's better to just skip the TreeNode(Coordinate c) constructor and move on with the working way

  14. #14
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    You need to set left and right to null in TreeNode(Coordinate). It should be
    Code:
        TreeNode (Coordinate c)
          : coord(std::move(c)), left(nullptr), right(nullptr) { }

  15. #15
    Registered User
    Join Date
    Jun 2013
    Posts
    25
    thanks a ton for that, but seriously I'm an idiot... it's definitely time to go get some sleep now after that... ><

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 03-08-2012, 06:12 PM
  2. total nodes in a tree
    By BEN10 in forum C Programming
    Replies: 5
    Last Post: 01-10-2010, 11:37 AM
  3. Binary Tree - sum of nodes
    By Tiffanie in forum C++ Programming
    Replies: 1
    Last Post: 09-15-2008, 08:49 AM
  4. Binary tree not inserting nodes correctly
    By jk1998 in forum C++ Programming
    Replies: 7
    Last Post: 09-22-2007, 12:37 PM
  5. number of nodes in tree
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2002, 06:49 AM