Home > A binary tree node insertion function

DirectorySync is a directory synchronizing and backup utility providing automated, real-time syncing and scheduled, configurable backups at an affordable price.

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

And 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

Filed under: C Programming,Low Level Posted by: Codehead

Do you have any questions? ask here.

Follow me on Twitter.

1 Comment »

Afnan:

Hi ,

I’m sorry to inconvenience U;

but I have a problem in the tree can U help Me ?

in this function I have seen run time error I don’t Know where problem

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

void insert()
{

Node *New=new Node;
New->Data=”president”;
New->LSubtree=NULL;
New->RSubtree=NULL;
New=root;

Node *p;
p = (Node *)malloc(sizeof(Node));// here problem & if I construct for this mode root->LSubtree=p;
root->LSubtree=new Node;
root->LSubtree->Data=”VP Support”;
root->LSubtree->LSubtree=NULL;
root->LSubtree->RSubtree=NULL;
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Is there something wrong ?

thank U

Comment