1

AVL ツリーを使用して Dictionary ADT を実装しようとしていますが、findAll(K key) メソッドに問題があります。entry() メソッドを使用してそれぞれを反復処理する方法を知っていますが、メソッドを O(logn) にする必要があるため、treeSearch(key, position) メソッドを使用する必要があります。私の Dictionary は次のようになります: public class FoodDictionary, V> implements Dictionary {

/** List in which all the entries are stored. */
private AVLTree<K,V> dictionary;

/** Create a new, empty unordered Dictionary. */
public FoodDictionary() {
    dictionary = new AVLTree<K,V>();
}

/**
 * FOR TESTING PURPOSES ONLY! 
 */
protected AVLTree<K,V> getTree(){
    return dictionary;
}

/**
 * Returns an iterable object of all the entries in the tree
 * @returns the tree, an iterable object
 */
public Iterable<Entry<K, V>> entries() {
    return dictionary;
}

/**
 * Returns the first entry found with the matching
 * key.
 * @param key the key to be found
 * @return the first entry found 
 */
public Entry<K, V> find(K key) {
    return dictionary.find(key).element();
}

/**
 * Returns all of the entries with the given key
 * 
 * @param key the key to be found 
 * @return an iterable object containing all the 
 * entries found with the given key
 */
public Iterable<Entry<K, V>> findAll(K key) {
    PLSequence<Entry<K,V>> list = new PLSequence<Entry<K,V>>();
    for(Entry<K,V> entry : entries()){
        if(entry.getKey().equals(key)){
            list.addLast(entry);
        }
    }
    return list;
}


/**
 * Returns the size of the dictionary
 * @return the size of the dictionary
 */
@Override
public int size() {
    return dictionary.size();
}

/**
 * Returns whether or not the dictionary 
 * is empty
 * @return true if the dictionary is empty
 *          false if the dictionary is not empty
 */
@Override
public boolean isEmpty() {
    return dictionary.isEmpty();
}

/**
 * Adds an entry to this dictionary
 * @param key they key of the new entry
 * @param value the value of the new entry
 * @return the new entry added to the dictionary
 * @throws InvalidKeyException if the given key was not valid
 */
@Override
public Entry<K, V> insert(K key, V value) throws InvalidKeyException {
    return dictionary.add(key, value);
}

/**
 * Removes an entry from this dictionary
 * @param e the entry to be removed
 * @return the entry removed or null if it was not found
 * @throws InvalidEntryException if the entry input was invalid
 */
@Override
public Entry<K, V> remove(Entry<K, V> e) throws InvalidEntryException {
    return dictionary.remove(e.getKey());
}
}

現在、私が言ったように、私のfindAll()はentries()を使用して反復していますが、どうにかしてtreeSearch()を使用する必要がありますこの実装で誰か助けてもらえますか?完成させる時間があまりなく、アイデアが完全に失われています。どんな助けでも大歓迎です!

4

0 に答える 0