Alberi AVL fattore bilanciamento
Ciao a tutti!
Sono 2 giorni che sto sclerando per capire bene come funziona il fattore di bilanciamento di un albero AVL senza però riuscirci molto bene
Prendiamo questo albero come esempio:
Ora vi illustro come ho proceduto io a calcolare sto benedetto fattore (FdB = fattore di bilanciamento).
La regola dice altezza s.a. SX - altezza s.a DX (s.a = sottoalberi).
1) $9-14-19-67-76$ sono le foglie e quindi stanno sempre a $0$ giusto?
2) siccome $9-14$ sono a $0$ allora $12$ è a $0$ (questa è una proprietà oppure c'è un motivo matematico che non so??)
3) $23$ ha $FdB= -1$ perchè a DX essendo vuoto ha valore $-1$ e SX si ha il valore $0$ e non capisco perchè. Scusate ma se 23 è la radice del sottoalbero da 23 a 19 incontro 1 nodo quindi avrò 1 come valore no?? E perchè invece si ha 0?
4) $54$ ha $Fdb = -1$ per $-1- 0$ (di nuovo, perchè 0???)
5) $72$ ha $FdB = 1$ per $1-0$ (ancora, perchè dell'ultimo non tengo conto?)
6) $17$ ha $FdB = 0$ per $1-1$
7) $50$ ha $FdB = 0$ perchè ho $2$ dei nodi (17-12) $- 2$ dei nodi (72-54)
Grazie in anticipo!
Sono 2 giorni che sto sclerando per capire bene come funziona il fattore di bilanciamento di un albero AVL senza però riuscirci molto bene
Prendiamo questo albero come esempio:
Ora vi illustro come ho proceduto io a calcolare sto benedetto fattore (FdB = fattore di bilanciamento).
La regola dice altezza s.a. SX - altezza s.a DX (s.a = sottoalberi).
1) $9-14-19-67-76$ sono le foglie e quindi stanno sempre a $0$ giusto?
2) siccome $9-14$ sono a $0$ allora $12$ è a $0$ (questa è una proprietà oppure c'è un motivo matematico che non so??)
3) $23$ ha $FdB= -1$ perchè a DX essendo vuoto ha valore $-1$ e SX si ha il valore $0$ e non capisco perchè. Scusate ma se 23 è la radice del sottoalbero da 23 a 19 incontro 1 nodo quindi avrò 1 come valore no?? E perchè invece si ha 0?
4) $54$ ha $Fdb = -1$ per $-1- 0$ (di nuovo, perchè 0???)
5) $72$ ha $FdB = 1$ per $1-0$ (ancora, perchè dell'ultimo non tengo conto?)
6) $17$ ha $FdB = 0$ per $1-1$
7) $50$ ha $FdB = 0$ perchè ho $2$ dei nodi (17-12) $- 2$ dei nodi (72-54)
Grazie in anticipo!
Risposte
L'albero non riesco a vederlo. In ogni caso mi sembra che il tuo problema sia nel comprendere la definizione di "altezza del sotto albero DX/SX"? Come la definisci?
da me la foto si vede sia da chrome che da FF O.o
comunque l'altezza di un sottoalbero sono i numeri di nodi che si incontrano dalla radice (esclusa) alla foglia più lontana...giusto??
comunque l'altezza di un sottoalbero sono i numeri di nodi che si incontrano dalla radice (esclusa) alla foglia più lontana...giusto??
Adesso la vedo anche io.. Probabilmente non si era caricata per qualche ragione l'immagine. Sì, come definizione immagino possa andare. Che cosa intendi con "siccome .. sono a zero"? Intendi dire che FdB = 0 o che l'altezza è uguale a zero?
Prendiamo il nodo 23 sul quale sei in dubbio come esempio. Seguendo la definizione hai che a sinistra hai un albero con un solo elemento (di altezza 0 quindi) e a destra un albero vuoto (di altezza quindi -1). Il risultato dovrebbe quindi essere FdB = 1 (non -1) seguendo la tua definizione (ma l'idea non cambia). Per il nodo 54 il discorso è analogo ma si scambiano i valori dei due rami.
In 72 hai due sottoalberi non vuoti. Quello sinistro ha altezza 1 (ha infatti due nodi disposti uno sopra l'altro) e quello destro ha un solo elemento e quindi altezza 0. Quindi, FdB = 1 - 0 = 1.
In 50 ci sono nuovamente due sottoalberi non vuoti, entrambi di altezza 2 per cui FdB = 0.
Prendiamo il nodo 23 sul quale sei in dubbio come esempio. Seguendo la definizione hai che a sinistra hai un albero con un solo elemento (di altezza 0 quindi) e a destra un albero vuoto (di altezza quindi -1). Il risultato dovrebbe quindi essere FdB = 1 (non -1) seguendo la tua definizione (ma l'idea non cambia). Per il nodo 54 il discorso è analogo ma si scambiano i valori dei due rami.
In 72 hai due sottoalberi non vuoti. Quello sinistro ha altezza 1 (ha infatti due nodi disposti uno sopra l'altro) e quello destro ha un solo elemento e quindi altezza 0. Quindi, FdB = 1 - 0 = 1.
In 50 ci sono nuovamente due sottoalberi non vuoti, entrambi di altezza 2 per cui FdB = 0.
La mia prof aveva detto "i due sottoalberi hanno altezza zero per cui il suo fattore e' zero"...ma questa è una regola oppure è perchè 1 - 1 = 0? (nel caso 9 -12 -14)??
E poi perchè 72 a SX ha altezza 1?? Se la radice del sottoalbero è 72 poi incontro 2 nodi ovvero 54 e 67 quindi sarà 2 no?? aiuto xD
E poi perchè 72 a SX ha altezza 1?? Se la radice del sottoalbero è 72 poi incontro 2 nodi ovvero 54 e 67 quindi sarà 2 no?? aiuto xD
Ma i sottoalberi destro e sinistro non hanno come radice il nodo di partenza ma i nodi figli del nodo.. Per il primo discorso è perché la differenza di due numeri uguali è 0.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo