private void remedyDoubleBlack(Position<Entry<K,V>> p) {
    Position<Entry<K,V>> z = parent(p);
    Position<Entry<K,V>> y = sibling(p);
    if (isBlack(y)) {
      if (isRed(left(y)) || isRed(right(y))) { // Case 1: trinode restructuring
        Position<Entry<K,V>> x = (isRed(left(y)) ? left(y) : right(y));
        Position<Entry<K,V>> middle = restructure(x);
        setColor(middle, isRed(z)); // root of restructured subtree gets z's old color
        makeBlack(left(middle));
        makeBlack(right(middle));
      } else {                           // Case 2: recoloring
        makeRed(y);
        if (isRed(z))
          makeBlack(z);                  // problem is resolved
        else if (!isRoot(z))
          remedyDoubleBlack(z);          // propagate the problem
      }
    } else {                             // Case 3: reorient 3-node
      rotate(y);
      makeBlack(y);
      makeRed(z);
      remedyDoubleBlack(p);              // restart the process at p
    }
  }