Если я правильно понимаю вопрос, вы спрашиваете, как определить абсолютное максимальное или минимальное значение для любого данного типа, чтобы вы могли указать диапазон, который будет принимать любое значение как действительное.
К сожалению, в общем случае произвольный T не обязательно имеет инстанцируемый минимум и максимум. На самом деле int и Integer делают только потому, что из-за ограничения представления они не могут быть сколь угодно большими или маленькими.
Например, для String можно утверждать, что тогда пустая строка ("") является минимумом, безусловно, меньше или равна любой другой String, использующей ее естественный порядок, но какой будет максимальная строка. Вероятно, это будет бесконечно длинное повторение максимального символа Юникода, поэтому вы не можете создать такой объект.
Однако это не должно помешать вам определить диапазоны, которые включают любое значение или они открыты на одном конце (т. Е. У них есть минимум, но не максимум или наоборот).
Например, если диапазон должен быть указан как два аргумента в сигнатуре метода, который будет использовать такой диапазон, тогда вы можете просто указать null, чтобы указать, что min или max не существует, то есть этот конец диапазона открыт.
Мне кажется, что это будет хорошо работать с вашим valideteBST, поскольку он уже имеет эти два параметра.
class BST<T extends Comparable<T>> {
// ...
public boolean checkBST(Node<T> root) {
return validateBST(root, null, null);
}
// ...
boolean validateBST(Node<T> node, T min, T max) {
if (node == null) {
// nothing to do here.
return true;
}
final T value = node.getValue();
if (min != null && min.compareTo(value) >= 0) {
return false;
} else if (max != null && max.compareTo(value) <= 0) {
return false;
} else {
return validateBST(node.getLeft(), min, value) &&
validateBST(node.getRight(), value, max);
}
}
// ...
}
Теперь некоторым людям может не понравиться видимое использование null для этого. В таком случае вам может потребоваться определить класс Range<T>, который его инкапсулирует:
public class Range<T extends Comparable<T>> {
private T min;
private T max;
private Range(T min, T max) {
this.min = min;
this.max = max;
}
public static <T> of(T min, T max) {
Objects.requiresNonNull(min);
Objects.requiresNonNull(max);
return new Range(min, max);
}
public static <T> from(T min) {
Objects.requiresNonNull(min);
return new Range(min, null);
}
public static <T> to(T max) {
Objects.requiresNonNull(max);
return new Range(null, max);
}
public static <T> all() {
return new Range(null, null);
}
public Range<T> subRangeTo(T max) {
Objects.requiresNonNull(max);
return new Range<>(this.min, max);
}
public Range<T> subRangeFrom(T min) {
Objects.requiresNonNull(min);
return new Range<>(min, this.max);
}
public boolean encloses(T value) {
Objects.requiresNonNull(value);
return (min == null || min.compareTo(value) < 0)
&& (max == null || max.compareTo(value) > 0);
}
}
Тогда код в validate более тривиален:
// ...
public boolean checkBST(Node<T> root) {
return validateBST(root, Range.all());
}
// ...
boolean validateBST(Node<T> node, Range<T> range) {
if (node == null) {
return true;
}
if (!range.encloses(node.getValue)) {
return false;
} else {
return validateBST(node.getLeft(), Range.subRangeTo(value))
&& validateBST(node.getRight(), Range.subRangeFrom(value));
}
}
// ...
Обратите внимание, что диапазоны в любом решении не включают в себя предельные значения.
Это необходимо для дерева BST, у которого нет повторяющихся ключей. Для дерева с возможными повторяющимися ключами вы можете заставить подход работать, сделав сравнение диапазона, включающее в себя принятие значений, таким же, как и его пределы.
В качестве альтернативы узлы могут содержать количество повторений для этой клавиши, поэтому ключи остаются уникальными, что имеет больше смысла, если большинство ключей будет повторяться.