/** Creates a new tree node. */
  protected BTPosition createNode(Object element, BTPosition parent,
				  BTPosition left, BTPosition right) {
    return new RBNode(element,parent,left,right); // a red-black node
  }
  public Entry insert(Object k, Object x) throws InvalidKeyException  {
    Entry toReturn = super.insert(k, x); 
    Position posZ = actionPos; // start at the insertion position
    setRed(posZ);
    if (isRoot(posZ))
      setBlack(posZ);
    else
      remedyDoubleRed(posZ); // fix a double-red color violation 
    return toReturn;
  }
  protected void remedyDoubleRed(Position posZ)  {
    Position posV = parent(posZ);
    if (isRoot(posV))
      return;
    if (!isPosRed(posV))
      return;
    // we have a double red: posZ and posV
    if (!isPosRed(sibling(posV)))  { // Case 1: trinode restructuring
      posV = restructure(posZ);
      setBlack(posV);
      setRed(left(posV));
      setRed(right(posV));
    }  
    else  { // Case 2: recoloring
      setBlack(posV);
      setBlack(sibling(posV));
      Position posU = parent(posV);
      if (isRoot(posU))
        return;
      setRed(posU);
      remedyDoubleRed(posU);
    }
  }