Red Black Tree Implementation

Question

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;
}

Answer 1

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

Answer 2

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

Answer 3

• 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?