-- 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;