Pages: [1]   Go Down
Print
Author Topic: Alberi autobilanciati  (Read 1281 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« 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
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #1 on: 17-07-2010, 12:28:57 »

Novità
Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #2 on: 17-07-2010, 13:04:50 »

Non ho svolto l'esercizio, ma non credo lo scopo sia implementare gli alberi AVL.
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #3 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
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #4 on: 30-10-2010, 10:40:52 »

Qualcuno di buona volontà che risponda c'è? Grazie
Logged
Pages: [1]   Go Up
Print
Jump to: