Análisis y Diseño de Algoritmos                                                                                                      

Prof: Ing. Victor Garro

Asistente: Marco Elizondo Vargas

 

Árboles

 

árbol Binario

 

Árboles binarios

Ø Definición.

Estructura tipo Árbol de grado dos:

Bien una estructura vacía o bien un elemento del tipo base y como máximo 2 estructuras de tipo árbol.

Figura - 4 Árbol binario

Árbol binario de Búsqueda

Elementos Menores à subárbol izquierdo

Elementos Mayores à subárbol derecho

 

Figura - 5.
Árbol binario de búsqueda

 

ALGORITMOS FUNDAMENTALES

 

Procedimiento de inserción en un árbol Binario de Búsqueda.

 

à Todas las inserciones de realizan en Nodos Hoja.

 

 

 

Ø CODIFICACIÓN

INSERCIÓN SIN CLAVES REPETIDAS

 

Pasos:

- Recorrer el árbol buscando la clave a insertar:

o     Si no está à Se inserta

o     Si está à Mensaje de error

Procedure Insertar ( var a: TArbol; Elem: TClave );

begin

if a = nil then (* búsqueda de la posición adecuada *)

begin

new ( a );

a^.Clave := Elem;

a^.Izq := nil;

a^.Der := nil

end

if a^.Clave > Elem (* búsqueda en el subárbol izq. *)

then Insertar ( a^.Izq, Elem )

else if a^.Clave < Elem (* búsqueda en el subárbol der. *)

then Insertar ( a^.Der, Elem )

end;

 

INSERCIÓN CON CLAVES REPETIDAS

 

Pasos:

- Recorrer el árbol buscando la clave a insertar:

o     Insertar la clave.

 

Procedure Insertar ( var a: TArbol; Elem: TClave );

begin

if a= nil then (* búsqueda de la posición adecuada *)

begin

new ( a );

a^.Clave := Elem;

a^.Izq := nil;

a^.Der := nil

end

else

if a^.Clave >= Elem then (* inserción *)

Insertar ( a^.Izq, Elem )

end;

 

Procedimiento de borrado en un árbol binario de Búsqueda.

 

CASOS	ACCIONES
La clave no está	Ninguna o mensaje de notificación
La clave está	Es un nodo hoja (a := NIL) Es un nodo interno (a^.Der , a^.Izq <> NIL) Buscar la clave mayor de las menores ó Buscar la clave menor de las mayores. Se cambia con la clave a borrar y se elimina la clave cambiada.
Nodo con 1 sólo descendiente	a:= a^.Izq a:= a^.Der ( ver Figura - 6 )

 

Figura - 6. Borrado en nodo con un sólo descendiente

Procedure Borrar ( var a: TArbol; Elem: TClave );

var Aux: TArbol;

Procedure MayorMenores ( var b: TArbol );

begin

if b^.Der = nil then

begin

Aux^.Clave := b^.Clave;

Aux := b;

b := b^.Izq

end

else

MayorMenores( b^.Der )

end;

begin (* Borrar *)

if a = nil then

writeln ( 'la clave no está' )

else

if a^.Clave > Clave then (* búsqueda de la clave *)

Borrar ( a^.Izq, Clave )

else

if a^.Clave < Clave then (* búsqueda de la clave *)

Borrar ( a^.Der, Clave )

else begin (* 2 *)

Aux := a;

if a^.Izq = nil then

a := a^.Der

else

if a^.Der = nil then

a := a^.Izq

else MayorMenores( a^.Izq );

dispose ( Aux )

end (* 2 *)

end; (* Borrar *)