This file contains (part of) the code from "Algorithms in C, Third Edition,
Parts 1-4," by Robert Sedgewick, and is covered under the copyright
and warranty notices in that book. Permission is granted for this
code to be used for educational purposes in association with the text,
and for other uses not covered by copyright laws, provided that
the following notice is included with the code:

 	"This code is from "Algorithms in C, Third Edition,"
	by Robert Sedgewick, Addison Wesley Longman, 1998."

Commercial uses of this code require the explicit written
permission of the publisher. Send your request for permission,
stating clearly what code you would like to use, and in what
specific way, to: aw.cse@aw.com

CHAPTER 13. Balanced Trees
-----
link balanceR(link h)
  { 
    if (h->N < 2) return h;
    h = partR(h, h->N/2);
    h->l = balanceR(h->l); 
    h->r = balanceR(h->r);
    return h;
  }
-----
link insertR(link h, Item item)
  { Key v = key(item), t = key(h->item);
    if (h == z) return NEW(item, z, z, 1);
    if (rand()< RAND_MAX/(h->N+1)) 
      return insertT(h, item);
    if less(v, t) h->l = insertR(h->l, item);
             else h->r = insertR(h->r, item);
    (h->N)++; return h;
  }
void STinsert(Item item)
  { head = insertR(head, item); }
-----
link STjoinR(link a, link b)
  { 
    if (a == z) return b;
    b = STinsert(b, a->rec); 
    b->l = STjoin(a->l, b->l); 
    b->r = STjoin(a->r, b->r); 
    fixN(b); free(a);
    return b;
  }
link STjoin(link a, link b)
  { 
    if (rand()/(RAND_MAX/(a->N+b->N)+1) < a->N)
         STjoinR(a, b);
    else STjoinR(b, a);
  }
-----
link joinLR(link a, link b)
  { 
    if (a == z) return b;
    if (b == z) return a;
    if (rand()/(RAND_MAX/(a->N+b->N)+1) < a->N)
         { a->r = joinLR(a->r, b); return a; }
    else { b->l = joinLR(a, b->l); return b; }
  }
-----
link splay(link h, Item item)
  { Key v = key(item);
    if (h == z) return NEW(item, z, z, 1);  
    if (less(v, key(h->item))) 
      { 
        if (hl == z) return NEW(item, z, h, h->N+1);
        if (less(v, key(hl->item))) 
          { hll = splay(hll, item); h = rotR(h); }
        else 
          { hlr = splay(hlr, item); hl = rotL(hl); }
        return rotR(h); 
      }
    else
      { 
        if (hr == z) return NEW(item, h, z, h->N+1);
        if (less(key(hr->item), v)) 
          { hrr = splay(hrr, item); h = rotL(h); }
        else 
          { hrl = splay(hrl, item); hr = rotR(hr); }
        return rotL(h);
      }
  }
void STinsert(Item item)
  { head = splay(head, item); }
-----
link RBinsert(link h, Item item, int sw)
  { Key v = key(item);
    if (h == z) return NEW(item, z, z, 1, 1);  
    if ((hl->red) && (hr->red)) 
      { h->red = 1; hl->red = 0; hr->red = 0; }
    if (less(v, key(h->item))) 
      { 
        hl = RBinsert(hl, item, 0); 
        if (h->red && hl->red && sw) h = rotR(h); 
        if (hl->red && hll->red) 
          { h = rotR(h); h->red = 0; hr->red = 1; }
      }
    else
      { 
        hr = RBinsert(hr, item, 1); 
        if (h->red && hr->red && !sw) h = rotL(h); 
        if (hr->red && hrr->red) 
          { h = rotL(h); h->red = 0; hl->red = 1; }
      }
    fixN(h); return h;
  }
void STinsert(Item item)
  { head = RBinsert(head, item, 0); head->red = 0; }
-----
Item searchR(link t, Key v, int k)
  { 
    if (eq(v, key(t->item))) return t->item;
    if (less(v, key(t->next[k]->item))) 
      { 
        if (k == 0) return NULLitem;
        return searchR(t, v, k-1); 
      }
    return searchR(t->next[k], v, k);
  }
Item STsearch(Key v)
  { return searchR(head, v, lgN); }
-----
typedef struct STnode* link;
struct STnode { Item item; link* next; int sz; };
static link head, z;
static int N, lgN;
link NEW(Item item, int k)      
  { int i; link x = malloc(sizeof *x);
    x->next = malloc(k*sizeof(link));
    x->item = item; x->sz = k;
    for (i = 0; i < k; i++) x->next[i] = z;
    return x;                         
  }                                   
void STinit(int max) 
  { 
    N = 0; lgN = 0; 
    z = NEW(NULLitem, 0); 
    head = NEW(NULLitem, lgNmax); 
  }
-----
int randX()
  { int i, j, t = rand();
    for (i = 1, j = 2; i < lgNmax; i++, j += j)
      if (t > RAND_MAX/j) break;
    if (i > lgN) lgN = i;
    return i;
  }
void insertR(link t, link x, int k)
  { Key v = key(x->item); 
    if (less(v, key(t->next[k]->item))) 
      { 
        if (k < x->sz)
          { x->next[k] = t->next[k]; 
            t->next[k] = x; }
        if (k == 0) return;
        insertR(t, x, k-1); return;
      }
    insertR(t->next[k], x, k);
  }
void STinsert(Key v)
  { insertR(head, NEW(v, randX()), lgN); N++; }
-----
void deleteR(link t, Key v, int k)
  { link x = t->next[k];
    if (!less(key(x->item), v)) 
      { 
        if (eq(v, key(x->item)))
          { t->next[k] = x->next[k]; }
        if (k == 0) { free(x); return; }
        deleteR(t, v, k-1); return;
      }
    deleteR(t->next[k], v, k);
  }
void STdelete(Key v)
  { deleteR(head, v, lgN); N--; }

----------