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

Gender: Male
Posts: 505



« on: 29-03-2011, 19:01:52 »

Qualcuno sa risolvere questo metodo?

Quote
Alberi autobilancianti
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 è il seguente:

public void selfBallance ();
// ristruttura l'albero trasformandolo in un albero completo a
meno dell'ultimo livello che deve essere riempito da sinistra a
destra


Grazie a chiunque risponda..
Logged
Angelo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 274



« Reply #1 on: 30-03-2011, 07:30:33 »

per, diciamo, "sistemarlo" avvaliti dei metodi Left e Right Rotate.. 
Logged

..elimindo il ponte pedonale di andrea doria..hanno eliminato una parte di me!..
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #2 on: 30-03-2011, 08:33:05 »

Si anche io avevo pensato questo ma il professore mi ha fatto ragionare, dicendomi che se per esempio un albero è molto sbilanciato o verso dx o verso sx, devo ogni volta capire dove applicare la left o right rotate.. Risultato dietro ci sta un algoritmo molto molto complesso..
Qualcun'altra idea? Grazie
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #3 on: 01-04-2011, 10:55:24 »

UP
Logged
Pages: [1]   Go Up
Print
Jump to: