INSERZIONE DI UN ELEMENTO e IN UN 2-3 ALBERO

Terminologia per un nodo X: 	
	f(X) = padre di X
	k(X) = contenuto di X (una o due chiavi)
	l(X), m(X), r(X) = puntatore sinistro, mediano (se definito), destro 

Nota: le chiavi sono contenute anche nelle foglie, per le quali 
l(X)=m(x)=r(X)=NIL (cioe' l'albero non comprende un ultimo livello di 
foglie vuote).


procedure INSERT(e,T)  // inserzione di e in un 2-3 albero T non vuoto //
	discendi in T cercando la posizione di e, fino a raggiungere 
		una foglia X
	INSERT_LEAF(e,X).


procedure INSERT_LEAF(e,X)  // inserzione di e in una foglia X //	
	if k(X)=[u] then 
		if e<u then k(X):=[e,u] else k(X):=[u,e]
		m(X):=NIL // l(X) e r(X) invariati //
	if k(X)=[u,v] then
		sia [a,b,c] la tripla ordinata e,u,v
		sia F=f(X)
		elimina nodo X
		crea nodo Y con k(Y):=a, l(Y):=NIL, r(Y):=NIL
		crea nodo Z con k(Z):=c, l(Z):=NIL, r(Z):=NIL 
		if F=NIL then CREA_ROOT(b,Y,Z) else INSERT_INT(b,F,Y,Z).


procedure INSERT_INT(e,X,A,B)  // inserzione di e in un nodo interno X 
				 provenendo da un figlio di X //
	if k(X)=[u] then 
		if e<u 	then k(X):=[e,u], l(X):=A, m(X):=B
			else k(X):=[u,e], m(X):=A, r(X):=B
	if k(X)=[u,v] then
		sia [a,b,c] la tripla ordinata e,u,v
		sia sia F=f(X), L=l(X), M=m(X), R=r(X)
		elimina nodo X
		crea nodo Y con k(Y):=a
		crea nodo Z con k(Z):=c
		if e=a // e viene dal figlio sinistro //
			then l(Y):=A, r(Y):=B, l(Z):=M, r(Z):=R
		if e=b // e viene dal figlio centrale //
			then l(Y):=L, r(Y):=A, l(Z):=B, r(Z):=R 
		if e=c // e viene dal figlio destro //
			then l(Y):=L, r(Y):=M, l(Z):=A, r(Z):=B 	
		if F=NIL then CREA_ROOT(b,Y,Z) else INSERT_INT(b,F,Y,Z).


procedure CREA_ROOT(e,A,B)  // inserzione di e in una nuova radice //
	crea nodo Y con k(Y):=e, l(Y):=A, r(Y):=B.