5
\$\begingroup\$

I'm working on a binary space partition tree.

For the time being, the nodes are only inserted into the right. A node that has children will have 0 as data. Here are the insertion rules.

If the insertion node has data and no parent, the current data becames the left child, and the node to insert goes to the right.

1       0
^ ---> / \
      1   2

If the node has a parent, is a the left child of the parent and has data, the node is reinserted in the parent's right node, and the inserted node takes its place

  0          0
 / \        / \ 
1   2 ---> 3   0
^             / \
             2   1

I'd like to have a feedback on my insert function. I put a goto statement to not repeat code, but I'd like to avoid it to make the function more clear.

Live on Coliru with verbose output

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

struct node
{
    int data;

    struct node* parent;
    struct node* left;
    struct node* right;
};

struct node* create_node(int i)
{
    struct node* n = calloc(1, sizeof(struct node));

    n->data = i;

    n->parent = NULL;
    n->left = NULL;
    n->right = NULL;

    return n;
}

void destroy_node(struct node* n)
{
    if (n->left != NULL)
    {
        destroy_node(n->left);
    }

    if (n->right != NULL)
    {
        destroy_node(n->right);
    }

    free(n);
}

void insert(struct node* i, struct node* n)
{
    printf("insert at %d node %d\n", i->data, n->data);
    // TODO : insert rightmost or leftmost
    if (i->parent != NULL)
    {
        if (i->parent->left == i)
        {
            // if insert node is left
            struct node* p = i->parent;
            i->parent = NULL;
            insert(p->right, i);
            p->left = n;
            n->parent = p;
            return;
        }
        else if (i->parent->right == i)
        {
            // if insert node is right
            if ((i->left == NULL) && (i->right == NULL))
            {
                // if insert node is rightmost
                goto insert;
            }

            if (i->right != NULL)
            {
                // if right node is not rightmost
                insert(i->right, n);
                return;
            }
        }
    }
    else if (i->parent == NULL)
    {
        // if insert node is root
        if ((i->left == NULL) && (i->right == NULL))
        {
            // if insert node has no children
            goto insert;
        }
        else if (i->right != NULL)
        {
            // if right child is not null
            insert(i->right, n);
            return;
        }
    }

insert: ;
    int value = i->data;
    i->data = 0;

    struct node* left = create_node(value);
    left->parent = i;

    n->parent = i;

    i->left = left;
    i->right = n;

    return;
}

int main()
{
    // A
    struct node* root = NULL;

    // B
    root = create_node(1);

    assert(root->data == 1);
    assert(root->left == NULL);
    assert(root->right == NULL);

    // C
    insert(root, create_node(2));

    assert(root->data == 0);
    assert(root->left->data == 1);
    assert(root->right->data == 2);

    // X
    insert(root->right, create_node(3));

    assert(root->right->data == 0);
    assert(root->right->left->data == 2);
    assert(root->right->right->data == 3);

    // Y
    insert(root->right->left, create_node(4));

    assert(root->right->left->data == 4);
    assert(root->right->right->data == 0);
    assert(root->right->right->left->data == 3);
    assert(root->right->right->right->data == 2);

    // Z
    insert(root->right->left, create_node(5));

    assert(root->right->left->data == 5);
    assert(root->right->right->left->data == 3);
    assert(root->right->right->right->left->data == 2);
    assert(root->right->right->right->right->data == 4);

    destroy_node(root);

    return 0;
}
\$\endgroup\$
2
\$\begingroup\$

Your insertion requirements are mighty strange, but I guess you have some reason for them, so I won't comment further on that.

  • One of the huge benefits of having a parent pointer in each node is that you can get rid of recursion entirely. In your case, getting rid of recursion will improve performance and stack consumption significantly. Since your recursion is not tail recursion, there is no sensible way the compiler can optimize it - so the result will be very inefficient code. Recursion should be avoided in general, since it slow, memory intense, dangerous and sometimes hard to read.

    Instead of using recursion, you can simply loop down the list of nodes until you hit NULL in a leaf, checking if each node sates the insert condition along the way. Keep track of the current node by pointing at it with a local pointer, rather than a pointer passed as parameter to a recursive function.

    If you need to step up in the tree, you do it by setting the current pointer to its parent, which is then equivalent of returning from a recursive function.

  • Your goto and multiple returns is a bit hard to read and follow. By getting rid of the recursion, you'll get rid of all of these too. Your new function should look something like this pseudo:

    insert function
      if we are at root
        special case, handle it
      else
        loop looking for candidate to insert
        if candidate found, set pointer to it and break loop
    
      if candidate found
        create node
        insert node at candidate
    
  • Similarly, your destroy_node function could be rewritten with a loop instead of recursion, although performance is less of an issue here.

  • The create_node function is mostly pointless, it is just a call to malloc/calloc and not much else of value. You set all the node's pointers manually anyway, so setting them to NULL in advance adds nothing. You might as well skip this function and just call malloc. (Also, the mandatory remark: you should check if malloc returns NULL and add some error handling.)

  • It is a bad idea to pick the same identifier for the function, as for the labels inside it. Yes they reside in different namespaces, but that's no excuse for using the same name. Always use distinctive names for every single identifier in your program, no matter if it is a function, variable, label, macro etc.

  • Having an empty return ; at the end of a void function fills no purpose.

  • The printf should naturally not be part of the insert algorithm, but I take it that's just debug code that will be removed later(?).

  • Minor remark: since you initialize all members of the struct, there is no reason to use calloc. malloc will be slightly faster.

  • int main() is obsolete style in C. You should use int main (void) (or alternatively argc/argv). Not to be confused with C++, where int main() is fine and means the same thing as int main (void).

\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback! The insertion requirements are weird because I tried to replicated BSPWM's automatic mode without looking at the code, but the insertion policy made no sense so I decided to go on my own. I will do the modification tonight and edit the main post. \$\endgroup\$ – bl4ckb0ne Apr 3 '18 at 15:20
  • \$\begingroup\$ @Bl4ckb0ne I believe the preferred course of action is to leave the code in the question alone, as others may post answers too, but instead post your fixed code as an answer to your own question. \$\endgroup\$ – Lundin Apr 3 '18 at 15:30
  • \$\begingroup\$ Should I bother about using less recursion if I know the depth will not go far? I think around 8-10 should be the max depth of this tree in my case. \$\endgroup\$ – bl4ckb0ne Apr 3 '18 at 16:03
  • \$\begingroup\$ @Bl4ckb0ne Stack usage aside, recursion will always be the slowest possible solution. If performance is a concern, then getting rid of recursion is the obvious first step. \$\endgroup\$ – Lundin Apr 4 '18 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.