AA tree by C

aatree.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include "aatree.h"

static aanode* new_aanode(const int key, void *val, aanode *nullnode) {
   aanode *n = (aanode*)malloc(sizeof(aanode));
   if(n == NULL) return NULL;
   n->key = key;
   n->val = val;
   n->lv  = 1;
   n->l = n->r = nullnode;
   return n;
}

aatree* new_aatree(void(*valfree_fun)(void*)) {
   aatree *t = (aatree*)malloc(sizeof(aatree));
   if(t == NULL) return NULL;
   aanode *nn = (aanode*)malloc(sizeof(aanode));
   if(nn == NULL) {
      free(t);
      return NULL;
   }
   nn->lv = 0;
   nn->l = nn->r = nn;
   t->root = t->nullnode = nn;
   t->deleted = NULL;
   t->num_entries = 0;
   t->valfree_fun = valfree_fun;
   return t;
}

unsigned aa_num_entries(const aatree *t) {
   return t->num_entries;
}

static void delete_aatree_(aatree *t, aanode *n) {
   assert(n);
   if(n == t->nullnode) return;
   if(n->l != t->nullnode) delete_aatree_(t, n->l);
   if(n->r != t->nullnode) delete_aatree_(t, n->r);
   if(n->val) (t->valfree_fun)(n->val);
   free(n);
}
void delete_aatree(aatree *t) {
   assert(t && t->root);
   delete_aatree_(t, t->root);
   free(t->nullnode);
   free(t);
}

static aanode* aa_skew(aanode *n) {
   assert(n && n->l);
   if(n->lv != n->l->lv) return n;
   aanode *left = n->l;
   n->l = left->r;
   left->r = n;
   n = left;
   return n;
}

static aanode* aa_split(aanode *n) {
   assert(n && n->r && n->r->r);
   if(n->r->r->lv != n->lv) return n;
   aanode *right = n->r;
   n->r = right->l;
   right->l = n;
   n = right;
   n->lv++;
   return n;
}

static aanode* aa_search_(const aanode *nn, aanode *n, const int key) {
   if(n == nn) return NULL;
   else if(n->key > key) return aa_search_(nn, n->l, key);
   else if(n->key < key) return aa_search_(nn, n->r, key);
   else return n;
}
void* aa_search(const aatree *t, const int key) {
   return aa_search_(t->nullnode, t->root, key)->val;
}

static aanode* aa_insert_(aatree *t, aanode *n, const int key, void *val) {
   if(n == t->nullnode) {
      n = new_aanode(key, val, t->nullnode);
      t->num_entries++;
      return n;
   }
   if(key < n->key) {
      n->l = aa_insert_(t, n->l, key, val);
   } else if(key > n->key) {
      n->r = aa_insert_(t, n->r, key, val);
   } else return n;
   n = aa_skew(n);
   n = aa_split(n);
   return n;
}
void aa_insert(aatree *t, const int key, void *val) {
   t->root = aa_insert_(t, t->root, key, val);
}

static aanode* aa_remove_(aatree *t, aanode *n, const int key) {
   if(n == t->nullnode) return n;
   t->last = n;
   if(key < n->key) {
      n->l = aa_remove_(t, n->l, key);
   } else {
      t->deleted = n;
      n->r = aa_remove_(t, n->r, key);
   }
   if(n == t->last && t->deleted != t->nullnode && key == t->deleted->key) {
      t->deleted->key = n->key;
      t->deleted = t->nullnode;
      n = n->r;
      free(t->last->val);
      free(t->last);
      t->num_entries--;
   } else if(n->l->lv < n->lv-1 || n->r->lv < n->lv-1) {
      n->lv--;
      if(n->r->lv > n->lv) n->r->lv = n->lv;
      n = aa_skew(n);
      n->r = aa_skew(n->r);
      n->r->r = aa_skew(n->r->r);
      n = aa_split(n);
      n->r = aa_split(n->r);
   }
   return n;
}
void aa_remove(aatree *t, const int key) {
   t->root = aa_remove_(t, t->root, key);
}

