Classe Nodo:
codice:
/**
* Classe node per un BST che contiene la chiave di tipo intero e un valore di tipo String.
*
* Si richiede che per ogni nodo la sua chiave sia strettamente maggiore di quelle memorizzate
* nel sottoalbero sinistro e minore o uguale di quelli nel sottoalbero destro.
*
Come conseguenza di cio' i valori con chiave duplicata devono essere inseriti nel ramo destro.
*/
public final class BSTNode {
private int key;
private String value;
private BSTNode left;
private BSTNode right;
/**
* costruisce un nodo vuoto
*/
public BSTNode() {
}
/**
* ritorna la chiave
*
* @return chiave
*/
public int getKey() {
return key;
}
/**
* imposta il valore della chiave
*
* @param key chiave
*/
public void setKey(int key) {
this.key = key;
}
/**
* restutisce il sottoalbero sinistro
*
* @return sottoalbero sinistro o null se non presente
*/
public BSTNode getLeft() {
return left;
}
/**
* imposta il valore del sottoalbero sinistro
*
* @param left sottoalbero sinistro
*/
public void setLeft(BSTNode left) {
this.left = left;
}
/**
* restituisce il riferimento al sottoalbero destro
*
* @return sottoalbero destro o null se non presente
*/
public BSTNode getRight() {
return right;
}
/**
* imposta il riferimento al sottoalbero destro
*
* @param right sottoalbero destro
*/
public void setRight(BSTNode right) {
this.right = right;
}
/**
* ritorna il valore associato al nodo
*
* @return valore associato al nodo
*/
public String getValue() {
return value;
}
/**
* imposta il valore associato al nodo
*
* @param value valore da impostare
*/
public void setValue(String value) {
this.value = value;
}
@Override
public String toString() {
return "<" + key + "=" + value + ">";
}
}
Interfaccia Dizionario
codice:
import java.util.*;
/**
* Interfaccia di un BST che implementa un dizionario contenente coppie chiave valore rispettivamente di tipo intero e String.
* Il dizionario deve ammettere chiavi multiple.
* Nel BST i valori duplicati devono essere inseriti nell'albero destro.
*/
public interface BSTDictionary {
/**
* a partire dalla chiave intera, viene restituito il valore associato. Se la chiave non fa parte del BST allora rescituisce null.
* Nel caso in cui siano presenti piu' chiavi uguali, deve restituire uno qualunque dei valori.
*
* @param key chiave
* @return valore associato alla chiave oppure null se la chiave non fa parte del dizionario.
*/
public String find(int key);
/**
* restituisce tutti i valori associati alla chiave. Se la chiave non e' presente, resituisce null.
*
* @param key chiave
* @return elenco dei valori associati alla chiave
*/
public List<String> findAll(int key);
/**
* inserisce una nuova coppia chiave valore, da aggiungere al dizionario.
* Si ricorda che il dizionario ammette duplicati.
*
* @param key chiave
* @param value valore
*/
public void insert(int key, String value);
/**
* controlla se l'albero e' vuoto (cioe' ha radice nulla)
*
* @return true o false a seconda se l'albero e' vuoto o no
*/
public boolean isEmpty();
/**
* restituisce la radice dell'albero
*
* @return radice dell'albero o null se l'albero e' vuoto
*/
public BSTNode root();
/**
* ritorna il numero di nodi dell'albero
*
* @return numero di nodi dell'albero
*/
public int size();
/**
* rimuove tutte le chiavi dell'albero strettamente maggiori della chiave specificata.
* Il metodo deve effettuare side - effect sui nodi dell'albero this.
* @param key chiave specificata
*/
public void removeHigh(int key);
}
codice:
import java.util.*;
/**
* Questa classe deve essere implementata per poter risolvere l'homework
* Si ricorda che il nome della classe deve essere Homework5Impl e non deve essere
*/
public abstract class Homework5 {
/**
* le sottoclassi dovranno avere un solo costruttore senza argomenti
*/
public Homework5() {
if (getClass().getConstructors().length != 1) {
throw new RuntimeException(String.format(
"ATTENZIONE!!! La sottoclasse deve avere solo il costrutture senza argomenti. Trovati %d costruttori",
getClass().getConstructors().length));
}
if (getClass().getConstructors()[0].getParameterTypes().length > 0)
throw new RuntimeException(String.format(
"ATTENZIONE!!! La sottoclasse deve avere solo il costrutture senza argomenti. Trovato un costruttore con %d argomenti",
getClass().getConstructors().length));
if (!getClass().getSimpleName().equals("Homework5Impl") &&
!getClass().getSimpleName().equals("Homework5ImplSolver")) {
throw new RuntimeException("ATTENZIONE!!! La sottoclasse deve avere nome Homework5Impl");
}
if (getClass().getPackage() != null) {
throw new RuntimeException("ATTENZIONE!!! La sottoclasse non deve appartenere ad alcun PACKAGE");
}
}
/**
* restituisce un nuovo dizionario vuoto
*
* @return restituisce un nuovo dizionario vuoto
*/
public abstract BSTDictionary createEmptyDictionary();
/**
* restituisce tutte le chiavi comuni ai due dizionari. In caso di duplicati restituire un unico valore per la chiave.
* Il metodo dovra' avere costo lineare rispetto al numero di nodi.
*
* @param d1 primo dizionario
* @param d2 secondo dizionario
* @return chiavi comuni ad entrambi i dizionari
*/
public abstract Set<Integer> commonKeys(BSTDictionary d1, BSTDictionary d2);
}
Queste sono classi già fornite, io devo realizzare questa:
codice:
import java.util.*;
public class Homework5Impl extends Homework5
{
public Homework5Impl() {}
class BSTDictionaryImpl implements BSTDictionary
{
private BSTNode root;
public BSTDictionaryImpl()
{
root = null;
}
//Ritorna l'elemento del nodo con chiave key
public String find(int key)
{
return findRic(key,root);
}
private String findRic(int k, BSTNode v)
{
if(isExternal(v))
{
return v.getValue();
}
if(k < v.getKey())
{
return findRic(k, v.getLeft());
}
else if(k == v.getKey())
{
return v.getValue();
}
else
{
return findRic(k, v.getRight());
}
}
//Ritorna il nodo che ha la stessa chiave passata come parametro
private BSTNode treeSearch(int k, BSTNode v)
{
if(isExternal(v))
{
return v;
}
if(k < v.getKey())
{
return treeSearch(k, v.getLeft());
}
else if(k == v.getKey())
{
return v;
}
else
{
return treeSearch(k, v.getRight());
}
}
private boolean isExternal(BSTNode v)
{
return ((v.getLeft() == null) && (v.getRight()==null));
}
public List<String> findAll(int key)
{
List<String> ris = new LinkedList<String>();
addAll(ris,root,key);
return ris;
}
private void addAll(List<String> L, BSTNode v, int key)
{
if(isExternal(v))
{
return;
}
BSTNode pos = treeSearch(key, v);
if(!isExternal(pos))
{
addAll(L,pos.getLeft(),key);
L.add(L.size()-1, pos.getValue());
addAll(L,pos.getRight(),key);
}
}
public void insert(int key, String value)
{
BSTNode toInsert = new BSTNode();
toInsert.setKey(key);
toInsert.setValue(value);
insert(key,value,toInsert);
}
private void insert(int key, String value, BSTNode v)
{
BSTNode w = treeSearch(key,v);
if(!isExternal(w))
{
insert(key,value,w.getRight());
}
insertAtExternal(w,key,value);
}
private void insertAtExternal(BSTNode v, int key, String value)
{
v.setKey(key);
v.setValue(value);
v.setLeft(new BSTNode());
v.setRight(new BSTNode());
}
public boolean isEmpty()
{
return this.root == null;
}
public BSTNode root()
{
return this.root;
}
public int size()
{
if(root == null)
{
return 0;
}
else return sizeRic(root,1);
}
private int sizeRic(BSTNode v, int s)
{
if(v.getLeft() != null)
{
s = 1 + sizeRic(v.getLeft(),s);
}
if(v.getRight() != null)
{
s = 1 + sizeRic(v.getRight(),s);
}
return s;
}
private BSTNode findParent(BSTNode v)
{
return findParentRic(this.root, v);
}
private BSTNode findParentRic(BSTNode root, BSTNode v) <--- QUI MI SERVE AIUTO
{
if(root.getKey() < v.getKey())
{
BSTNode d = root.getRight();
if(d.getKey() == v.getKey() && d.getValue().equals(v.getValue()))
{
return root;
}
return findParentRic(d,v);
}
else if(root.getKey() > v.getKey())
{
BSTNode s = root.getLeft();
if(s.getKey() == v.getKey() && s.getValue().equals(v.getValue()))
{
return root;
}
return findParentRic(s,v);
}
else
return null;
}
private void removeExternal(BSTNode v)
{
.....
}
public void remove(int key)
{
.....
}
public void removeHigh(int key)
{
}
}
/*Il metodo restituisce un nuovo dizionario inizialmente vuoto. Il metodo
al suo interno potra' utilizzare la classe BSTDictionaryImpl descritta
nella successiva sotto-sezione.*/
public BSTDictionary createEmptyDictionary()
{
BSTDictionary ris = new BSTDictionaryImpl();
return ris;
}
/*Il metodo restituisce l'insieme delle chiavi comuni ai due dizionari. In
caso di chiavi duplicate in uno o entrambi i dizionari deve restituire un
unico valore per la chiave.
Il metodo dovra' avere costo lineare rispetto al massimo tra
le dimensioni dei due dizionari.*/
public Set<Integer> commonKeys(BSTDictionary d1, BSTDictionary d2)
{
..........
}
}
Permessi di invio
Rispondi quotando