• Ogni nodo interno ha 2 o 3 figli: $F_1, F_2, F_3$
• Ogni nodo interno ha 2 etichette: $L(v)=MAX(F_1(v)), M(v)=MAX(F_2(v))$
• Gli elementi inseriti risiedono solo sulle foglie
• Tutte le foglie hanno la stessa profondità
• E' ordinato. → per ogni nodo con etichette L e M, il primo sottoalbero contiene esclusivamente valori ≤ L, il secondo sottoalbero valori >L e ≤ M, il terzo (se esiste) valori > M

Proprietà

Lemma: si n il numero di dati in un albero 2-3 di altezza h. Si ha allora

$$ 2^h \leq n \leq 3^h $$

Dimostrazione (per induzione su h)

• $(h=1)$: immediato dalla definizione di albero 2-3

• $(h>1)$: la radice ha albemo 2 sottoalberi (di altezza h-1) $T_1 \ e \ T_2$.

  Per ipotesi insuttiva vale $n\geq N_{dati}(T_1)+N_{dati}(T_2)\geq2^{h-1}+2^{h-1}=2^h$

  La radice ha al massimo 3 sottoalberi (di altezza h-1) $T_1, T_2 \ e \ T_3$.

  Per ipotesi induttiva vale: $n\leq N_{dati}(T_1)+N_{dati}(T_2)+N_{dati}(T_3)\leq 3^{h-1}+3^{h-1}+3^{h-1}=3^h$

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

Gli alberi 2-3 sono quindi bilanciati

F famiglia di alberi bilanciati

→ T appartiene a F, T ha n nodi → $H(T)=O(\log n)$

Inserimento

Discendo nell'albero fino al nodo che dovrà ospitare il nuovo elemento

1. Il nodo ha 2 figli: inserisco l'elemento come 3 figlio e aggiorno le etichette (quest'ultima operazione può propagarsi fino alla radice)

   

2. Divido il nodo in 2 nodi da due figli ciascuno e li collego al padre, su cui la procedura viene iterata ricorsivamente. Se il nodo è radice l'altezza dell'albero aumenta

   

Cancellazione