• 1

• 11.9k
• 1
• 20
• 46

#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.)