Binary Search Tree implementation of DictionaryADT. The only public functions in

Question

Binary Search Tree implementation of DictionaryADT. The only public functions in the Binary Search Tree files are the ones implemented from DictionaryADT. For comparing two things just use (((Comparable<K>)key).compareTo(x.key) < 0) for something like (key < x.key). The iterators must be fail fast. Use the functions provided

import java.util.Iterator;

import java.util.NoSuchElementException;

public interface DictionaryADT<K,V> {

// Returns true if the dictionary has an object identified by

// key in it, otherwise false.

public boolean contains(K key);

// Adds the given key/value pair to the dictionary. Returns

// false if the dictionary is full, or if the key is a duplicate.

// Returns true if addition succeeded.

public boolean insert(K key, V value);

// Deletes the key/value pair identified by the key parameter.

// Returns true if the key/value pair was found and removed,

// otherwise false.

public boolean remove(K key);

// Returns the value associated with the parameter key. Returns

// null if the key is not found or the dictionary is empty.

public V getValue(K key);

// Returns the key associated with the parameter value. Returns

// null if the value is not found in the dictionary. If more

// than one key exists that matches the given value, returns the

// first one found.

public K getKey(V value);

// Returns the number of key/value pairs currently stored

// in the dictionary

public int size();

// Returns true if the dictionary is at max capacity

public boolean isFull();

// Returns true if the dictionary is empty

public boolean isEmpty();

// Returns the Dictionary object to an empty state.

public void clear();

// Returns an Iterator of the keys in the dictionary, in ascending

// sorted order. The iterator must be fail-fast.

public Iterator<K> keys();

// Returns an Iterator of the values in the dictionary. The

// order of the values must match the order of the keys.

// The iterator must be fail-fast.

public Iterator<V> values();

}

Explanation / Answer

BST Find:

Algorithm find(node n,key k)

Input:the node at the root of the tree to explore.The key k to find

Output;returns one mode with equal key to k

if(n=null) return null

if(n.key>e) return find(n.leftchild,k)

if(n.key<e) return find(n.rightchild,k)

Note:you can modify this code a bit depending the functions provided

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.