如何使用任意类型的键定义通用二进制搜索树验证的通用值范围（包括开放范围）

Question

二进制搜索树验证在从根节点开始验证之前需要最小和最大范围。

下面是我为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

随着验证在树中向下进行，根据在子树节点处找到的值，有效范围被指定。但是对于验证顶级节点，我需要指定一个可以接受任何值的范围。

如果您提交特定的元素类型，使用Integer（上面的示例）或Double等数字原始类型包装器很容易。然而，我需要概括这种方法，以便它适用于任何给定的T类型（它可能是一个Number，或完全不同的东西）。

我们可以假设T是Comparable<? extends T>，或者在构造树时传递适当的比较器。

我怎样才能做到这一点？

Answer 1

要比较对象，你需要它们来实现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实现可比较时，您可以比较两个对象，例如：

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 &&
                            aNode.getValue().compareTo(maxNode.getValue()) > 0 );

能够比较，你应该能够定义boolean isBST(Node node, Node minNode, Node maxNode)

编辑：如果您的问题是关于“任何给定T的Integer.MIN_VALUE和Integer.MAX_VALUE的通用版本”： 我不认为这是实际需要的。您可以迭代整个图形查找最小值，最大值并使用这些值。

Answer 2

如果我正确理解了这个问题，那么您就会问如何计算出任何给定类型的绝对最大值或最小值，以便您可以指定一个接受任何值作为有效值的范围。

不幸的是，一般来说，任意T不一定具有可实例化的最小值和最大值。实际上int和Integer只是因为代表性限制而不能任意大或小。

例如，对于String，人们可以争辩说，空字符串（“”）是最小值，当然小于或等于使用其自然顺序的任何其他String，但最大字符串是什么。它可能会无限长地重复最大的unicode字符，因此您无法创建这样的对象。

但是，这不应该阻止您能够定义包含任何值的范围或者它们在一端打开的范围（即它们具有最小值但不具有最大值或反之亦然）。

例如，如果要将范围指定为将要使用此类范围的方法的签名中的两个参数，则可以简单地将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);
    }
}

然后验证中的代码更加简单：

   // ...
   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树是必需的。对于具有可能重复键的树，您可以通过使范围“封闭”与接受值的比较与其限制相同来使方法起作用。

或者，节点可以保持该键的重复次数，因此键保持唯一，如果大多数键将被重复，则更有意义。