11
\$\begingroup\$

I would like some feedback on my red black tree implementation. Anything is fine. I've debugged this and it seems to be working fine, however I may have missed something.

Basically, this is a red black tree that stores character strings as keys and the passage that contains those strings as values. Since these keys are able to be repeated, they form a linked list as well.

    TNODE *tree_add(TNODE *root, const KEY k, const VALUE v) {
        LNODE *lnode = NULL;
        if (root == NULL) {
                TNODE *node = talloc(k);
                lnode = lalloc(v);
                node->head = lnode;
                node->tail = lnode;
                node->is_red = true;
                return node;
        }
        if (strcmp(k, root->key) < 0) { 
                root->left = tree_add(root->left, k, v);
        } else if (strcmp(k, root->key) > 0) {  
                root->right = tree_add(root->right, k, v);
        } else {
                if (strcmp(k, root->key) == 0) {
                        lnode = lalloc(v);
                        root->tail->next = lnode;
                        root->tail = lnode;
                        root->tail->next = NULL;
                }
        }
        if (is_red(root->right) && !is_red(root->left)) {
                root = rotate_left(root);
        }
        if (is_red(root->left) && is_red(root->left->left)) {
                root = rotate_right(root);
        }
        if (is_red(root->left) && is_red(root->right)) {
                flip_colors(root);
        }
        return root;

}

Here are TNODE and LNODE:

    // LNODE is the data structure for a singly linked list.
typedef struct lnode {
  VALUE val;          // A pointer to the value stored in the linked list.
  struct lnode *next; // Pointer to the next item in the list; it should be NULL if there is no successor.
} LNODE;

typedef struct tnode {
  KEY key;             // Search key for this binary search tree node.
  struct tnode *right; // Right child.
  struct tnode *left;  // Left child.

  LNODE *head; // Head of the linked list storing the values for the search key.
  LNODE *tail; // Tail of the linked list storing the values for the search key.

  bool is_red; // Flag use only in red-black trees to denote redness.
} TNODE;

Here are some more functions: TALLOC, LALLOC, and rotate

    TNODE *talloc(const KEY k) {
        TNODE *tnode = malloc(sizeof(TNODE));
        if (tnode == NULL) {
                return NULL;
        }
        tnode->key = k;
        tnode->is_red = false;
        tnode->head = NULL;
        tnode->tail = NULL;
        tnode->right = NULL;
        tnode->left = NULL;
        return tnode;
}

LNODE *lalloc(const VALUE v) {
        LNODE *lnode = malloc(sizeof(LNODE));
        if (lnode == NULL) {
                return NULL;
        }
        lnode->val = v;
        lnode->next = NULL;
        return lnode;
}

TNODE *rotate_left(TNODE *h) { 
        TNODE *x = h->right;
        h->right = x->left;
        x->left = h;
        x->is_red = h->is_red;
        h->is_red = true;
        return x;

}

TNODE *rotate_right(TNODE *h) { 
        TNODE *x = h->left;
        h->left = x->right;
        x->right = h;
        x->is_red = h->is_red;
        h->is_red = true;
        return x;
}

void flip_colors(TNODE *h) { 
        h->is_red = true;
        h->left->is_red = false;
        h->right->is_red = false;
}
\$\endgroup\$
1
\$\begingroup\$

Implementation Issue:

I would call strcmp(k, root->key) once:

int cmpval;
if (root == NULL)
{
    ...
}
else
{
    cmpval = strcmp(k, root->key);
    if (cmpval < 0)
    {
        ...
    }
    else if (cmpval > 0)
    {
        ...
    }
    else // if (cmpval == 0)
    {
        ...
    }
}

Design Issue:

The use of strcmp essentially couples the KEY type with a null-terminated string type.

You should try to decouple them in order to allow the user to easily change the KEY type.

One way to do it is by implementing a comparison function alongside the KEY type:

typedef char* KEY;

int compare(const KEY key1,const KEY key2)
{
    return strcmp(key1,key2);
}

Of course, this does not really decouple KEY from char*, but at least it lets the user know that changing the KEY type must be followed by changing the implementation of the compare function.

There is probably a design-pattern specifically for the case at hand...

\$\endgroup\$
2
\$\begingroup\$

This isn't quite a full review, but here goes anyway:

  • It looks like you're using 8-space indents. That's quite a lot. I think 4 is more common, but it is a matter of preference and it is consistent, so it's definitely not wrong

  • You have KEY, presumably a typedef of char*, but then you call strcmp on it. If you want it to be general across key types (which is a pretty good idea IMO), you should pass in a comparator function that takes two keys as arguments.

  • I'm going to assume that the other fields of TNODE exist for some reason, but is there a chance you could move them out to rbtree_t and leave TNODE smaller?

  • I don't know the naming conventions for types in C, so don't take this as implicit agreement or disagreement

  • talloc and lalloc probably don't need to be their own functions; malloc(sizeof(TNODE)) is probably sufficient

\$\endgroup\$
2
\$\begingroup\$
  • A (strcmp(k, root->key) == 0) test seems redundant: cases of < 0 and > 0 are already excluded.

  • I trust that talloc properly initializes right and left pointers. It would be nice to see the implementation though. Same for lalloc.

  • rotate_left, rotate_right and flip_colors are the key to the proper RB-tree implementation. Can you post the code for them as well?

\$\endgroup\$

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.