L'albero della divisione per $2$
Propongo qui un problema a cui sto pensando da alcuni giorni.
Fissiamo un naturale $n > 1$ e associamo a $n$ un albero binario così definito:
- la radice è $n$.
- un nodo, etichettato con $k$, ha un solo figlio se $k$ è pari, e questo figlio si chiama $k/2$, e due figli se $k$ è dispari, indicati con $(k+1)/2$ e $(k-1)/2$.
- un nodo non ha figli se è etichettato con $1$.
Evidentemente tutte le foglie dell'albero sono etichettate con $1$. Mi piacerebbe riuscire a dire se, avendo $n$, è possibile determinare esattamente l'altezza dell'albero senza dover fare tutto il procedimento.
Metto in spoiler qualche osservazione che ho già fatto:
Fissiamo un naturale $n > 1$ e associamo a $n$ un albero binario così definito:
- la radice è $n$.
- un nodo, etichettato con $k$, ha un solo figlio se $k$ è pari, e questo figlio si chiama $k/2$, e due figli se $k$ è dispari, indicati con $(k+1)/2$ e $(k-1)/2$.
- un nodo non ha figli se è etichettato con $1$.
Evidentemente tutte le foglie dell'albero sono etichettate con $1$. Mi piacerebbe riuscire a dire se, avendo $n$, è possibile determinare esattamente l'altezza dell'albero senza dover fare tutto il procedimento.
Metto in spoiler qualche osservazione che ho già fatto:
Risposte
Ciao,
non vedo nulla di complicato per definire la profondità di un albero binario non queste proprietà, anzi cambia minimamente. Se vorresti calcolarne il numero di nodi c'è un minimo di lavoro da fare ma in questo caso no.
Comuque ti faccio alcune osservazioni.
Si può riscrivere la tua definizione come:
$\text{child}_p.k = {(\text{null} if p.k=1),( (p.k)/2 if n>1\ is\ even),(\lfloor (p.k)/2\rfloor ^^ \lceil (p.k)/2 \rceil if n>1\ is\ odd):}$
con $p=\text{parent}$ e $k=\text{key}$
se $p.k$ dispari (left e right a piacere): $\text{child}_p|\text{left}.k + \text{child}_p|\text{right}.k = \lfloor (p.k)/2\rfloor + \lceil (p.k)/2 \rceil = p.k$
se $p.k$ pari, il cammino nodo-foglia è equivalente se esistono due nodi identici o meno, perciò possiamo semplicare tutto e dire che abbiamo due figli con chiave $k/2$:
$\text{child}_p|\text{left}.k + \text{child}_p|\text{right}.k = (p.k)/2 + ((p.k)/2) = p.k$
non vedo nulla di complicato per definire la profondità di un albero binario non queste proprietà, anzi cambia minimamente. Se vorresti calcolarne il numero di nodi c'è un minimo di lavoro da fare ma in questo caso no.
Comuque ti faccio alcune osservazioni.
Si può riscrivere la tua definizione come:
$\text{child}_p.k = {(\text{null} if p.k=1),( (p.k)/2 if n>1\ is\ even),(\lfloor (p.k)/2\rfloor ^^ \lceil (p.k)/2 \rceil if n>1\ is\ odd):}$
con $p=\text{parent}$ e $k=\text{key}$
se $p.k$ dispari (left e right a piacere): $\text{child}_p|\text{left}.k + \text{child}_p|\text{right}.k = \lfloor (p.k)/2\rfloor + \lceil (p.k)/2 \rceil = p.k$
se $p.k$ pari, il cammino nodo-foglia è equivalente se esistono due nodi identici o meno, perciò possiamo semplicare tutto e dire che abbiamo due figli con chiave $k/2$:
$\text{child}_p|\text{left}.k + \text{child}_p|\text{right}.k = (p.k)/2 + ((p.k)/2) = p.k$
Secondo me è ancora più facile, ed è sempre che l'altezza è il logarimo in base 2 di n, arrotondato per eccesso quando non è un numero naturale.
Fondamentalmente quello che mi viene in mente è che non è un discorso molto diverso da quello che si fa quando cerchiamo di rappresentare un numero in forma binaria, e vogliamo calcolare quanti bit servono.
Unica diversità è che lo 0 non lo rappresentiamo, quindi risparmiamo un valore e, dati h bit, rappresentiamo numeri da 1 a $2^{h}$.
per esempio, con n=19 abbiamo altezza h=5 (infatti rappresentiamo numeri da 1 a 32. 4 non basta perché rappresenteremmo numeri da 1 a 16).
Ora penso e formulo qualcosa di più matematico e preciso eh!
EDIT: Corretti un paio di errori
Fondamentalmente quello che mi viene in mente è che non è un discorso molto diverso da quello che si fa quando cerchiamo di rappresentare un numero in forma binaria, e vogliamo calcolare quanti bit servono.
Unica diversità è che lo 0 non lo rappresentiamo, quindi risparmiamo un valore e, dati h bit, rappresentiamo numeri da 1 a $2^{h}$.
per esempio, con n=19 abbiamo altezza h=5 (infatti rappresentiamo numeri da 1 a 32. 4 non basta perché rappresenteremmo numeri da 1 a 16).
Ora penso e formulo qualcosa di più matematico e preciso eh!
EDIT: Corretti un paio di errori
"canemacchina":
Secondo me è ancora più facile, ed è sempre che l'altezza è il logarimo in base 2 di n, arrotondato per eccesso quando non è un numero naturale.
infatti è quello che volevo far comprendere a Pappappero, cioè che i "buchi" creati da un figlio pari non cambia la proprietà. Esiste una differenza ma vediamo se Pappappero la intuisce
Ok, allora colpa mia che ho letto frettolosamente la tua risposta e ho pensato che fosse più complicata di quanto non sia! 
"canemacchina":
Ok, allora colpa mia che ho letto frettolosamente la tua risposta e ho pensato che fosse più complicata di quanto non sia!
sì in effetti lo ho espresso in modo un po' complicato. Prima avevo in mente un altro metodo di dimostrazione, applicando la somma che ho messo
mmm...in effetti l'avevo presa molto più larga di quello che sembra.
Con questi suggerimenti sono in effetti riuscito a dimostrare, anche se non proprio rigorosamente, che l'altezza dell'albero è proprio $t$, definito come la parte intera superiore di $log_2 (n)$.
Prendo infatti l'albero di $2^t$ e lo metto accanto a quello di $n$. Le etichette dell'albero di $n$ hanno sempre numero più basso di quella allo stesso livello dell'albero di $2^t$. Quindi l'altezza è al più $t$.
Prendo poi l'albero di $2^{t-1}$. In questo caso ad ogni livello trovo almeno un'etichetta dell'albero di $n$ che ha numero maggiore stretto dell'etichetta allo stesso livello dell'albero di $2^{t-1}$. Quindi quando $2^{t-1}$ arriva a $1$ dall'altra parte non ho ancora finito. Perciò l'altezza è almeno $t$.
Formalizzando il tutto, dovrebbe tornare...
Con questi suggerimenti sono in effetti riuscito a dimostrare, anche se non proprio rigorosamente, che l'altezza dell'albero è proprio $t$, definito come la parte intera superiore di $log_2 (n)$.
Prendo infatti l'albero di $2^t$ e lo metto accanto a quello di $n$. Le etichette dell'albero di $n$ hanno sempre numero più basso di quella allo stesso livello dell'albero di $2^t$. Quindi l'altezza è al più $t$.
Prendo poi l'albero di $2^{t-1}$. In questo caso ad ogni livello trovo almeno un'etichetta dell'albero di $n$ che ha numero maggiore stretto dell'etichetta allo stesso livello dell'albero di $2^{t-1}$. Quindi quando $2^{t-1}$ arriva a $1$ dall'altra parte non ho ancora finito. Perciò l'altezza è almeno $t$.
Formalizzando il tutto, dovrebbe tornare...
"Pappappero":
definito come la parte intera superiore di $log_2 (n)$.
perchè parli di parte intera superiore?
Visto che quello che cerchi è la profondità, io direi che è più corretto dire parte intera inferiore (floor): $\lfloor log_2(n) \rfloor$
Il numero di livelli invece è: $\lfloor log_2(n) \rfloor + 1$
Circa è la stessa cosa, se si parla di altezza, ma è meglio separare i concetti
Per l'int alla dimostrazione mi pare che può andare
Ti propongo due quesiti, così da "pensare":
qual è la differenza tra la definizione di "profondità" di un albero binario classico e quella in questo caso?
Se sai rispondere, sapresti trovare il numero di nodi dell'albero binario che hai definito?
Non ho mai studiato sul serio teoria dei grafi o comunque qualcosa che mi abbia portato a studiare con attenzione gli alberi. Da quel che ho visto però mi pare di aver capito che la profondità è un concetto legato ai singoli nodi, mentre quando si prende l'intero albero si parla di altezza (questo è quello che ho capito da una rapida occhiata su wiki...).
Quindi direi proprio che l'altezza del mio albero (definita come la massima lunghezza dalla radice a una delle foglie) che dovrebbe coincidere con il numero dei livelli meno $1$, direi che è proprio il $ceil(log_2 n)$, dove ceil è la parte intera superiore. Giusto per intendersi, se l'albero ha un solo nodo, allora quel nodo è etichettato con $1$; quell'albero ha altezza $0$, che è proprio il ceil di $0=log_2 1$. Se la radice è $3$ l'albero ha altezza $2$, che è il ceil di $log_2 3$.
Se poi sto usando impropriamente il termine altezza e quella che io chiamo altezza in realtà si chiama profondità, allora sono perfettamente d'accordo con te.
Quindi direi proprio che l'altezza del mio albero (definita come la massima lunghezza dalla radice a una delle foglie) che dovrebbe coincidere con il numero dei livelli meno $1$, direi che è proprio il $ceil(log_2 n)$, dove ceil è la parte intera superiore. Giusto per intendersi, se l'albero ha un solo nodo, allora quel nodo è etichettato con $1$; quell'albero ha altezza $0$, che è proprio il ceil di $0=log_2 1$. Se la radice è $3$ l'albero ha altezza $2$, che è il ceil di $log_2 3$.
Se poi sto usando impropriamente il termine altezza e quella che io chiamo altezza in realtà si chiama profondità, allora sono perfettamente d'accordo con te.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo