Kyle Kyle - 1 month ago 7
C Question

Insert function for Ternary Search Tree - C

I am new to C and am trying to code up a data structure, primarily, a ternary search tree. I am working under the assumption (for now) that valid char inputs are being passed in. I am having some issues with my insert function. Note that I am also inserting the original string in the last TSTnode where the last character of str will also be held.

Here is what I have so far

struct TSTnode {
char* word; // NULL if no word ends here
char self;
struct TSTnode *left, *sub, *right;
};


int insert_tst(struct TSTnode** tree, const char* str) {
return _insert(tree, str, 0);
}


int _insert(struct TSTnode** tree, const char* str, int position) {

if((*tree) == NULL) {
*tree = new_tst_node(*(str+position));
position = position + 1;
if(*(str+position) == '\0') {
(*tree)->word = strcpy((*tree)->word,str);
return 1;
}
}

else if ((*tree)->self > *(str+position)) {
position = position + 1;
_insert( &((*tree)->left), str, position);
}

else if ((*tree)->self < *(str+position)) {
position = position + 1;
_insert( &((*tree)->right), str, position);
}
else {
position = position + 1;
_insert( &((*tree)->sub), str, position);
}
return 0;

}




struct TSTnode* new_tst_node(char self) {
struct TSTnode* newNode = (struct TSTnode*) malloc(sizeof(struct
TSTnode));

if (newNode == NULL) {
return NULL;
}
newNode->word = NULL;
newNode->self = self;
newNode->left = NULL;
newNode->right = NULL;
newNode->sub = NULL;

return newNode;
}


Here is how I am testing:

struct TSTnode* tree = NULL;
char* words[1] = {"hello"};

for (int i = 0; i < 1; i++) {
if (insert_tst(&tree, words[i]) == 0) {
//print some error
}
else { //success }


EDIT - My issue is that none of my conditional branches are being taken and the insert function simply goes straight to return 0.

Answer Source

Note: You confusingly use tree for both TSTnode* and TSTnode**. I'm going to use tree_ptr for the latter, and pretend that you did the same.


Your claim is false. The body of if((*tree_ptr) == NULL) is executed. You do have a number of problems, though.

  1. You don't handle the case where *tree_ptr == NULL && *(str+position+1) != '\0'.

  2. You don't correctly handle the case where *tree_ptr != NULL && *(str+position+1) == '\0'.

  3. You always return 0 when *tree_ptr != NULL || str[1] != '\0'.

  4. You never allocate word, but you deference it. The thing is, you shouldn't be storing the string again anyway!

  5. You don't handle the case where str[0] == '\0' (empty string).

Fixed:

int insert_tst(struct TSTnode** tree_ptr, const char* str) {
    if (!*str)
        return 0;  /* Zero-length strings are not supported. */

    return insert_tst_helper(tree_ptr, str, 0);
}

int insert_tst_helper(struct TSTnode** tree_ptr, const char* str, int position) {
    if (*tree_ptr == NULL) {
        *tree_ptr = new_tst_node(*(str+position));
        if (*tree_ptr == NULL)
            return 0;  /* Memory allocation error. */
    }

    if (*(str+position+1) == '\0') { /* If the next char is a NUL */
        (*tree_ptr)->is_word = 1;
        return 1;
    }

    else if ((*tree_ptr)->self > *(str+position)) {
        position = position + 1;
        return insert_tst_helper( &((*tree_ptr)->left), str, position);
    }

    else if ((*tree_ptr)->self < *(str+position)) {
        position = position + 1;
        return insert_tst_helper( &((*tree_ptr)->right), str, position);
    }
    else {
        position = position + 1;
        return insert_tst_helper( &((*tree_ptr)->sub), str, position);
    } 
}

Untested.


Let's clean this up, though.

  • *(str+position)
    simplifies to
    str[position]
  • ch == '\0'
    simplifies to
    ch == 0
    then to
    !ch
  • position = position + 1; return insert_tst_helper(..., str, position);
    simplifies to
    ++position; return insert_tst_helper(..., str, position);
    then to
    return insert_tst_helper(..., str, position+1);
    then to
    return insert_tst_helper(..., str+1, 0);
    then to
    return insert_tst(..., str+1);
  • Why is recursion being used at all???

Fixed:

int insert_tst(struct TSTnode** tree_ptr, const char* str) {
    if (!*str)
        return 0;  /* Zero-length strings are not supported. */

    while (1) {
        if (*tree_ptr == NULL) {
            *tree_ptr = new_tst_node(*str);
            if (*tree_ptr == NULL)
                return 0;  /* Memory allocation error. */
        }

        if (!*(str+1)) { /* If the next char is a NUL */
            (*tree_ptr)->is_word = 1;
            return 1;
        }

        int cmp = *str - (*tree_ptr)->self;
        if      (cmp < 0) { tree_ptr = &( (*tree_ptr)->left  ); }
        else if (cmp > 0) { tree_ptr = &( (*tree_ptr)->right ); }
        else              { tree_ptr = &( (*tree_ptr)->sub   ); }

        ++str;
    }
}

Untested.