Java 中泛型的排序

Question

我必须实现一个通用的 AVL 树作为作业。它的定义如下：

public class AVL<Key,Elem>;

问题是我假设在某个时候，我必须比较键来决定在节点的哪一侧分配元素。出于本作业的目的，将使用整数作为键。

由于没有给出其他限制或信息，我首先想到假设 Key 始终是一个 Integer。然而，这使得通用的“钥匙”变得多余，我认为这并不是老师们所期望的。因此，我认为最好的解决方案包括强制作为 Key 传递的任何内容实现 Comparator 或类似的东西（我真的从未使用过 Comparator，只是猜测），然后使用该比较器来比较 Key 而不是使用 ==,<,>;和 != 运算符。但是，我不知道该怎么做。有什么提示吗？

提前致谢。

Answer 1

尝试 public class AVL,Elem>; 并使用 Comparable 所需的 compareTo() 方法code> 接口，由 Integer 实现。

Answer 2

标准 Java API 中的 SortedMap 和 SortedSet 实现使用 Comparator 并调用其 compare(k1, k2) 方法，或者假设键实现了 Comparable，并调用 k1.compareTo(k2)。大多数都提供两者，具体取决于使用哪个构造函数。 （EnumMap/EnumSet 不支持，因为它们仅支持按声明顺序对枚举值进行内置排序。）

Comparable 方法要求键始终以相同的方式排序，并且将用于具有规范排序（如整数）的键，您希望在其中使用此排序。

Comparator 方法更加灵活，因为您可以将相同的键对象用于顺序不同的不同映射，并且可以将其用于您无法控制或无法控制的键具有规范的排序（如列表、树/图等）。您还可以使用 Collat​​or（这是一个实现 Comparator 的类），使用它根据纯 unicode 值之外的其他标准（例如基于区域设置）对字符串键进行排序。

两者都需要键上的总顺序，但我认为这对于您的 AVL 树也是必要的。

这是一个适用于任何可比较对象的 Comparator 实现，因此您可以使用它（可能在内部）作为 Comparable 变体的适配器。 。

 public static <X extends Comparable<X>> Comparator<X> makeComparator() {
     return new Comparator<X>() {
         public int compare(X left, X right) {
             return left.compareTo(right);
         }
     };
 }