Treap implementation in C

Question

I was needed a SET-like data structure written in pure C for some university class, so I've implemented a simple one - the Treap (or cartesian tree).

Please check if everything is okay (actually, I'm not sure that there isn't a memory leak there).

cartesian_tree.h

#ifndef _CARTESIAN_TREE_H_
#define _CARTESIAN_TREE_H_

#define  NODE  struct Node
#define pNODE  struct Node*
#define ppNODE struct Node**

/* Each node of the tree has the following structure: */
struct Node {
  long key, priority;   /* priority is a kind of `technical' information */
  char* assoc;          /* pointer to a user's data (imagine MAP) */
  NODE *left, *right;   /* links to the left and right child */
};

/* Returns a pointer to the tree consisting only from the root */
pNODE construct_tree(void);

/* Inserts new element to the tree. 
   Returns 0 if there was no such element in tree and -1 otherwise
   (in such case, nothing is inserted) */
char insert(pNODE, long, char*);

/* Erases a node with a particular key.
   returns 0 if an element with key `key' was deleted 
   and -1 otherwise. */
char erase(pNODE, long);

/* Returns a pointer to node with the particular key
   or NULL if there is no such node. */
pNODE find(pNODE, long);

/* Clean up. One should call this function every time 
   when the tree isn't needed no more. */
void destruct_tree(pNODE);


#endif

cartesian_tree.c

#include <time.h>
#include <stdlib.h>
#include <limits.h>

#include "cartesian_tree.h"


pNODE construct_tree(void) {
  srand(time(0));   /* treap is a randomized data structure, remember? */

  pNODE root = (pNODE)malloc(sizeof(NODE));
  root->key = root->priority = LONG_MIN;
  root->assoc = NULL;
  root->left = root->right = NULL;

  return root;
}


char insert(pNODE root, long key, char* assoc) {
  /* nope, Mr. Duplicate, we don't wanna see you at our party */
  if(find(root, key))
    return -1;

  /* constructing a new node */
  pNODE fresh_node = (pNODE)malloc(sizeof(NODE));
  fresh_node->key = key;
  fresh_node->priority = ((rand() << 15) | rand());
  fresh_node->assoc = assoc;

  /* searching for the proper place for new node */
  ppNODE T = &(root->right);
  while(1) {
    /* if we're at the bottom */
    if(!*T) {
      *T = fresh_node;
      return 0;
    }

    if((*T)->priority > fresh_node->priority)
      break;

    /* choosing the right direction */
    T = (fresh_node->key < (*T)->key) ? &((*T)->left) : &((*T)->right);
  }

  /* placing new node to its place */
  pNODE to_split = *T;
  *T = fresh_node;

  /* splitting a treap into two smaller treaps, 
     those smaller than `key', and those larger than `key' */
  ppNODE left_subt = &((*T)->left);
  ppNODE right_subt = &((*T)->right);

  while(to_split) {
    if(to_split->key < key) {
      *left_subt = to_split;
      left_subt = &((*left_subt)->right);
      to_split = to_split->right;
    } else {
      *right_subt = to_split;
      right_subt = &((*right_subt)->left);
      to_split = to_split->left;
    }
  }

  return 0;
}


char erase(pNODE root, long key) {
  /* searching for the node */
  pNODE pos = root;
  ppNODE pred_link;
  while(pos) {
    if(pos->left)
      if(pos->left->key == key) {
        pred_link = &(pos->left);
        pos = pos->left;
        break;
      }

    if(pos->right)
      if(pos->right->key == key) {
    pred_link = &(pos->right);
    pos = pos->right;
    break;
      }

    pos = (key < pos->key) ? pos->left : pos->right;
  }

  /* if there is no node with such key */
  if(!pos)
    return -1;

  pNODE to_free = pos;

  /* performing a `merge' operation */
  pNODE left_subt = pos->left;
  pNODE right_subt = pos->right;

  while(1) {
    if(!left_subt || !right_subt) {
      *pred_link = left_subt ? left_subt : right_subt;
      break;
    }

    if(left_subt->priority < right_subt->priority) {
      *pred_link = left_subt;
      pred_link = &(left_subt->right);
      left_subt = left_subt->right;
    } else {
      *pred_link = right_subt;
      pred_link = &(right_subt->left);
      right_subt = right_subt->left;
    }
  }

  /* sorry friend, we don't need you anymore */
  free(to_free);

  return 0;
}


pNODE find(pNODE root, long key) {
  pNODE T = root;

  /* lookup like in ordinary BST */
  while(T) {
    if(key == T->key)
      return T;

    T = (key < T->key) ? T->left : T->right;
  }
  return NULL;
}


