@Override
  protected void fixAfterInsertion(N x)
  {
    x.setColour(RED);
    while (x != null && x != getRoot() && x.getParent().getColour() == RED)
    {
      if (parentOf(x) == leftOf(parentOf(parentOf(x))))
      {
        N y = rightOf(parentOf(parentOf(x)));
        if (colorOf(y) == RED)
        {
          setColor(parentOf(x), BLACK);
          setColor(y, BLACK);
          setColor(parentOf(parentOf(x)), RED);
          x = parentOf(parentOf(x));
        }
        else
        {
          if (x == rightOf(parentOf(x)))
          {
            x = parentOf(x);
            rotateLeft(x);
          }
          setColor(parentOf(x), BLACK);
          setColor(parentOf(parentOf(x)), RED);
          rotateRight(parentOf(parentOf(x)));
        }
      }
      else
      {
        N y = leftOf(parentOf(parentOf(x)));
        if (colorOf(y) == RED)
        {
          setColor(parentOf(x), BLACK);
          setColor(y, BLACK);
          setColor(parentOf(parentOf(x)), RED);
          x = parentOf(parentOf(x));
        }
        else
        {
          if (x == leftOf(parentOf(x)))
          {
            x = parentOf(x);
            rotateRight(x);
          }
          setColor(parentOf(x), BLACK);
          setColor(parentOf(parentOf(x)), RED);
          rotateLeft(parentOf(parentOf(x)));
        }
      }
    }
    getRoot().setColour(BLACK);
  }