Adding a new node in an AVL tree

Question

I was working on a class assignment today and I wrote this code which works perfectly fine. It looks tho kind of has too much 'if statements' in it, and I was thinking that it could be written much better than this. (I'm still a beginner in C).

Do you suggest any new techniques that I could use/learn to avoid so many if statements and how could you improve this code without making it much longer or complex?

The code is a part of much bigger code to add a new node in an AVL tree.

if (avlt->root == NULL) {
    new = &(avlt->root);   
    parent = NULL;
}
if (avlt->root != NULL) {
    parent = avlt->root;
    while (1)
    {
        if (parent->value > value)
        {
            if (parent->left) parent = parent->left;
            else
            {
                new = &(parent->left);
                break;
            }
        }
        else if (parent->value < value)
        {
            if (parent->right) parent = parent->right;
            else
            {
                new = &(parent->right);
                break;
            }
        }
        else return;
    }
}

These are the structs, maybe they can be useful for you to understand the code:

struct AVLNode {
  struct AVLNode* left;     
  struct AVLNode* right;    
  struct AVLNode* parent;
  int value;
  int height;
};

struct AVLTree {
  struct AVLNode* root;
  int numberOfNodes;
};

typedef struct AVLNode AVLNode;
typedef struct AVLTree AVLTree;

Answer 1

Complexity

One method for determining how complex your code is, is called cyclomatic complexity. You basically count the number of branches in the code to determine its complexity. I count about 10 in the above code snippet. A cyclomatic complexity of 10 is often considered the maximum you should have in good readable code. (This is of course subjective.) By that standard, this code is fine. I do think the code could be made more clear, though.

Infinite Loops

I generally hate infinite loops in code unless it's some top-level thing like an event loop that realistically should never stop. The infinite loop you've created is not one of those cases. It has a very clear criteria for stopping. When the value is either greater than the greatest value along this path, or less than the minimum value along this path, or equal to any value along the path. Fixing that will make the code clearer, though I don't know if it will reduce the number of conditions to check. It might be worth breaking it out into a separate function. Something like this:

void whateverFunctionThisIs(AVLTree* avlt)
{
    //...
    if (avlt->root == NULL) {
        new = &(avlt->root);   
        parent = NULL;
    }
    else
    {
        new = findPositionInTree(avlt->root);
    }

    if (new == NULL) {
        return;
    }
    // ...
}

That immediately reduces the complexity of that function from 10 to 3. Now we can rewrite the loop in its own function like this:

AVLNode* findPositionInTree(AVLNode* parent)
{
    struct AVLNode* new = NULL;

    int found = 0;
    do {
        if (parent->value > value) 
        {
            if (parent->left) 
            {
                parent = parent->left;
            }
            else 
            {
                new = &(parent->left);
                found = 1;
            }
        }
        else if (parent->value < value) 
        {
            if (parent->right) 
            {
                parent = parent->right;
            }
            else 
            {
                new = &(parent->right);
                found = 1;
            }
        }
        else 
        {
            found = 1;
        }
    } while (!found);

    return new;
}

Even though we have the same number of if statements, it seems clearer to me without the break and return statements. And this function only has a cyclomatic complexity of 8.

Reducing ifs

You could reduce the number of if statements if you don't actually need to use parent after the loop ends by inverting the sense of the inner-most ifs. For example, instead of:

if (parent->right) 
{
    parent = parent->right;
}
else
{
    new = &(parent->right);
    found = 1;
}

you could do this:

if (parent->right != NULL)
{
    new = &(parent->right);
    found = 1;
}
parent = parent->right;

At this point parent is NULL so you can't use it for anything in the future, so I really don't like that idea. But it does eliminate 2 if statements thereby reducing your complexity. (If you're using the infinite loop, then the found = 1; becomes just a break and parent is no longer NULL. But that feels gross to me.)