void destruct_tree(pNODE T) {
  /* recursive depth-first traversal */

  if(!T)
    return;

  if(T->left)
    destruct_tree(T->left);

  if(T->right)
    destruct_tree(T->right);

  free(T);
}

example.c (one can simply test all the above code)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "cartesian_tree.h"

int main(void) {
  char buf[10];
  pNODE T = construct_tree();
  long key;

  printf("Usage:\nadd <key>\nremove <key>\nlookup <key>\n\n");

  while(1) {
    /* dealing with user */
    scanf("%s %ld", buf, &key);

    if(!strcmp(buf, "add")) {
      if(!insert(T, key, NULL))
    puts("Inserted, OK.");
      else
    puts("Ooops, a duplicate detected.");
    }
    else if(!strcmp(buf, "remove")) {
      if(!erase(T, key))
    puts("Found and erased, OK.");
      else
    puts("No such element.");
    }
    else if(!strcmp(buf, "lookup")) {
      if(find(T, key))
    puts("Yup, found.");
      else
    puts("Not found.");
    } else {
      destruct_tree(T);
      puts("Bye!");
      exit(0);
    }
  }
}

Answer 1

• It's preferred to only call srand() once in main(). It's easier to maintain in this way as it'll avoid the possibility of calling srand() multiple times, which will give you the same random value with rand() each time. It should only be called once.

• You don't need to call exit() in main() since it is supposed to return an integer value related to the program's execution outcome. Just return 0 or 1.

• The indentation in main()'s while(1) loop is a bit inconsistent. Statements under an if or else should still be indented.

  I would also refactor the loop to use fewer conditional statements. It's not only difficult to follow the flow, especially with few comments, but you could also experience a reduction in performance due to branch prediction (this may not be a problem, especially with modern architecture, but it's still something worth keeping in mind).

Answer 2

Design problems:

Consider what the client may want to do if insert fails? Very likely, he'd want to inspect the data associated with the existing key, and decide if it shall stay or be replaced. In the current design, the client is forced to call find. I'd recommend to return the existing node (you know it already, so there's no additional cost incurred) along with the boolean insertion happens flag, STL style. Same way, erase shall return the pointer to an associated data: it is very well possible it was dynamically allocated, so client shall have a way to free it - again, without a redundant call to find.

Answer 3

I would move the exit call out of the loop. End the loop with a break, flag variable, or even a goto if you like and then exit the function. This also gives you a place to handle failure conditions cleanly.

In many fonts !, l, and 1 look a lot alike. I would prefer to see

if (! foo)

With strcmp I also prefer to use == 0 for the check because it lets me extend in the future. But this is definitely more personal preference.

On modern systems long is the same as int. I can see why in a class you may need to use long but in real world coding you would likely use an int unless you need to be explicit about the size and then you would use something like int16_t or int64_t.

I would consider a mkNode() function which allocated the node and set the fields to something sensible. This would get rid of some boiler plate code.

Answer 4

In addition to the comments already given, I would give one more: I'm not a fan of the pNODE and ppNODE macros. The reason is that with the macro, pNODE a, b; declares one pointer to a node, and one node -- it's too error-prone.

If you want to use a single identifier for these types, I'd prefer a typedef. The definition of the struct and the typedef together could look something like this:

typedef struct node_ {
    ...;
    struct node_ *left, *right;
} node;

typedef node *pnode;
typedef pnode *ppnode;

Now pnode a, b; defines two pointers to nodes.

I think there is also value in just keeping the levels of pointer indirection completely explicit, so omitting the pnode and ppnode types and just using node * and node **; but that's more a matter of personal taste.

Answer 5

Bugs:

• The root node always has key=LONG_MIN. What happens if someone tries to use that as a key?
• scanf("%s") is not safe. If the user types more than 9 characters, it will overflow the buffer and probably crash. Use fgets(buf, sizeof(buf), stdin) instead. (There's almost never a good reason to use scanf.)

Refactoring:

• find, insert, and erase have very similar lookup loops. These could be factored out as a function which finds the link under which a node either will be inserted.
• The sections about splitting and merging could be extracted as separate functions.
• The section that constructs a new node could also be a separate function.
• The if(T->left) checks in destruct_tree are unnecessary. Since it's safe on NULL (as it should be), you can just blindly recurse on both children.

Style:

• As Erik said, the pNODE macros are error-prone; use typedef instead. Or, better, do without them — Node *x is clearer than pNODE x.

• The conventional way to do the NODE typedef is to wrap it around the struct definition:

  typedef struct Node {
    //...
    struct Node *left, *right;
  } Node;
  

• destruct_tree would usually be called something like free_tree or delete_tree.

• Using a special Node as the root is confusing, because it doesn't act like a normal node. (And this causes the first bug above.) There should be comments about this, or the root should be a separate type: typedef struct { Node *root; } Treap;