Un albero 2-3-4 è un albero in cui:

• ogni nodo contiene almeno un valore e al massimo 3
• ogni nodo interno con i valori ha i+1 figli
• tutte le foglie sono sullo stesso livello
• è ordinato (i+1 intervalli associati a i+1 sottoalberi)

Lemma

Sia n il numero di dati in un albero 2-3-4 di altezza h. Si ha allora

$$ 2^{h+1}-1 \leq n \leq 4^{h+1}-1 $$

Dimostrazione (per induzione su h):

• (h=0) Segue immediatamente dalla definizione

$$ 2^1-1\leq n\leq 4^1-1=3 $$

• (h > 1) L'albero 2-3-4 con meno valori ha una radice con un solo valore e 2 sottoalberi (di altezza h-1) $T_1$ e $T_2$. Per ipotesi induttiva vale:

  $$ n\geq 1 +N_{dati}(T_1)+N_{dati}(T_2)\geq 1 +2^h-1+2^h -1=2^{h+1}-1 $$

  L'albero 2-3-4 con più valori ha una radice con tre valori e 4 sottoalberi (di altezza h-1) $T_1, T_2, T_3, T_4.$ Per ipotesi induttiva vale:

  $$ n\leq3 +N_{dati}(T_1)+N_{dati}(T_2)+N_{dati}(T_3)+N_{dati}(T_4)\leq 3+4(4^h-1)=4^{h+1}-1 $$

Proprietà

Dal precedente lemma deriva che un albero 2-3-4 con n dati ha altezza $O(\log n)$

Gli alberi 2-3-4 sono quindi bilanciati

Inserimento

L'operazione di inserimento di x in T avviene inserendo x in una foglia di T (individuata attraverso una serie di confronti a partire dalla radice)