void Dict::insert(itemType v, infoType info)
  {
    x = head; p = head; g = head;
    while (x != z)
      {
        gg = g; g = p; p = x;
        x = (v < x->key) ? x->l :  x->r;
        if (x->l->b && x->r->b) split(v);
      }
    x = new node(v, info, 1, z, z);
    if (v < p->key) p->l = x; else p->r = x;
    split(v); head->r->b = black;
  }