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-&gt;head = lnode;
                node-&gt;tail = lnode;
                node-&gt;is_red = true;
                return node;
        }
        if (strcmp(k, root-&gt;key) &lt; 0) { 
                root-&gt;left = tree_add(root-&gt;left, k, v);
        } else if (strcmp(k, root-&gt;key) &gt; 0) {  
                root-&gt;right = tree_add(root-&gt;right, k, v);
        } else {
                if (strcmp(k, root-&gt;key) == 0) {
                        lnode = lalloc(v);
                        root-&gt;tail-&gt;next = lnode;
                        root-&gt;tail = lnode;
                        root-&gt;tail-&gt;next = NULL;
                }
        }
        if (is_red(root-&gt;right) &amp;&amp; !is_red(root-&gt;left)) {
                root = rotate_left(root);
        }
        if (is_red(root-&gt;left) &amp;&amp; is_red(root-&gt;left-&gt;left)) {
                root = rotate_right(root);
        }
        if (is_red(root-&gt;left) &amp;&amp; is_red(root-&gt;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-&gt;key = k;
        tnode-&gt;is_red = false;
        tnode-&gt;head = NULL;
        tnode-&gt;tail = NULL;
        tnode-&gt;right = NULL;
        tnode-&gt;left = NULL;
        return tnode;
}

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

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

}

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

void flip_colors(TNODE *h) { 
        h-&gt;is_red = true;
        h-&gt;left-&gt;is_red = false;
        h-&gt;right-&gt;is_red = false;
}
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