Tree structure - incorrect children

Question

I'm trying to build simple structure in C++. It should be similar to AVL tree.

Everything is OK when I build a simple tree with three nodes in main() function.

The problem is when I try use insert() function. The first argument of this function contains information where put the value from the second argument.

Here is the code:

#include <numeric>
#include <vector>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct Node {
    Node* left;
    Node* right;
    Node* parent;
    int value;
    int count_leafs;
    int height;
};

Node* root;


void insert2(int p, int value, Node* node, int left) 
{
    //printf("insert %d %d - (%d, %d) %d \n", p, value, node->left, node->right, left);

    if (root == NULL) {
        //  creating a tree root

        Node new_node;
        new_node.left = NULL;
        new_node.right = NULL;
        new_node.parent = NULL;

        root = &new_node;

        root->value = value;
        root->count_leafs = 1;
        root->height = 1;
        return;
    }

    if (node->left == NULL && node->right == NULL) {
        //  joining value to the leaf

        Node new_parent;
        new_parent.count_leafs = 2;
        new_parent.height = 2;
        new_parent.value = node->value + value;
        new_parent.parent = node->parent;
        new_parent.left = NULL;
        new_parent.right = NULL;

        Node new_leaf;
        new_leaf.value = value;
        new_leaf.count_leafs = 1;
        new_leaf.left = NULL;
        new_leaf.right = NULL;
        new_leaf.height = 1;
        new_leaf.parent = &new_parent;

        new_parent.left = &new_leaf;
        new_parent.right = node;


        if (node->parent != NULL && node->parent->left != NULL && node->parent->left == node) {
            printf("a");
            node->parent->left = &new_parent;
        }

        if (node->parent != NULL && node->parent->right != NULL && node->parent->right == node) {
            printf("b");
            node->parent->right = &new_parent;  
        }

        node->parent = &new_parent;

        return;
    }

    //printf("GOTO: %d %d \n", left + node->left->count_leafs, p);

    node->value += value;
    node->count_leafs += 1;

    if (left + node->left->count_leafs + 1 >= p) {
        //printf("W left\n");
        insert2(p, value, node->left, left);
    } else {    
        //printf("W right\n");
        insert2(p, value, node->right, left + node->left->count_leafs);
    }
}


void insert(int p, int value) 
{
    insert2(p, value, root, 0);
}

int main() 
{
    Node new_root;
    root = NULL;

    new_root.value = 10;
    new_root.height = 2;
    new_root.count_leafs = 2;
    new_root.parent = NULL;
    root = &new_root;

    Node left;
    left.value = 6;
    left.height = 1;
    left.count_leafs = 1;
    left.parent = root;
    left.left = NULL;
    left.right = NULL;

    Node right;
    right.value = 4;
    right.height = 1;
    right.count_leafs = 1;
    right.parent = root;
    right.left = NULL;
    right.right = NULL;

    root->left = &left;
    root->right = &right;

    // PLACE A

    insert(0, 1);

    // PLACE B

    return 0;
}

As you see before PLACE A is building a tree with 3 nodes. It look like this in PLACE A:

  10
 /  \
6    4

Next, in a line between PLACE A and PLACE B, I want to add a new node. After that (in PLACE B) the tree should looks like this:

But I gets something like this:

            11
           /  \
  1972250912   4
     / \
    2   2

I can't figure out what is wrong. It should be the problem in insert2() function, but I can't find it.

Do you see it? Thanks in advance for you help!

Reason #948452 not to link code to a 3rd party site, the VPN at work blocked that site, so I cannot see your code. So even if I wanted to help, I cannot. Please post a small reproducable example of your problem here and explain specifically what is not working — Cory Kramer, May 15 '15 at 18:36

score 2 · Accepted Answer · edited May 23 '17 at 10:26

The cause of a such behavior is that you use scope variables out of the scope. You must not use the pointer that points to the scope variable out of that scope. Scope variables exists only withing the scope were they were declared. If decide to access a scope variable out of the scope, you will access some piece of stack that would have some other data overwritten that variable that would result in undefined behavior.

I mean, that you must NOT do like this:

if (root == NULL) 
{
    Node new_node;
    root = &new_node;
    return;
}

You may use operator new to create a new instance of struct Node in the heap and use it later.

if (root == NULL) 
{
    root = new Node;
    return;
}

But you have to delete this node later. Or you may use smart pointers, see this.

Read this and this for more information.

The code below do just what you expected. However it does not delete created nodes that would result in memory leak, so this code have to be improved, but this is a separate issue.

#include <numeric>
#include <vector>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct Node {
    Node* left;
    Node* right;
    Node* parent;
    int value;
    int count_leafs;
    int height;
};

Node* root;


void insert2(int p, int value, Node* node, int left)
{
    //printf("insert %d %d - (%d, %d) %d \n", p, value, node->left, node->right, left);

    if (root == NULL) {
        //  creating a tree root

        Node* new_node = new Node;
        new_node->left = NULL;
        new_node->right = NULL;
        new_node->parent = NULL;

        root = new_node;

        root->value = value;
        root->count_leafs = 1;
        root->height = 1;
        return;
    }

    if (node->left == NULL && node->right == NULL) {
        //  joining value to the leaf

        Node* new_parent = new Node;
        new_parent->count_leafs = 2;
        new_parent->height = 2;
        new_parent->value = node->value + value;
        new_parent->parent = node->parent;
        new_parent->left = NULL;
        new_parent->right = NULL;

        Node* new_leaf = new Node;
        new_leaf->value = value;
        new_leaf->count_leafs = 1;
        new_leaf->left = NULL;
        new_leaf->right = NULL;
        new_leaf->height = 1;
        new_leaf->parent = new_parent;

        new_parent->left = new_leaf;
        new_parent->right = node;


        if (node->parent != NULL && node->parent->left != NULL && node->parent->left == node) {
            printf("a");
            node->parent->left = new_parent;
        }

        if (node->parent != NULL && node->parent->right != NULL && node->parent->right == node) {
            printf("b");
            node->parent->right = new_parent;
        }

        node->parent = new_parent;

        return;
    }

    //printf("GOTO: %d %d \n", left + node->left->count_leafs, p);

    node->value += value;
    node->count_leafs += 1;

    if (left + node->left->count_leafs + 1 >= p) {
        //printf("W left\n");
        insert2(p, value, node->left, left);
    }
    else {
        //printf("W right\n");
        insert2(p, value, node->right, left + node->left->count_leafs);
    }
}


void insert(int p, int value)
{
    insert2(p, value, root, 0);
}

int main()
{
    Node new_root;
    root = NULL;

    new_root.value = 10;
    new_root.height = 2;
    new_root.count_leafs = 2;
    new_root.parent = NULL;
    root = &new_root;

    Node left;
    left.value = 6;
    left.height = 1;
    left.count_leafs = 1;
    left.parent = root;
    left.left = NULL;
    left.right = NULL;

    Node right;
    right.value = 4;
    right.height = 1;
    right.count_leafs = 1;
    right.parent = root;
    right.left = NULL;
    right.right = NULL;

    root->left = &left;
    root->right = &right;

    // PLACE A

    insert(0, 1);

    // PLACE B

    return 0;
}

Tree structure - incorrect children

1 Answers1