@Override
  protected @NotNull IntervalNode<T> swapWithMaxPred(@NotNull Node<T> root, @NotNull Node<T> maxPred) {
    checkMax(false);
    IntervalNode<T> a = (IntervalNode<T>)root;
    IntervalNode<T> d = (IntervalNode<T>)maxPred;
    boolean aColor = a.isBlack();
    boolean dColor = d.isBlack();
    assert !a.isValid() || a.delta == 0 : a.delta;
    for (IntervalNode<T> n = a.getLeft(); n != null; n = n.getRight()) {
      assert !n.isValid() || n.delta == 0 : n.delta;
    }
    swapNodes(a, d);

    // set range of the key to be deleted, so it won't disrupt maxes
    a.setValid(false);
    a.setColor(dColor);
    d.setColor(aColor);
    correctMaxUp(a);

    checkMax(false);
    assert a.delta == 0 : a.delta;
    assert d.delta == 0 : d.delta;
    return a;
  }
@Override
  protected @NotNull IntervalNode<T> swapWithMaxPred(@NotNull Node<T> root, @NotNull Node<T> maxPred)