Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: vincenzo86 on 14-07-2010, 09:24:22



Title: Alberi autobilanciati
Post by: vincenzo86 on 14-07-2010, 09:24:22
Qualcuno si è accorto che in questo esercizio è richiesta l'implementazione degli alberi AVL? Avete provato a implementarlo?  Grazie


Title: Re:Alberi autobilanciati
Post by: vincenzo86 on 17-07-2010, 12:28:57
Novità


Title: Re:Alberi autobilanciati
Post by: XDnl on 17-07-2010, 13:04:50
Non ho svolto l'esercizio, ma non credo lo scopo sia implementare gli alberi AVL.


Title: Re:Alberi autobilanciati
Post by: vincenzo86 on 29-10-2010, 17:29:21
Quote
Un albero si dice autobilanciante se è in grado di modificare la propria struttura in modo
tale da trasformarsi in un albero completo, a meno dell'ultimo livello che è riempito da
sinistra verso destra.
Implementare l'interfaccia mostrata di seguito rappresentante un albero autobilanciante i
cui nodi contengono come valori delle stringhe.
I nodi dell'albero sono degli oggetti BTNode (se ne fornisca l'implementazione)
Tempo di risoluzione: 2 ore
Interfaccia SelfBallancedTree
public interface SelfBallancedTree {
public int size ();
// ritorna il numero di nodi contenuti nell'albero
public BTNode root () throws EmptyTreeException;
// ritorna la radice dell'albero
public BTNode left (BTNode x) throws InvalidArgumentException;
// ritorna il figlio sinistro del nodo dell'albero x
public BTNode right (BTNode x) throws InvalidArgumentException;
// ritorna il figlio destro del nodo dell'albero x
public BTNode parent (BTNode x) throws InvalidArgumentException;
// ritorna il padre del nodo dell'albero x
public int size (BTNode x) throws InvalidArgumentException;
// ritorna il numero di nodi nel sottoalbero radicato in x
public void insert (String s);
// inserisce nell'albero un nuovo nodo con valore e
public BTNode delete (String s);
// cancella un nodo contenente il valore e. Restituisce il nodo
public boolean isBallanced (BTNode x);
// restituisce true se il sottoalbero radicato in x è completo,
a meno dell'ultimo livello (eventualmente riempito da sinistra)
public void selfBallance ();
// ristruttura l'albero trasformandolo in un albero completo a
meno dell'ultimo livello che deve essere riempito da sinistra a
destra
}
Il metodo selfBallance() cosa deve fare di preciso? Io avevo pensato a implementare le procedure right rotate e left rotate dopo aver effettuato un controllo del tipo:
Code:
if(isBallanced(root))
 return; //in questo caso non fare nulla
else
{
    //procedure di right e left da implementare;

Potrebbe essere una strada possibile?
Grazie


Title: Re:Alberi autobilanciati
Post by: vincenzo86 on 30-10-2010, 10:40:52
Qualcuno di buona volontà che risponda c'è? Grazie