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

• coredump: For example, the Linux kernel coding style favors 8 spaces indent (kernel.org/doc/Documentation/CodingStyle)
• raptortech97: @coredump Oh wow, I didn't realize that!

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?