Albero 2-3

Dimostrazione

Le due proprietà possono essere dimostrate per induzione sull'altezza ${\displaystyle h}$ dell'albero.

Caso base (${\displaystyle h=0}$): per ${\displaystyle h=0}$ si ha ${\displaystyle 2^{0}=1\leq f\leq 3^{0}=1}$ e in effetti l'albero ha solo una foglia, cioè la radice. Allo stesso modo verifichiamo che ${\displaystyle 2^{1}-1=1\leq n\leq (3^{1}-1)/2=1}$, infatti si ha un solo nodo.

Passo induttivo: Supponiamo che le due disuguaglianze valgano per un albero 2-3 di altezza ${\displaystyle h}$. Consideriamo un albero 2-3 ${\displaystyle T}$ con altezza ${\displaystyle h+1}$ e ${\displaystyle T'}$ di altezza ${\displaystyle h}$, ottenuto a partire da ${\displaystyle T}$ eliminandone l'ultimo livello. Siano ${\displaystyle n'}$ il numero di nodi e ${\displaystyle f'}$ il numero di foglie dell'albero ${\displaystyle T'}$. Per ipotesi induttiva si ha:

${\displaystyle 2^{h+1}-1\leq n'\leq {\frac {3^{h+1}-1}{2}}}$ e ${\displaystyle 2^{h}\leq f'\leq 3^{h}}$

Poiché ogni foglia di ${\displaystyle T'}$ ha almeno 2 o al più 3 figli in ${\displaystyle T}$ si avrà:

${\displaystyle 2\cdot 2^{h}\leq f\leq 3\cdot 3^{h}\Longrightarrow 2^{h+1}\leq f\leq 3^{h+1}}$

Per il numero totale di nodi, osserviamo che ${\displaystyle n=n'+f}$. Utilizzando le disuguaglianze ottenute:

Limite inferiore per n: ${\displaystyle n=n'+f\geq (2^{h+1}-1)+2^{h+1}=2\cdot 2^{h+1}-1=2^{h+2}-1}$

Limite superiore per n: ${\displaystyle n=n'+f\leq {\frac {3^{h+1}-1}{2}}+3^{h+1}={\frac {3^{h+1}-1+2\cdot 3^{h+1}}{2}}={\frac {3\cdot 3^{h+1}-1}{2}}={\frac {3^{h+2}-1}{2}}}$

Quindi si ottiene ${\displaystyle 2^{h+2}-1\leq n\leq {\frac {3^{h+2}-1}{2}}}$, che è esattamente ciò che volevamo dimostrare per l'altezza ${\displaystyle h+1}$.