static void aa_foreach_(const aanode *nn, const aanode *n, AAForeach cb, void *arg) {
   if(n == nn) return;
   (*cb)(n, arg);
   aa_foreach_(nn, n->l, cb, arg);
   aa_foreach_(nn, n->r, cb, arg);
}
void aa_foreach(const aatree *t, AAForeach callback, void *arg) {
   aa_foreach_(t->nullnode, t->root, callback, arg);
}

static void aa_map_(const aanode *nn, aanode *n, AAMap cb) {
   if(n == nn) return;
   void *tmp = (*cb)(n);
   free(n->val);
   n->val = tmp;
   aa_map_(nn, n->l, cb);
   aa_map_(nn, n->r, cb);
}
void aa_map(const aatree *t, AAMap callback) {
   aa_map_(t->nullnode, t->root, callback);
}

static aanode* aa_first_(aanode *nn, aanode *n) {
   if(n == nn) return nn;
   else if(n->l == nn) return n;
   else return aa_first_(nn, n->l);
}
aanode* aa_first(const aatree *t) {
   return aa_first_(t->nullnode, t->root);
}

static aanode* aa_last_(aanode *nn, aanode *n) {
   if(n == nn) return nn;
   else if(n->r == nn) return n;
   else return aa_last_(nn, n->r);
}
aanode* aa_last(const aatree *t) {
   return aa_last_(t->nullnode, t->root);
}

aatree.h

#ifndef AA_TREE_H__
#define AA_TREE_H__ 1

typedef struct aanode_ {
   int key;
   void *val;
   int lv;
   struct aanode_*l, *r;
} aanode;

typedef struct {
   aanode *root;
   aanode *nullnode;
   aanode *deleted;
   aanode *last;
   void(*valfree_fun)(void*);
   unsigned int num_entries;
} aatree;

// new empty AA tree
aatree* new_aatree(void(*valfree_fun)(void*));
// delete the AA tree(release all resources)
void  delete_aatree(aatree *t);

// the number of elements
unsigned aa_num_entries(const aatree *t);
// search an item in the tree by the key, and return the value
void* aa_search(const aatree *t, const int key);
// insert an item by key-value into the tree
void  aa_insert(aatree *t, const int key, void *val);
// remove an item from the tree by the key
void  aa_remove(aatree *t, const int key);
// a node of smallest key in the tree
aanode* aa_first(const aatree *t);
// a node of biggest key in the tree
aanode* aa_last(const aatree *t);

// foreach statement
typedef void (*AAForeach)(const aanode *, void *args);
void aa_foreach(const aatree *t, AAForeach callback, void *arg);
// map statement(previous data is released automatically)
typedef void*(*AAMap)(const aanode *);
void aa_map(const aatree *t, AAMap callback);

#endif

test.c

#include <stdio.h>
#include "aatree.h"

void do_nothing(void *val) {
}

void print(const aanode *n, void *arg) {
   printf("key %d\n", n->key);
}

int main(void) {
   aatree *t = new_aatree(do_nothing);
   for(int i = 0; i < 10; ++i) {
      aa_insert(t, i, NULL);
   }
   aa_foreach(t, print, NULL);
   printf("%d\n", aa_num_entries(t));
   delete_aatree(t);
   return 0;
}

For newbies, to run the program.

1. " Download ZIP " of this program. ( You will get 3 files )
2. Download Code Blocks.
3. In Code Blocks Create New Project. ( FIle -> New -> Projects -> Empty Project->(Create Project in a separate folder ).
4. Right click the Project created. (its on the "side bar -> work-space") ( If sidebar not available goto "View -> Manager (check) " )
5. Add Files. ( All three files ) ( .h file will automaticaly go inside "Headers" Folder. )
6. Open "test.c" from sidebar.
7. Build -> Build & Run.

Output Screenshot Attached.