C++ pointers not working?

Question

I have a problem with working with c++ pointers. I'm trying to code a splay tree by using a Node struct and Tree struct. However, upon testing, I have encountered a problem. The portion of my code that's not working is below:

struct Node {
    Node* l, *r, *p;
    int v;
    Node() {}
    Node(int _v, Node* _p) : v(_v), p(_p) {}
};

struct Tree {
    Node* root;

    Tree() : root(0) {}

    //...

    void insert(int k) {
        if (!root) {
            root = new Node(k, 0);
            return;
        }
        Node* cur = new Node();
        cur->v = root->v;
        while (1) {
            int x = cur->v;
            cout << x << endl;
            return;
            if (k <= x) {
                //cout << x << endl;
                //return;
                if (!cur->l) {
                    cur->l = new Node(k, cur);
                    //splay(cur->l);
                    return;
                } else cur = cur->l;
            } else {
                if (!cur->r) {
                    cur->r = new Node(k, cur);
                    //splay(cur->r);
                    return;
                } else cur = cur->r;
            }
        }
    }

    //...
};

int main() {
    Tree t = Tree();
    t.insert(1);
    t.insert(5);
    return 0;
}

First, I inserted a node with value 1 in the tree; since there was no root, the tree assigned its root as a new node with value 1. Then, when I inserted 5 into the tree, something weird happened. If you leave the code like it is (keeping the first cout), then it will print out 1 for x. However, if you comment out the first cout and return and uncomment the second cout and return, you'll find that it prints out a random garbage number for x, even though no modifications were made. Can somebody tell me what's wrong?

Answer 1

C++ does not initialize class members automatically.

struct Node {
    Node* l, *r, *p;
    int v;
    Node() {}
    Node(int _v, Node* _p) : v(_v), p(_p) {}
};

When you create a new node in your code C++ allocates a piece of memory for the Node but it will not clear it. So the values of l, r & p will be whatever was there.
In your algorithm the tests: if (!cur->r) & (!cur->l) currently fail because there is uninitialized garbage in the nodes and not NULL.
As a result when you try to insert the second node the algorithm thinks that there is a valid node to the right of root. And tries to read the memory there and the value there which is the junk x you see. Depending on the value of the junk it may also crash for some people running the code :)

Also I'm 99.9% certain that Node* cur should be a pointer to a Node in the tree and not a new node so: Node* cur = new Node(); cur->v = root->v; is wrong and should be Node* cur = root;

Proper Initialization - In c++11 you can do:

struct Node {
    Node* l = nullptr;
    Node *r = nullptr;
    Node *p = nullptr;
    int v   = 0;
    Node() {}
    Node(int _v, Node* _p) : v(_v), p(_p) {}
};

Otherwise

struct Node {
    Node* l;
    Node *r;
    Node *p;
    int v;
    Node() : l(NULL), r(NULL), p(NULL), v(0){}
    Node(int _v, Node* _p) : l(NULL), r(NULL), p(_p), v(_v) {}
};

You should initialize members of a class in the same order they were defined.

Now there are a lot of other things that are problematic in the code:

Tree seems to allocate lots of nodes but does not release any memory. (easiest to just use unique_ptr for l and r and root Node)

Is tree the owner of subnodes? Or should it be Node owning and allocating left and right? (goes away if you use std::unique_ptr for left and right)

You are not initializing the members in the order they are defined. This can cause all kind of errors. (since the compiler reorders initialization without telling you)

Node and Tree handle raw pointers but do not define a proper operator=, copy ctor (or delete them) (goes away if you use unique_ptr)

Tree is missing a dtor to clean allocated memory (goes away if you use unique_ptr)

Upvotes: 6