1

我正在尝试使用 AVL 树实现 Dictionary ADT，但 findAll(K key) 方法遇到了问题。我知道如何使用 entry() 方法并遍历每个方法来做到这一点，但我需要我的方法为 O(logn)，所以我需要使用 treeSearch(key, position) 方法。我的字典看起来像这样： 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