[Java] Universita: algoritmo alberi AVl

[spud85]

Un albero binario di ricerca(BST) è un AVL se ogni sottoalbero avente come radice un nodo dell'albero è bilanciato in altezza.
2)si descriva un metodo che verifichi con costo computazionale lineare se un BST è un albero AVL


qualkuno sa darmi un idea su come farlo??

[LeleFT]

Letto il regolamento?
E' obbligatorio specificare il linguaggio di programmazione.

Inoltre, non è consentita la richiesta di codice completo, ma solo interventi correttivi/migliorativi su codice proprio. Per le richieste di codice completo esiste la sezione "Offro Lavoro / Collaborazione".

PS: L'indicazione "Università" nel titolo non serve a nulla e a nessuno...


Ciao.

[spud85]

1) infatti cè scritto "qualkuno sa darmi un idea su come farlo??" e nn datemi il codice...
2) ho provato a metterlo nella sezione Progrmmazione->JAva ma dicono ke nn è la sezione giusta...
3)l'indicazione universita è utile a chi affronta lo stesso argomento con esami universitari...per lo meno a me ha aiutato a volte nella ricerca di thread appositi

Cmq ho pensato di poter usare questo metodo....anke se lo devo provare..causa problemi con jcreator



public boolean isAVL(BSTnode r) { //dove r è il riferimento alla radice

boolean temp =true;
int a = height(r.left);
int b = height(r.right);
if ((Math.abs(a-b)) >2)
temp=false;
else
isAVL(r.left) && isAVL(r.right);
return temp;

}

public int height(BSTnode r) {
if (r==o) return 0;
else
return 1 +height(r.left) + height(r.right);
}

[LeleFT]

Originariamente inviato da spud85
1) infatti cè scritto "qualkuno sa darmi un idea su come farlo??" e nn datemi il codice...

E va bene... ma se non indichi con quale linguaggio intendi realizzare la cosa, nessuno saprà mai se ti sta dando un'informazione utile... e non mi pare il caso di fornire un'informazione per ciascun linguaggio, per non rendere incomprensibile il thread.

2) ho provato a metterlo nella sezione Progrmmazione->JAva ma dicono ke nn è la sezione giusta...

L'utente che ha scritto questa cosa, probabilmente, lo ha fatto proprio perchè la tua richiesta era troppo generica...

3)l'indicazione universita è utile a chi affronta lo stesso argomento con esami universitari...per lo meno a me ha aiutato a volte nella ricerca di thread appositi

Lo stesso argomento può essere affrontato in diversi ambiti, non solo ristretti a quello universitario, soprattutto in un forum frequentato da una moltitudine di persone (studenti di ogni grado, appassionati e professionisti, che possono tutti avere il tuo stesso problema): ergo, tale indicazione è del tutto inutile (ma ci si può sorvolare tranquillamente sopra). Assolutamente non inutile, invece, l'informazione sul linguaggio.

Visto che, quindi, si tratta di Java, provvedo io ad inserire tale informazione nel titolo (come da regolamento) e a spostare nell'apposita sezione. L'altra discussione ti è stata chiusa per altri motivi (cross-posting).

Cmq ho pensato di poter usare questo metodo....anke se lo devo provare..causa problemi con jcreator

public boolean isAVL(BSTnode r)  { //dove r è il riferimento alla radice
 
    boolean temp =true;
    int a = height(r.left);
    int b = height(r.right);
    if ((Math.abs(a-b)) >2) 
           temp=false;
    else 
          isAVL(r.left) && isAVL(r.right);
     return temp;

}

public int height(BSTnode r)  {
    if (r==o) return 0;
    else
    return 1 +height(r.left) + height(r.right); 
}

Ciao.

[spud85]

Originariamente inviato da spud85
1) infatti cè scritto "qualkuno sa darmi un idea su come farlo??" e nn datemi il codice...
2) ho provato a metterlo nella sezione Progrmmazione->JAva ma dicono ke nn è la sezione giusta...
3)l'indicazione universita è utile a chi affronta lo stesso argomento con esami universitari...per lo meno a me ha aiutato a volte nella ricerca di thread appositi

Cmq ho pensato di poter usare questo metodo....anke se lo devo provare..causa problemi con jcreator



public boolean isAVL(BSTnode r) { //dove r è il riferimento alla radice

boolean temp =true;
int a = height(r.left);
int b = height(r.right);
if ((Math.abs(a-b)) >2)
temp=false;
else
isAVL(r.left) && isAVL(r.right);
return temp;

}

public int height(BSTnode r) {
if (r==o) return 0;
else
return 1 +height(r.left) + height(r.right);
}

no...ho sbagliato il metodo height mi da il numero di nodi e nn l'altezza dell'albero...

[Pastore12]

/**
* ...
* @param r la radice dell'albero AVL
*/
public boolean isAVL(BSTnode r)
{ 

    boolean temp = true;
    int a = height(r.left);
    int b = height(r.right);

    // Immagino sia la definizione di BST bilanciato
    if ((Math.abs(a-b)) > 2)
        temp=false;
    else
        // forse temp = ...
        isAVL(r.left) && isAVL(r.right);
    return temp;

}

public int height(BSTnode r)
{
    // [b]o[/b] da dove salta fuori?
    // Forse dovresti controllare se entrambi i figli sono nulli
    if (r==o)
        return 0;
    else
        return 1 +height(r.left) + height(r.right);
} 

[spud85]

Originariamente inviato da Pastore12

/**
* ...
* @param r la radice dell'albero AVL
*/
public boolean isAVL(BSTnode r)
{ 

    boolean temp = true;
    int a = height(r.left);
    int b = height(r.right);

    // Immagino sia la definizione di BST bilanciato
    if ((Math.abs(a-b)) > 2)
        temp=false;
    else
        // forse temp = ...
        isAVL(r.left) && isAVL(r.right);
    return temp;

}

public int height(BSTnode r)
{
    // [b]o[/b] da dove salta fuori?
    // Forse dovresti controllare se entrambi i figli sono nulli
    if (r==o)
        return 0;
    else
        return 1 +height(r.left) + height(r.right);
} 

il metodo height è sbagliato....restituisce il numero di nodi anziche il numero di livelli dell'albero....

[Pastore12]

Non me ne ero accorto.. be' facile no? altro calcolo ricorsivo:

altezza padre = 1 + max (altezza figlio destro, altezza figlio sinistro)

Solo che a sto' punto siamo ancora in O(n)? mmm...

[spud85]

credo di aver risolto...
il metodo height dovrebbe essere cosi...

public static int height(BSTnode r) {
if(r ==null) //albero vuoto
return -1;
else {
int a = height(a.left);
int b= height(b.right);
if (a>b) return a+1;
else return b+1;
}
}

[spud85]

si infatti....
ho appena risolto......
quindi sono stato bocciato all'esame di algoritmi per un esercizio cosi facile VVoVe: