if (t < k) return selectR(h->r, k-t-1);      return h->item;    }public:  Item select(int k)    { return selectR(head, k); } -----void partR(link& h, int k)  { int t = (h->l == 0) ? 0: h->l->N;    if (t > k )      { partR(h->l, k); rotR(h); }    if (t < k )      { partR(h->r, k-t-1); rotL(h); }  } -----private:  link joinLR(link a, link b)    {       if (b == 0) return a;      partR(b, 0); b->l = a;       return b;    }  void removeR(link& h, Key v)    { if (h == 0) return;      Key w = h->item.key();       if (v < w) removeR(h->l, v);      if (w < v) removeR(h->r, v);      if (v == w)         { link t = h;           h = joinLR(h->l, h->r); delete t; }    }public:  void remove(Item x)    { removeR(head, x.key()); }-----    private:      link joinR(link a, link b)        {           if (b == 0) return a;          if (a == 0) return b;          insertT(b, a->item);           b->l = joinR(a->l, b->l);           b->r = joinR(a->r, b->r);           delete a; return b;        }    public:      void join(ST<Item, Key>& b)        { head = joinR(head, b.head); }----------CHAPTER 13. Balanced Trees-----void balanceR(link& h)  {    if ((h == 0) || (h->N == 1)) return;    partR(h, h->N/2);    balanceR(h->l);    balanceR(h->r);  }-----private:  void insertR(link& h, Item x)    { if (h == 0) { h = new node(x); return; }      if (rand() < RAND_MAX/(h->N+1))        { insertT(h, x); return; }      if (x.key() < h->item.key())            insertR(h->l, x);      else insertR(h->r, x);      h->N++;     }public:  void insert(Item x)    { insertR(head, x); }-----private:  link joinR(link a, link b)    {       if (a == 0) return b;      if (b == 0) return a;      insertR(b, a->item);       b->l = joinR(a->l, b->l);       b->r = joinR(a->r, b->r);       delete a; fixN(b); return b;    }public:  void join(ST<Item, Key>& b)    { int N = head->N;      if (rand()/(RAND_MAX/(N+b.head->N)+1) < N)           head = joinR(head, b.head);      else head = joinR(b.head, head); }-----link joinLR(link a, link b)  {     if (a == 0) return b;    if (b == 0) 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; }  }-----private:  void splay(link& h, Item x)    {       if (h == 0)         { h = new node(x, 0, 0, 1); return; }      if (x.key() < h->item.key())        { link& hl = h->l; int N = h->N;          if (hl == 0)             { h = new node(x, 0, h, N+1); return; }          if (x.key() <  hl->item.key())                { splay(hl->l, x); rotR(h); }          else { splay(hl->r, x); rotL(hl); }          rotR(h);        }      else        { link &hr = h->r; int N = h->N;          if (hr == 0)             { h = new node(x, h, 0, N+1); return; }          if (hr->item.key() < x.key())                { splay(hr->r, x); rotL(h); }          else { splay(hr->l, x); rotR(hr); }          rotL(h);        }    }public:  void insert(Item item)    { splay(head, item); }-----private:  int red(link x)     { if (x == 0) return 0; return x->red; }  void RBinsert(link& h, Item x, int sw)    {       if (h == 0) { h = new node(x); return; }      if (red(h->l) && red(h->r))       { h->red = 1; h->l->red = 0; h->r->red = 0; }      if (x.key() < h->item.key())        {          RBinsert(h->l, x, 0);           if (red(h) && red(h->l) && sw) rotR(h);           if (red(h->l) && red(h->l->l))             { rotR(h); h->red = 0; h->r->red = 1; }        }      else        {           RBinsert(h->r, x, 1);           if (red(h) && red(h->r) && !sw) rotL(h);           if (red(h->r) && red(h->r->r))             { rotL(h); h->red = 0; h->l->red = 1; }        }    }public:  void insert(Item x)    { RBinsert(head, x, 0); head->red = 0; }-----private:  Item searchR(link t, Key v, int k)    { if (t == 0) return nullItem;      if (v == t->item.key()) return t->item;      link x = t->next[k];      if ((x == 0) || (v < x->item.key()))         {           if (k == 0) return nullItem;          return searchR(t, v, k-1);         }      return searchR(x, v, k);    }public:  Item search(Key v)    { return searchR(head, v, lgN); }-----private:  struct node     { Item item; node **next; int sz;       node(Item x, int k)        { item = x; sz = k; next = new node*[k];           for (int i = 0; i < k; i++) next[i] = 0; }     };   typedef node *link;  link head;  Item nullItem;  int lgN;public:  ST(int)    { head = new node(nullItem, lgNmax); lgN = 0; }-----private:  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 = x->item.key(); link tk = t->next[k];      if ((tk == 0) || (v < tk->item.key()))         {           if (k < x->sz)            { x->next[k] = tk; t->next[k] = x; }          if (k == 0) return;          insertR(t, x, k-1); return;        }      insertR(tk, x, k);    }public:  void insert(Item v)    { insertR(head, new node(v, randX()), lgN); }-----private:  void removeR(link t, Key v, int k)    { link x = t->next[k];      if (!(x->item.key() < v))         {           if (v == x->item.key())            { t->next[k] = x->next[k]; }          if (k == 0) { delete x; return; }          removeR(t, v, k-1); return;        }      removeR(t->next[k], v, k);    }public:  void remove(Item x)    { removeR(head, x.key(), lgN); }----------CHAPTER 14. Hashing-----int hash(char *v, int M)  { int h = 0, a = 127;    for (; *v != 0; v++)       h = (a*h + *v) % M;    return h;  }-----int hashU(char *v, int M)  { int h, a = 31415, b = 27183;    for (h = 0; *v != 0; v++, a = a*b % (M-1))         h = (a*h + *v) % M;    return (h < 0) ? (h + M) : h;  }-----private:  link* heads;  int N, M;public:  ST(int maxN)    {       N = 0; M = maxN/5;      heads = new link[M];       for (int i = 0; i < M; i++) heads[i] = 0;    }  Item search(Key v)    { return searchR(heads[hash(v, M)], v); }  void insert(Item item)    { int i = hash(item.key(), M);      heads[i] = new node(item, heads[i]); N++; }-----private:  Item *st;   int N, M;  Item nullItem;public:  ST(int maxN)    {       N = 0; M = 2*maxN;      st = new Item[M];       for (int i = 0; i < M; i++) st[i] = nullItem;    }  int count() const { return N; }  void insert(Item item)    { int i = hash(item.key(), M);      while (!st[i].null()) i = (i+1) % M;      st[i] = item; N++;    }  Item search(Key v)    { int i = hash(v, M);      while (!st[i].null())      if (v == st[i].key()) return st[i];        else i = (i+1) % M;      return nullItem;    }-----void remove(Item x)  { int i = hash(x.key(), M), j;    while (!st[i].null())      if (x.key() == st[i].key()) break;         else i = (i+1) % M;    if (st[i].null()) return;    st[i] = nullItem; N--;    for (j = i+1; !st[j].null(); j = (j+1) % M, N--)    { Item v = st[j]; st[j] = nullItem; insert(v); }  }-----void insert(Item item)  { Key v = item.key();    int i = hash(v, M), k = hashtwo(v, M);    while (!st[i].null()) i = (i+k) % M;    st[i] = item; N++;  }Item search(Key v)  { int i = hash(v, M), k = hashtwo(v, M);    while (!st[i].null())    if (v == st[i].key()) return st[i];      else i = (i+k) % M;    return nullItem;  }-----private:  void expand()    { Item *t = st;      init(M+M);      for (int i = 0; i < M/2; i++)        if (!t[i].null()) insert(t[i]);      delete t;    }public:  ST(int maxN)    { init(4); }  void insert(Item item)    { int i = hash(item.key(), M);      while (!st[i].null()) i = (i+1) % M;      st[i] = item;       if (N++ >= M/2) expand();    }----------CHAPTER 15. Radix Search-----private:  Item searchR(link h, Key v, int d)    { if (h == 0) return nullItem;      if (v ==  h->item.key()) return h->item;      if (digit(v, d) == 0)           return searchR(h->l, v, d+1);      else return searchR(h->r, v, d+1);    }public:  Item search(Key v)     { return searchR(head, v, 0); } -----private:  Item searchR(link h, Key v, int d)    { if (h == 0) return nullItem;      if (h->l == 0 && h->r == 0)        { Key w = h->item.key();          return (v == w) ? h->item : nullItem; }      if (digit(v, d) == 0)           return searchR(h->l, v, d+1);      else return searchR(h->r, v, d+1);    }public:  Item search(Key v)     { return searchR(head, v, 0); } -----private:  link split(link p, link q, int d)    { link t = new node(nullItem); t->N = 2;      Key v = p->item.key(); Key w = q->item.key();      switch(digit(v, d)*2 + digit(w, d))        { case 0: t->l = split(p, q, d+1); break;          case 1: t->l = p; t->r = q; break;          case 2: t->r = p; t->l = q; break;          case 3: t->r = split(p, q, d+1); break;        }      return t;    }  void insertR(link& h, Item x, int d)    { if (h == 0) { h = new node(x); return; }      if (h->l == 0 && h->r == 0)        { h = split(new node(x), h, d); return; }      if (digit(x.key(), d) == 0)            insertR(h->l, x, d+1);      else insertR(h->r, x, d+1);    }public:  ST(int maxN)    { head = 0; }  void insert(Item item)    { insertR(head, item, 0); }-----private:  Item searchR(link h, Key v, int d)    {       if (h->bit <= d) return h->item;      if (digit(v, h->bit) == 0)           return searchR(h->l, v, h->bit);      else return searchR(h->r, v, h->bit);    }public:  Item search(Key v)     { Item t = searchR(head, v, -1);       return (v == t.key()) ? t : nullItem;    } -----private:  link insertR(link h, Item x, int d, link p)    { Key v = x.key();      if ((h->bit >= d) || (h->bit <= p->bit))        {           link t = new node(x); t->bit = d;          t->l = (digit(v, t->bit) ? h : t);          t->r = (digit(v, t->bit) ? t : h);          return t;         }      if (digit(v, h->bit) == 0)           h->l = insertR(h->l, x, d, h);      else h->r = insertR(h->r, x, d, h);      return h;    }public:  void insert(Item x)    { Key v = x.key(); int i;      Key w = searchR(head->l, v, -1).key();      if (v == w) return;      for (i = 0; digit(v, i) == digit(w, i); i++) ;      head->l = insertR(head->l, x, i, head);    }  ST(int maxN)    { head = new node(nullItem);       head->l = head->r = head; }-----private:  void showR(link h, ostream& os, int d)    {       if (h->bit <= d) { h->item.show(os); return; }      showR(h->l, os, h->bit);      showR(h->r, os, h->bit);    }public:  void show(ostream& os)    { showR(head->l, os, -1); } -----private:  struct node     { node **next;      node()        { next = new node*[R];          for (int i = 0; i < R; i++) next[i] = 0; }     };   typedef node *link;  link head;  Item searchR(link h, Key v, int d)    { int i = digit(v, d);       if (h == 0) return nullItem;      if (i == NULLdigit)         { Item dummy(v); return dummy; }      return searchR(h->next[i], v, d+1);    }  void insertR(link& h, Item x, int d)    { int i = digit(x.key(), d);      if (h == 0) h = new node;      if (i == NULLdigit) return;      insertR(h->next[i], x, d+1);    }public:  ST(int maxN)    { head = 0; }  Item search(Key v)     { return searchR(head, v, 0); }   void insert(Item x)    { insertR(head, x, 0); }-----private:  struct node     { Item item; int d; node *l, *m, *r;      node(int k)        { d = k; l = 0; m = 0; r = 0; }     };   typedef node *link;  link head;  Item nullItem;   Item searchR(link h, Key v, int d)    { int i = digit(v, d);       if (h == 0) return nullItem;      if (i == NULLdigit)         { Item dummy(v); return dummy; }      if (i < h->d) return searchR(h->l, v, d);      if (i == h->d) return searchR(h->m, v, d+1);      if (i > h->d) return searchR(h->r, v, d);    }  void insertR(link& h, Item x, int d)    { int i = digit(x.key(), d);      if (h == 0) h = new node(i);      if (i == NULLdigit) return;      if (i < h->d) insertR(h->l, x, d);      if (i == h->d) insertR(h->m, x, d+1);      if (i > h->d) insertR(h->r, x, d);    }public:  ST(int maxN)    { head = 0; }  Item search(Key v)     { return searchR(head, v, 0); }   void insert(Item x)    { insertR(head, x, 0); }-----private:  char word[maxW];  void matchR(link h, char *v, int i)    {       if (h == 0) return;      if ((*v == 0) && (h->d == 0))        { word[i] = 0; cout << word << " "; }      if ((*v == '*') || (*v == h->d))        { word[i] = h->d; matchR(h->m, v+1, i+1); }      if ((*v == '*') || (*v < h->d))        matchR(h->l, v, i);      if ((*v == '*') || (*v > h->d))        matchR(h->r, v, i);    }public:  void match(char *v)     { matchR(head, v, 0); }-----  struct node     { Item item; int d; node *l, *m, *r;       node(Item x, int k)        { item = x; d = k; l = 0; m = 0; r = 0; }       node(node* h, int k)        { d = k; l = 0; m = h; r = 0; }       int internal()         { return d != NULLdigit; }     };   typedef node *link;  link heads[R];  Item nullItem;-----private:  link split(link p, link q, int d)    { int pd = digit(p->item.key(), d),           qd = digit(q->item.key(), d);      link t = new node(nullItem, q