Использование универсального класса Pair и Splaytree для подсчета и хранения слов и их частот в Java

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 для частот. Это не жертвует сложностью, поскольку операции над деревом сопряжения выполняются O(log n), а операции над HashMap О (1). Чтобы сохранить инкапсуляцию и инварианты, вы можете поместить оба в больший класс, который предоставляет необходимые операции.