Red Black Tree Implementation

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->tail = lnode;
node->is_red = true;
return node;
}
if (strcmp(k, root->key) < 0) {
} else if (strcmp(k, root->key) > 0) {
} 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 *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->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;
}

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

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

• For example, the Linux kernel coding style favors 8 spaces indent (kernel.org/doc/Documentation/CodingStyle) Oct 31 '14 at 7:59
• @coredump Oh wow, I didn't realize that! Oct 31 '14 at 10:07
• 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?