-- AUTOR: Elvira Mayordomo Cámara
-- PROYECTO: módulo de implementación del
-- TAD arboles binarios de búsqueda
-- FICHERO: abb.adb
-- FECHA: 14-11-03

with unchecked_deallocation;
with text_io;
use text_io;

package body abb 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 insertar(a:in out arbin; e:in
elemento) is
-- Pre: a=a0; padre es el padre de a
-- Post: a=insertar(a0,e)
-- coste en tiempo: para un árbol de n nodos tarda O(n)
begin
	if a=null then 
		a:=new nodo'(e,null,null);
	elsif (e<=a.dato) then
		insertar(a.izq,e);
	else insertar(a.der,e);
	end if;
end insertar;

function esta(a:arbin; e:elemento) return
boolean is
-- Post: esta(a,e)= está?(a,e)
-- coste en tiempo: para un árbol de n nodos tarda O(n)
resultado: boolean;
begin
	resultado:=false;
	if a/=null then 
		if (a.dato = e) then resultado:=true;
		elsif (e<=a.dato) then
		resultado:=esta(a.izq,e);
		else resultado:=esta(a.der,e);
		end if;
	end if;
	return resultado;	
end esta;

function min(a:arbin) return elemento is
-- Pre: not(esvacío(a))
-- Post: min(a)= min(a)
-- coste en tiempo: para un árbol de n nodos tarda O(n)
begin
	if a.izq=null then return a.dato;
	else return min(a.izq);
	end if;
end min;

function max(a:arbin) return elemento is
-- Pre: not(esvacío(a))
-- Post: max(a)= max(a)
-- coste en tiempo: para un árbol de n nodos tarda O(n)
begin
	if a.der=null then return a.dato;
	else return max(a.der);
	end if;
end max;

procedure borrar(a:in out arbin; e:in
elemento) is
-- Pre: a=a0
-- Post: a=borrar(a0,e)
-- coste en tiempo: para un árbol de n nodos tarda O(n)
aux:arbin; 
nuevaraiz:elemento;
begin
	if a/=null then 
		if (a.dato = e) then 
			if a.der=null and a.izq=null then
				aux:=a;
				a:=null;
				disponer(aux);
			elsif a.izq/=null then
				nuevaraiz:=max(a.izq);
				a.dato:=nuevaraiz;
				borrar(a.izq,nuevaraiz);
			else
				nuevaraiz:=min(a.der);
				a.dato:=nuevaraiz;
				borrar(a.der,nuevaraiz);	
			end if;
		elsif (e<=a.dato) then
			borrar(a.izq,e);
		else borrar(a.der,e);
		end if;
	end if;
end borrar;

procedure preOrden(a:in arbin) is
-- muestra por pantalla el preorden de a
-- coste en tiempo: para un árbol de n nodos tarda O(n)
begin 
	if a/=null then
		put(a.dato);
		preOrden(a.izq);
 		preOrden(a.der);
 	end if;
end preOrden;

procedure postOrden(a:in arbin) is
-- muestra por pantalla el preorden de a
-- coste en tiempo: para un árbol de n nodos tarda O(n)
begin 
	if a/=null then
		postOrden(a.izq);
 		postOrden(a.der);
		put(a.dato);
 	end if;
end postOrden;

procedure mostrar(a:in arbin) is
-- Muestra por pantalla preorden y postorden
-- coste en tiempo: para un árbol de n nodos tarda O(n)
begin
	put_line("El preorden es:");
	preOrden(a);
	put_line("");
	put_line("El postorden es:");
	postOrden(a);
	put_line("");
end mostrar;	

end abb;