An AVL tree implementation used for memoizing strings:

typedef enum {
	  INS_DROP = 1,
	  INS_SAME,
	  INS_DEEPEN
	  } AVLIS;

typedef struct memostr MEMOSTR;
typedef struct avlrv AVLRV;

struct avlrv {
  AVLIS stat;
  MEMOSTR *ms;
  } ;

struct memostr {
  MEMOSTR *l;
  MEMOSTR *r;
  MEMOSTR *u;
  int balance;
  unsigned int hash;
  char *str;
  int refs;
  } ;

static MEMOSTR *msroot;

#define HASHPOLY 0xedb88320

static int rebalance(MEMOSTR **up, MEMOSTR *uval)
{
 MEMOSTR *u;
 MEMOSTR *f;
 MEMOSTR *b;
 MEMOSTR *c;

 u = *up;
 if (u->u != uval) abort();
 switch (u->balance)
  { case 0:
       return(0);
       break;
    case 1: case -1:
       return(1);
       break;
    case -2:
       if (u->l->balance <= 0)
	{ u->balance = -1 - u->l->balance;
	  u->l->balance ++;
	  *up = u->l;
	  u->l->u = uval;
	  f = u->l->r;
	  u->l->r = u;
	  u->u = u->l;
	  u->l = f;
	  if (f) f->u = u;
	  if (u->balance) return(1);
	}
       else
	{ f = u->l->r;
	  b = f->l;
	  c = f->r;
	  *up = f;
	  f->u = uval;
	  f->l = u->l;
	  f->l->u = f;
	  f->r = u;
	  u->u = f;
	  f->l->r = b;
	  if (b) b->u = f->l;
	  u->l = c;
	  if (c) c->u = u;
	  f->l->balance = (f->balance > 0) ? -1 : 0;
	  f->r->balance = (f->balance < 0) ?  1 : 0;
	  f->balance = 0;
	}
       return(0);
       break;
    case 2:
       if (u->r->balance >= 0)
	{ u->balance = 1 - u->r->balance;
	  u->r->balance --;
	  *up = u->r;
	  u->r->u = uval;
	  f = u->r->l;
	  u->r->l = u;
	  u->u = u->r;
	  u->r = f;
	  if (f) f->u = u;
	  if (u->balance) return(1);
	}
       else
	{ f = u->r->l;
	  b = f->r;
	  c = f->l;
	  *up = f;
	  f->u = uval;
	  f->r = u->r;
	  f->r->u = f;
	  f->l = u;
	  u->u = f;
	  f->r->l = b;
	  if (b) b->u = f->r;
	  u->r = c;
	  if (c) c->u = u;
	  f->r->balance = (f->balance < 0) ?  1 : 0;
	  f->l->balance = (f->balance > 0) ? -1 : 0;
	  f->balance = 0;
	}
       return(0);
       break;
  }
 abort();
}

static AVLRV insert(unsigned int h, const char *s, MEMOSTR **up, MEMOSTR *uval)
{
 MEMOSTR *u;
 int cv;
 AVLRV v;

 u = *up;
 if (! u)
  { u = malloc(sizeof(MEMOSTR));
    u->l = 0;
    u->r = 0;
    u->u = uval;
    u->balance = 0;
    u->hash = h;
    u->str = strdup(s);
    u->refs = 1;
    *up = u;
    return((AVLRV){.stat=INS_DEEPEN,.ms=u});
  }
      if (h < u->hash) cv = -1;
 else if (h > u->hash) cv = 1;
 else                  cv = strcmp(s,u->str);
 if (cv < 0)
  { v = insert(h,s,&u->l,u);
    switch (v.stat)
     { default:
	  abort();
	  break;
       case INS_DROP:
       case INS_SAME:
	  break;
       case INS_DEEPEN:
	  u->balance --;
	  if (! rebalance(up,uval)) v.stat = INS_SAME;
	  break;
     }
  }
 else if (cv > 0)
  { v = insert(h,s,&u->r,u);
    switch (v.stat)
     { default:
	  abort();
	  break;
       case INS_DROP:
       case INS_SAME:
	  break;
       case INS_DEEPEN:
	  u->balance ++;
	  if (! rebalance(up,uval)) v.stat = INS_SAME;
	  break;
     }
  }
 else
  { u->refs ++;
    return((AVLRV){.stat=INS_DROP,.ms=u});
  }
 return(v);
}

static MEMOSTR *memoize(const char *s)
{
 unsigned int h;
 static unsigned int hv[256] = { 0, 0 };
 int i;
 int j;

 if (hv[1] == 0)
  { for (i=255;i>=0;i--)
     { h = i;
       for (j=8;j>0;j--) h = (h >> 1) ^ ((h & 1) ? HASHPOLY : 0);
       hv[i] = h;
     }
  }
 h = 0;
 for (i=0;s[i];i++) h = (h >> 8) ^ hv[0xff&(h^(unsigned char)s[i])];
 return(insert(h,s,&msroot,0).ms);
}