Binary Search Tree Version 2

Tweet

#include <stdio.h>
#include <stdlib.h> // for exit() functionh
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)
typedef enum {
    STATUS_OK,
    STATUS_MEM_EXHAUSTED,
    STATUS_DUPLICATE_KEY,
    STATUS_KEY_NOT_FOUND
} statusEnum;
typedef int keyType;      
typedef struct
{
    int stuff; 
} recType;
typedef struct nodeTag
{
    struct nodeTag *left;
    struct nodeTag *right;
    struct nodeTag *parent;
    keyType key;                   
   recType rec;               
}nodeType;
nodeType *root = NULL;  
statusEnum insert(keyType key, recType *rec)
{
    nodeType *x, *current, *parent;
    current = root;
    parent = 0;
    while (current) {
        if (compEQ(key, current->key)) 
            return STATUS_DUPLICATE_KEY;
        parent = current;
        current = compLT(key, current->key) ? current->left : current->right;
}
if ((x = malloc (sizeof(*x))) == 0)
   return STATUS_MEM_EXHAUSTED;
    x->parent = parent;
    x->left = NULL;
    x->right = NULL;
    x->key = key;
    x->rec = *rec;

      if(parent)
        if(compLT(x->key, parent->key))
            parent->left = x;
        else
            parent->right = x;
    else
        root = x;

    return STATUS_OK;
}
statusEnum delete(keyType key)
{
    nodeType *x, *y, *z;
     z = root;
    while(z != NULL) {
        if(compEQ(key, z->key)) 
            break;
        else
            z = compLT(key, z->key) ? z->left : z->right;
    }
    if (!z) return STATUS_KEY_NOT_FOUND;
     if (z->left == NULL || z->right == NULL)
        y = z;
    else {
        y = z->right;
        while (y->left != NULL) y = y->left;
    }

    if (y->left != NULL)
        x = y->left;
    else
        x = y->right;

     if (x) x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        root = x;

        if (y != z)
       {
        y->left = z->left;
        if (y->left) y->left->parent = y;
        y->right = z->right;
        if (y->right) y->right->parent = y;
        y->parent = z->parent;
        if (z->parent)
            if (z == z->parent->left)
                z->parent->left = y;
            else
                z->parent->right = y;
        else
            root = y;
        free (z);
    }
    else
         free (y);
    
    return STATUS_OK;
}

statusEnum find(keyType key, recType *rec)
{

    nodeType *current = root;
    while(current != NULL)
   {
        if(compEQ(key, current->key))
        {
            *rec = current->rec;
            return STATUS_OK;
         }
      else
     {
            current = compLT(key, current->key) ? 
                current->left : current->right;
      }
    }
    return STATUS_KEY_NOT_FOUND;
}
int main(int argc, char **argv)  // command line argument
{
    int i, maxnum, random;
    recType *rec;
    keyType *key;
    statusEnum status;
    maxnum = atoi(argv[1]);
    random = argc > 2;
    if ((rec = malloc(maxnum * sizeof(recType))) == 0)
    {
        fprintf (stderr, "insufficient memory (rec)\n");
        exit(1);
    }
    if ((key = malloc(maxnum * sizeof(keyType))) == 0)
    {
        fprintf (stderr, "insufficient memory (key)\n");
        exit(1);
    }
    if (random)
    {
        for (i = 0; i < maxnum; i++) key[i] = rand();
        printf ("ran bt, %d items\n", maxnum);
    }
   else
   {
        for (i=0; i<maxnum; i++) key[i] = i;
        printf ("seq bt, %d items\n", maxnum);
   }
    for (i = 0; i < maxnum; i++)
   {
        status = insert(key[i], &rec[i]);
        if (status) printf("pt1, i=%d: %d\n", i, status);
    }
    for (i = maxnum-1; i >= 0; i--)
   {
        status = find(key[i], &rec[i]);
        if (status) printf("pt2, i=%d: %d\n", i, status);
    }
    for (i = maxnum-1; i >= 0; i--)
    {
        status = delete(key[i]);
        if (status) printf("pt3, i=%d: %d\n", i, status);
    }
    return 0;
}

Posted in: Tree