-- AUTOR: Elvira Mayordomo Cámara
-- PROYECTO: módulo de implementación del TAD arboles binarios
-- FICHERO: arbolesbin.adb
-- FECHA: 22-10-02, basado en el libro de Javier Campos (ver bibliografía)

with unchecked_deallocation;
package body arbolesbin is

procedure disponer is new unchecked_deallocation(nodo,arbin);

procedure creaVacio(a:out arbin) is
-- Post: a=aVacío
-- coste en tiempo O(1)
begin
a:=null;
end creaVacio;

procedure enraiza(e: in elemento; ai,ad:in arbin; a:out arbin) is
-- Post: a=enraizar(e,ai,ad)
-- NO COPIA ai NI ad
-- coste en tiempo O(1)
begin
a:=new nodo'(e,ai,ad,0);
if ai/=null and ad/=null then
a.altura:=1+integer'Max(ai.altura,ad.altura);
elsif ai/=null then
a.altura:=1+ai.altura;
elsif ad/=null then
		a.altura:=1+ad.altura;
end if;
end enraiza;

function raiz(a:arbin) return elemento is 
-- Pre: not(esvacío(a))
-- Post: raiz(a)=raíz(a)
-- coste en tiempo O(1)
begin
return(a.dato);
end raiz;

procedure subIzq(a:in arbin; ai:out arbin) is
-- Pre: not(esvacío(a))
-- Post: ai=subIzq(a)
-- ATENCION: NO DUPLICA ai
-- coste en tiempo O(1)
begin
ai:= a.izq;
end subIzq;

procedure subDer(a:in arbin; ad:out arbin) is
-- Pre: not(esvacío(a))
-- Post: ad=subDer(a)
-- ATENCION: NO DUPLICA ad
-- coste en tiempo O(1)
begin
ad:= a.der;
end subDer;

function esVacio(a:arbin) return boolean is
-- Post: esVacio(a)=esvacío(a)
-- coste en tiempo O(1)
begin
return(a=null);
end esVacio;

function altura(a:arbin) return integer is
-- Post: altura(a)=altura(a)
-- coste en tiempo O(1)
begin
if esVacio(a) then
	return -1;
else
return(a.altura);
end if;
end altura;

procedure asignar(nuevo:out arbin; viejo:in arbin) is
-- Duplica la representación del árbol viejo 
-- guardándolo en nuevo.
-- coste en tiempo: para un árbol de n nodos tarda O(n)
ai,ad:arbin;
begin
if viejo=null 
then
nuevo:=null;
else
asignar(ai,viejo.izq);
asignar(ad,viejo.der);
nuevo:=new nodo'(viejo.dato,ai,ad,viejo.altura);
end if;
end asignar;

procedure liberar(a:in out arbin) is
--  Libera la memoria dinámica accesible desde a, 
-- quedando a vacío.
-- coste en tiempo: para un árbol de n nodos tarda O(n)
begin
if a/=null then
liberar(a.izq);
liberar(a.der);
disponer(a);
a:=null;
end if;
end liberar;

end arbolesbin;