A binary tree node insertion function
I was working on this for a few days and came up with 3 versions of this function, don’t even ask for the first one.
Here is the second version which is inspired by K&R’s example:
(Just read BTree as Binary Tree)
/** First Version **/ void BTree_Store(BTree *t, char *key, void *elem) { t->root = BTree_Install(t, t->root, key, elem); } Node *BTree_Install(BTree *t, Node *parent, char *key, void *elem) { int cmpResult; if (parent == NULL) parent = BTree_NewNode(t, key, elem); else { cmpResult = t->cmpfn(parent->key, key, BTREE_MAX_KEY_SIZE); if (cmpResult == 0) memcpy(parent->elem, elem, t->elemSize); else if (cmpResult < 0) parent->lnode = BTree_Install(t, parent->lnode, key, elem); else parent->rnode = BTree_Install(t, parent->rnode, key, elem); } return parent; }
The problem with this (or my problem ;)) is that I don’t like creation of stack frames and local variables over and over here, it might need like 40 of them and I knew I could do better so I came up with this version:
/** Second Version **/ void BTree_Store(BTree *t, char *key, void *elem) { Node **n; int cmpResult; n = &t->root; while (*n != NULL) { cmpResult = t->cmpfn((*n)->key, key, BTREE_MAX_KEY_SIZE); if (cmpResult == 0) break; else if (cmpResult < 0) n = &((*n)->lnode); else n = &((*n)->rnode); } if (cmpResult == 0) memcpy((*n)->elem, elem, t->elemSize); else *n = BTree_NewNode(t, key, elem); }
I actually love this version, it’s quick, compact and right to the point.
Here is how the node and the tree structures look like:
struct node { char *key; /* Owned by tree */ void *elem; /* Owned by tree */ struct node *lnode; struct node *rnode; }; typedef struct node Node; struct btree { Node *root; int elemSize; int numNodes; int memUsed; int (*cmpfn)(const char *, const char *, size_t); }; typedef struct btree BTree;
The cmpfn is strncmp by defaults because keys are char *, here are the tree & node construction and destruction functions:
void BTree_Init(BTree *t, int elemSize, int (*cmpfn)(const char *, const char *, size_t)) { t->elemSize = elemSize; t->cmpfn = cmpfn != NULL ? cmpfn : BTREE_DFLT_CMP_FN; t->numNodes = 0; t->memUsed = 0; t->root = NULL; } void BTree_Dispose(BTree *t) { BTree_DisposeNodeRecursive(t, t->root); } static Node *BTree_NewNode(BTree *t, char *key, void *elem) { Node *n; if (BTREE_NODE_SIZE(t, key) > BTREE_MEM_LIMIT) { printf("BTree Error: Not enough memory"); BTree_Dispose(t); exit(0); } n = (Node *) malloc(sizeof(Node)); n->elem = malloc(t->elemSize); memcpy(n->elem, elem, t->elemSize); n->key = (char *) malloc(strlen(key) + 1); /* +1 for '\0' */ strcpy(n->key, key); n->lnode = NULL; n->rnode = NULL; t->memUsed += BTREE_NODE_SIZE(t, key); t->numNodes++; return n; } static void BTree_DisposeNode(BTree * t, Node *n) { t->memUsed -= BTREE_NODE_SIZE(t, n->key); t->numNodes--; free(n->key); free(n->elem); free(n); } static void BTree_DisposeNodeRecursive(BTree *t, Node *n) { if (n->lnode != NULL) BTree_DisposeNodeRecursive(t, n->lnode); if (n->rnode != NULL) BTree_DisposeNodeRecursive(t, n->rnode); BTree_DisposeNode(t, n); }
Here is the BTREE_NODE_SIZE macro:
#define BTREE_NODE_SIZE(t, k) sizeof(Node) + strlen(k) + 1 + t->elemSizeAnd here is the search function:
Node *BTree_FindNode(BTree *t, char *key) { Node *n; int cmpResult; n = t->root; while (n != NULL) { cmpResult = t->cmpfn(n->key, key, BTREE_MAX_KEY_SIZE); if (cmpResult == 0) return n; else if (cmpResult < 0 && n->lnode != NULL) n = n->lnode; else if (n->rnode != NULL) n = n->rnode; else break; } return BTREE_KEY_NOT_FOUND; } void *BTree_Get(BTree *t, char *key) { Node *n; n = BTree_FindNode(t, key); return n != BTREE_KEY_NOT_FOUND ? n->elem : BTREE_KEY_NOT_FOUND; }
The only problem with this tree is that if you store sorted data you will end up with a linked list rather than a binary search tree so I’m working on a self balancing binary search tree which is very chalanging but I love chalanges 
