java - 在 Java 中使用通用 Pair 类和 Splaytree 来计数和存储单词及其频率

Question

我正在实现一个 splaytree 来保存单词及其频率，并选择创建一个 Pair 类来保存每个单词频率(键值)对。也就是说，splaytree的每个节点都保存一对Pair类。 Pair 类如下所示:

public class SplayEntry<K, V> implements Comparable<SplayEntry<K, V>>{

public K word;
public V frequency;

public SplayEntry(K word, V frequency) {
    this.word = word;
    this.frequency = frequency;
}
getters, setters, hashCode, equals, compareTo etc...

Splaytree:

public class SplayTree<AnyType extends Comparable<? super AnyType>> {

public SplayTree( )
{
    nullNode = new BinaryNode<AnyType>( null );
    nullNode.left = nullNode.right = nullNode;
    root = nullNode;
}

并具有 BinaryNode 类。

我遇到的问题是如何将每个单词和频率对放入树中，并检查该对是否已经存在，如果存在则将频率增加一。我逐行读取文本文件并将每一行拆分为单词，然后执行 countWords() 方法，但现在很困惑:

    public void countWords(String line) {
    line = line.toLowerCase();
    String[] words = line.split("\\P{L}+");
    SplayEntry<String, Integer> entry = new SplayEntry<String, Integer>(null, null);
    for (int i = 0, n = words.length; i < n; i++) {
        Integer occurances = 0;
        entry.setWord(words[i]);
        entry.setFrequency(occurances);

        if (tree.contains(entry.equals(entry)) && entry.getFrequency() == 0) {
            occurances = 1;

        } else {
            int value = occurances.intValue();
            occurances = new Integer(value + 1);
            entry.setFrequency(occurances);
        }

        entry = new SplayEntry<String, Integer>(words[i], occurances);
        tree.insert(entry);
    }
}

我知道这并没有真正起作用，我需要帮助来弄清楚应该如何实例化 SplayEntry 类以及以什么顺序？我还想要该方法，对于单词数组中的每个单词，检查它是否存在于树内的 SplayEntry 中(包含)，如果该单词是新单词，则频率将为 1，否则，频率将为是+1。最后，我将新的 SplayEntry 添加到 Splaytree 中，并将其放入适当的节点中。

现在，我只是因为在同一段代码上工作了太多时间而不是必要的时间而让自己感到困惑，我非常感谢一些可以引导我走向正确方向的指示!

如果我没有说清楚，请告诉我。

Answer 1

我建议使用伸展树(Splay Tree)的标准实现，即没有计数器，并为频率使用单独的HashMap。这不会牺牲复杂性，因为伸展树(Splay Tree)上的操作为 O(log n)，而 HashMap 上的操作为 O(1)。为了保留封装性和不变量，您可以将它们放在一个更大的类中，以公开所需的操作。