Блог

Для проверки дерева двоичного поиска требуется минимальный и максимальный диапазон перед началом проверки с корневого узла.

ниже приведен мой код, чтобы сделать это для Integer.

  public boolean checkBST(Node root) {
    int min = Integer.MIN_VALUE;
    int max = Integer.MAX_VALUE;
    return validateBST(root, min, max);
  }
  

Ссылка : https://en.wikipedia.org/wiki/Binary_search_tree#Verification

По мере продвижения проверки вниз по дереву допустимый диапазон уменьшается в зависимости от значения, найденного в узле поддерева. Однако для узла verify top мне нужно указать диапазон, который будет принимать любое значение.

Это легко сделать с помощью оболочек числового примитивного типа, таких как Integer (пример выше) или Double , если вы фиксируете определенный тип элемента. Однако мне нужно обобщить этот подход, чтобы он работал с любым заданным T типом (это может быть Number или что-то совершенно другое).

Мы можем предположить, что T это Comparable<? extends T> или что соответствующий компаратор передается при построении дерева.

Как я могу это сделать?

Для сравнения объектов вам необходимо их реализовать Comparable поэтому определите тип вашего узла как подкласс Comparable :

 class Node<Q extends Comparable<Q>>{

    private final Q value;
    private Node left, right;   

    Node getLeft() {
        return left;
    }

    Node getRight() {
        return right;
    }

    Node(Q value){
        this.value = value;
    }

    Q getValue(){
        return value;
    }
}
  

Когда Q реализуется comparable, вы можете сравнить два объекта, например:

 Node<String> minNode = new Node<>("Z");
Node<String> maxNode = new Node<>("A");
Node<String> aNode = new Node<>("L");
System.out.println(aNode.getValue().compareTo(minNode.getValue())< 0 amp;amp;
                            aNode.getValue().compareTo(maxNode.getValue()) > 0 );
  

Имея возможность сравнивать, вы должны быть в состоянии определить boolean isBST(Node node, Node minNode, Node maxNode)

Редактировать: Если ваш вопрос касается «общей версии Integer.MIN_VALUE и Integer.MAX_VALUE для любого заданного T»:
Я не думаю, что это практически необходимо. Вы могли бы выполнить итерацию по всему графику, найти минимальные, максимальные значения и использовать эти значения.

Если я правильно понимаю вопрос, вы спрашиваете, как определить абсолютное максимальное или минимальное значение для любого заданного типа, чтобы вы могли указать диапазон, который принимал бы любое значение как допустимое.

К сожалению, в общем случае произвольный T не обязательно имеет инстанцируемый минимум и максимум. На самом деле int и Integer делаю только потому, что из-за ограничения представления они не могут быть сколь угодно большими или маленькими.

Например, для String можно утверждать, что тогда пустая строка («») является минимальной, безусловно, меньше или равна любой другой, String используя ее естественный порядок, но какова была бы максимальная строка. Вероятно, это привело бы к бесконечно долгому повторению максимального символа Юникода, поэтому вы не можете создать такой объект.

Однако это не должно мешать вам определять диапазоны, которые включали бы любое значение или которые были бы открыты на одном конце (т. Е. у них есть min, но не max или наоборот).

Например, если диапазон должен быть указан в виде двух аргументов в сигнатуре метода, который собирается использовать такой диапазон, тогда вы можете просто обозначить null как, чтобы указать, что этот минимальный или максимальный размер не существует, то есть этот конец диапазона открыт.

Мне кажется, это будет хорошо работать с вашим 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 amp;amp; min.compareTo(value) >= 0) {
             return false;
         } else if (max != null amp;amp; max.compareTo(value) <= 0) {
             return false;
         } else {
             return validateBST(node.getLeft(), min, value) amp;amp;
                    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) 
            amp;amp;  (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)) 
                   amp;amp; validateBST(node.getRight(), Range.subRangeFrom(value));
         }
   }
   // ...

  

Обратите внимание, что диапазоны в любом решении не включают предельные значения.

Это необходимо для дерева BST, в котором нет повторяющихся ключей. Для дерева с возможными повторяющимися ключами вы можете заставить подход работать, сделав сравнение диапазона «охватывающим», чтобы принимать значения, совпадающие с его пределами.

В качестве альтернативы узлы могут содержать количество повторений для этого ключа, чтобы ключи оставались уникальными, что имеет больше смысла, если большинство ключей будут повторяться.