3
\$\begingroup\$

I'm a novice C programmer (moving onto C++ soon) and I've tried to implement a basic (search,insertion,deletion) generic unbalanced BST whilst adhering to a few OO design principles. I'm looking for some feedback and advice from seasoned C programmers on my code and style.

tree.h

#ifndef TREE_H
#define TREE_H

struct btree_node {
    struct btree_node *left;
    struct btree_node *right;
    void *item;
};

static void btree_free_node(struct btree_node *node);

static struct btree_node* find_min_node(struct btree_node *node);

static struct btree_node* find_max_node(struct btree_node *node);

int btree_search(struct btree_node *root, void *item, int (*comp)(const void*,const void*));

int btree_insert(struct btree_node **root, void *item, unsigned int size, int (*comp)(const void*,const void*));

struct btree_node* btree_delete_node(struct btree_node *root, void *item, unsigned int size, int (*compare_node)(const void*,const void*));

void btree_print(struct btree_node *root, void (*print)(const void *));

void btree_free(struct btree_node *root);

#endif

tree.c

#include "tree.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int btree_insert(struct btree_node **root, void *item, unsigned int size, int (*compare_node)(const void*,const void*)) {
    // Insert the root    
    if (*root == NULL) {
        *root = malloc(sizeof(struct btree_node));
        if (!(*root)) {
            fprintf(stderr,"malloc() fail\n");
            return 0;
        }
        (*root)->left = (*root)->right = NULL;
        (*root)->item = malloc(size);
        if (!((*root)->item)) {
            fprintf(stderr,"malloc() fail\n");
            free(*root);
            return 0;
        }
        memcpy((*root)->item,item,size);
    } else {
        if (compare_node((*root)->item,item) > 0) {
            //Insert left
            btree_insert(&(*root)->left,item,size,compare_node);
        } else {
            //Insert right
            btree_insert(&(*root)->right,item,size,compare_node);
        }
    }
    return 1;
}

static void btree_free_node(struct btree_node *node) {
    free(node->item);
    free(node);
}

static struct btree_node* find_min_node(struct btree_node *node) {
    node = node->right;
    while (node) node = node->left;
    return node;
}

static struct btree_node* find_max_node(struct btree_node *node) {
    node = node->left;
    while (node) node = node->right;
    return node;
}

struct btree_node* btree_delete_node(struct btree_node *root, void *item, unsigned int size, int (*compare_node)(const void*,const void*)) {
    if (root == NULL) return root;
    else if (compare_node(item,root->item) < 0) root->left = btree_delete_node(root->left,item,size,compare_node);
    else if (compare_node(item,root->item) > 0) root->right = btree_delete_node(root->right,item,size,compare_node);
    else {
        // 1. Deleting a node with two children
        if ( root->left && root->right ) {
            struct btree_node *min_node = find_min_node(root);
            if (!min_node) {
                min_node = find_max_node(root);
            }
            memcpy(root->item,min_node->item,size);
            root->right = btree_delete_node(root->right,min_node->item,size,compare_node);
        } else if (root->left) {
            // 2. Deleting a node with one child (left)
            struct btree_node *node_delete = root;
            root = root->left;
            btree_free_node(node_delete);
        } else if (root->right) {
            // 2. Deleting a node with one child (right)
            struct btree_node *node_delete = root;
            root = root->right;
            btree_free_node(node_delete);
        } else {
            // 3. Deleting a leaf node
            btree_free_node(root);    
            root = NULL;
        }
    }
    return root; 
}

void btree_print(struct btree_node *root, void (*print_node)(const void *)) {
    if (root) {
        print_node(root->item);
        btree_print(root->left,print_node);
        btree_print(root->right,print_node);
    }
}

void btree_free(struct btree_node *root) {
    if (root) {
        free(root->item);
        btree_free(root->left);
        btree_free(root->right);
        free(root);
    }
}

int btree_search(struct btree_node *root, void *item, int (*compare_node)(const void*,const void*)) {
    if (root == NULL) return 0;
    else if (compare_node(item,root->item) > 0) return btree_search(root->right, item, compare_node);
    else if (compare_node(item,root->item) < 0) return btree_search(root->left, item, compare_node);
    else return 1;
}

test.c

#include <stdio.h>
#include "tree.h"

void print_node(const void *node) {
    printf("%d\n",*(int*)node);
}

int compare_node(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main() {

    struct btree_node *root = NULL;
    for (int i=0; i<10; i++) {
        btree_insert(&root,&i,sizeof(int),compare_node);
    }

    int a = 6;
    printf("found %d ? %d\n",a,btree_search(root, &a, compare_node));
    a = 100;
    printf("found %d ? %d\n",a,btree_search(root, &a, compare_node)); 
    a = 6;
    btree_delete_node(root, &a, sizeof(int),compare_node); 
    printf("found %d ? %d\n",a,btree_search(root, &a, compare_node));   

    btree_print(root,print_node);
    btree_free(root);
    return 0;
}

To compile and test

gcc test.c tree.c -o test.o -O3

./test.o

found 6 ? 1
found 100 ? 0
found 6 ? 0
0
1
2
3
4
5
7
8
9

Memory leak check with Valgrind

valgrind --leak-check=full --show-leak-kinds=all ./test.o

==91414== HEAP SUMMARY:
==91414==     in use at exit: 0 bytes in 0 blocks
==91414==   total heap usage: 21 allocs, 21 frees, 1,304 bytes allocated
==91414== 
==91414== All heap blocks were freed -- no leaks are possible
\$\endgroup\$
3
\$\begingroup\$
  • A bug: btree_insert returns 1 even if a recursive call fails. You shall return exactly what a recursive call returns:

        if (compare_node(....)) {
            return btree_insert(....);
        else {
            return btree_insert(....);
        }
    

    (and return 1; from the successful base case).

  • A serious bug: find_min_node and find_max_node always return NULL.

    Notice that your test builds a degenerate tree - no node having 2 children - and hence doesn't exercise those two functions.

  • Returning a boolean indicator from btree_search throws away important information. Most likely a caller is interested in the item of a found node, or even the node itself. Consider returning btree_node *. One perk benefit of such approach is that you could call btree_search at the beginning of btree_delete_node.

  • As a side note, insert and search in BSTs are naturally iterative. Consider eliminating the recursion.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for your suggestions. I went for the recursive solution as it seemed easiest but the recursive insert is quite slow as I've found. \$\endgroup\$ – Nubcake Aug 4 '17 at 14:04
2
\$\begingroup\$

One thing you can do is consolidate the storage of the item and the node itself.

struct btree_node {
    struct btree_node *left;
    struct btree_node *right;
    char item[0];
};
if (!(*root)) {
    fprintf(stderr,"malloc() fail\n");
    return 0;
}
*root = malloc(sizeof(struct btree_node)+size);
memcpy((*root)->item,item,size);

This avoids the second allocation.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer. I was unaware such a trick existed in C! \$\endgroup\$ – Nubcake Aug 3 '17 at 15:11

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.