AlgoritmicaII-Arbol Binario de Busqueda

Árbol Binario de Búsqueda

Algorítmica y Programación II

Alg

orítm

ica

y P

rogr

amac

ión

II

Nivel lógico

¿Qué es un árbol?

Las imágenes representan distintos objetos perocada uno ilustra un concepto común: un árbol.

Un árbol es una estructura de datos en formajerárquica o de niveles, en cuyos elementospuede existir una relación de uno a muchos (1:n).

2

Alg

orítm

ica

y P

rogr

amac

ión

II

Nodo raíz: primer elemento de un árbol. Notiene ascendiente.

Nodo padre: nodo que tiene por lo menos unhijo.

Hijo: descendiente de un nodo. Nodo hoja: nodo que no tiene descendiente. Nodos hermanos: nodos con un mismo

padre. Rama: relación que conecta un padre con un

hijo.

Terminología básica

3

Alg

orítm

ica

y P

rogr

amac

ión

II

Ancestro: nodo padre de un nodo o padre dealgún nodo ancestro.

Descendiente: hijo de un nodo o hijo de otrodescendiente de ese nodo.

Subárbol: conjunto de descendientes de unnodo por una de las ramas.

Nivel de un nodo: distancia desde la raíz.Esta es el nivel cero.

Grado de un nodo: número de hijos quetiene.

Terminología básica

4

Alg

orítm

ica

y P

rogr

amac

ión

II

Nodo raíz

Nodos hoja

Subárbol

5

Nivel 0

Nivel 2

Alg

orítm

ica

y P

rogr

amac

ión

II

6

o Hijo izquierdo de nodo raíz: nodo que contiene 3.

o Nodo padre de nodos que contienen 1 y 6: nodo que contiene 3.

o Nodos hoja: nodos que contienen 1, 4, 7 y 13.

o Nodos hermanos: nodos que contienen (1 y 6), (4 y 7), (3 y 10).

o Ancestros de nodo que contiene 14: nodos que contienen 10 y 8.

o Descendientes de nodo que contiene 3: nodos que contienen 1, 6, 4 y 7.

o Subárbol derecho de nodo raíz: tiene como raíz al nodo que contiene 10.

Alg

orítm

ica

y P

rogr

amac

ión

II

Árbol – Árbol binario

Árbol general: aquel en el que no seconsidera ninguna limitación en el gradomáximo de sus nodos. Los árboles n-ariosson aquellos en los que el grado máximo desus nodos es n, siendo n un número positivo.

Árbol binario: aquel en que cada nodo tienecomo máximo dos hijos.

7

Alg

orítm

ica

y P

rogr

amac

ión

II

Árbol Binario de Búsqueda

Estructura de datos que guarda información norepetida, en el que cada nodo apunta como máximoa dos nodos y además cumple con un ordenamientode modo que para cada elemento del ABB, loselementos menores están a su izquierda (subárbolizquierdo) y los mayores a su derecha (subárbolderecho).

8

Alg

orítm

ica

y P

rogr

amac

ión

II¿Qué operaciones senecesitan?

Crear Insertar Suprimir Vacío Buscar Limpiar

9

Alg

orítm

ica

y P

rogr

amac

ión

II

Especificación del TAD ABB

Función de acceso: la ubicación de cada elementoen el árbol satisface la siguiente regla: el valor de laclave de un elemento es mayor que el valor de laclave de cualquier elemento en su subárbolizquierdo y menor que el valor de la clave decualquier elemento en su subárbol derecho.

Crear(Arbol)Función: Inicializar Arbol al estado vacío.Entrada: Ninguna.Precondiciones: Ninguna.Salida: Arbol.Poscondiciones: Arbol está vacío.

10

Alg

orítm

ica

y P

rogr

amac

ión

II


Vacio(Arbol)

Función: Indicar si Arbol está vacío.

Entrada: Arbol a ser testeado.

Precondiciones: Arbol existe.

Salida: Vacio (valor booleano).

Poscondiciones: Vacio = (el árbol está vacío).

11

Alg

orítm

ica

y P

rogr

amac

ión

II

Suprimir(Arbol, ValSup)Función: Quitar de Arbol el elemento

especificado.Entrada: Arbol, ValSup.Precondiciones: Arbol existe, ValSup pertenece a

la Arbol.Salida: Arbol (cambiado)Poscondiciones: Arbol = Arbol original sin ValSup.Excepciones: Plantea ArbolVacio si ValSup no

pertenece a Arbol. El árbol no semodifica.


12

Alg

orítm

ica

y P

rogr

amac

ión

II


Insertar(Arbol, NuevoElemento)

Función: Añadir NuevoElemento a Arbol.

Entrada: Arbol, NuevoElemento.


Salida: Arbol (cambiado).

Poscondiciones: Arbol = Arbol original +NuevoElemento.

13

Alg

orítm

ica

y P

rogr

amac

ión

II


Esta(Arbol,Valor)

Función: Indicar si Valor pertenece a Arbol.

Entrada: Arbol, Valor.


Salida: Esta (valor booleano)

Poscondiciones: Esta = (Valor pertenece a Arbol)

14

Alg

orítm

ica

y P

rogr

amac

ión

II

Limpiar(Arbol)

Función: Liberar los nodos que pudieranexistir en Arbol.

Entrada: Arbol a vaciar.

Precondiciones: Arbol existe

Salida: Arbol (vacío)

Poscondiciones: Arbol está vacío.


15

Alg

orítm

ica

y P

rogr

amac

ión

II


Buscar(Arbol, clave, infoNodo, encontrado)

Función: Buscar el nodo clave y devolver los datos asociados. Devuelve falso si no pertenece.

Entrada: Arbol y clave.

Precondiciones: Arbol no es vacío

Salida: infoNodo, encontrado

Poscondiciones:infoNodo = datos del nodo quecontiene clave si está en el árbol;en ese caso encontrado esverdadero, en caso contrario esfalso. 16

Alg

orítm

ica

y P

rogr

amac

ión

II

TAD ABB

type TipoNodo;type TipoArbol is access TipoNodo;type TipoNodo isrecord

Info: TipoElem;Izq, Der: TipoArbol;

end record;

17

Puntero a la raíz del subárbol derecho

Puntero a la raíz del subárbol izquierdo

Info

TipoNodo

Alg

orítm

ica

y P

rogr

amac

ión

II

18

generictype TipoElem is private;with function "<" (X, Y: TipoElem) return Boolean;with function ">" (X, Y: TipoElem) return Boolean;with procedure Put (X: in TipoElem);package Arbol is

type TipoArbol is private;-- procedure Crear (Raiz: out TipoArbol); -- no es necesario

function Vacio (Raiz: TipoArbol) return Boolean; procedure Insertar (Raiz: in out TipoArbol; Elemento: in TipoElem);procedure Suprimir (Raiz: in out TipoArbol; ValSup: in TipoElem); function Esta (Raiz: in TipoArbol; Buscado: in TipoElem) return Boolean;procedure Limpiar (Ptr: in out TipoArbol);function Izq (Ptr: TipoArbol) return TipoArbol; function Der (Ptr: TipoArbol) return TipoArbol; function Info (Ptr: TipoArbol) return TipoElem; ArbolVacio: exception;

Alg

orítm

ica

y P

rogr

amac

ión

II

19

with Ada.Unchecked_Deallocation; package body Arbol isprocedure Free is new Ada.Unchecked_Deallocation(TipoNodo, TipoArbol);

function Vacio (Raiz: TipoArbol) return Boolean is begin

return Raiz = null;end Vacio;

procedure Limpiar (Ptr: in out TipoArbol) isbegin

if not Vacio (Ptr) thenLimpiar (Ptr.Izq); Limpiar (Ptr.Der);Free (Ptr);

end if;end Limpiar;

Alg

orítm

ica

y P

rogr

amac

ión

II

20

[Dale 2003]

Operación Insertar

Alg

orítm

ica

y P

rogr

amac

ión

II

21

procedure Insertar (Raiz: in out TipoArbol; Elemento: in TipoElem) isNuevoNodo: TipoArbol:= new TipoNodo'(Elemento, null, null);Ptr: TipoArbol:= Raiz;Anterior: TipoArbol:= null;begin-- el nodo creado contiene el elemento y se inserta en el lugar apropiado del ABB

while Ptr /= null loop -- busca hasta que ptr caiga del árbolAnterior:= Ptr;if Ptr.Info > Elemento then Ptr:= Ptr.Izq;else Ptr:= Ptr.Der;end if;

end loop;-- se encontró lugar de inserción. Conectar punteros para enlazar NuevoNodo al

árbolif Anterior = null then Raiz:= NuevoNodo;else if Anterior.Info > Elemento

then Anterior.Izq:= NuevoNodo;else Anterior.Der:= NuevoNodo ;end if;

end if;end Insertar;

Alg

orítm

ica

y P

rogr

amac

ión

II

22

Procedimiento Insertar Versión recursiva

procedure Insertar (Raiz: in out TipoArbol; Elemento: in TipoElem) is

begin

if Raiz = null then Raiz:= new TipoNodo'(Elemento, null, null);

elsif Elemento < Raiz.Info then Insertar (Raiz.Izq, Elemento);

else Insertar (Raiz.Der, Elemento);

end if;

end Insertar;

Alg

orítm

ica

y P

rogr

amac

ión

II

Operación insertar recursiva

23[Dale 2003]

Insertar Elemento=13

Alg

orítm

ica

y P

rogr

amac

ión

II

Operación Suprimir

Esta operación involucra dos pasos:1. Encontrar el nodo en el árbol.2. Borrar el nodo del árbol.

El segundo paso requiere el análisis de trescasos: Borrar un nodo hoja Borrar un nodo que tiene un hijo Borrar un nodo que tiene dos hijos

Encontrar el predecesor (nodo más a la derecha delsubárbol izquierdo)

Reemplazar los datos del nodo a borrar con los datosdel predecesor

Borrar el nodo predecesor24

Alg

orítm

ica

y P

rogr

amac

ión

II

25

[Dale 2003]

Eliminar un nodo hoja

Eliminar un nodo con un hijo

Operación SuprimirA

lgor

ítmic

a y

Pro

gram

ació

n II

26

[Dale 2003]

Eliminar un nodo con dos hijos

Operación Suprimir

Alg

orítm

ica

y P

rogr

amac

ión

II

27

[Dale 2003]

Supresión de un ABBA

lgor

ítmic

a y

Pro

gram

ació

n II

28

procedure suprimir (arbol: in out tipoarbol; valsup: in tipoelem) is

begin

if arbol = null then raise arbolVacio;

elsif valsup = arbol.Info then suprimirnodo (arbol);

elsif valsup < arbol.Info then suprimir (arbol.izq, valsup);

else suprimir (arbol.der, valsup);

end if;

end suprimir;

Alg

orítm

ica

y P

rogr

amac

ión

II

29

procedure suprimirnodo (arbol : in out tipoarbol) istemp: tipoarbol;max: tipoarbol;begin

if arbol.izq = null and arbol.der = null then Free(arbol);elsif arbol.izq = null then temp:= arbol;

arbol:= arbol.der ;Free (temp);

elsif arbol.der = null then temp:= arbol;arbol:= arbol.izq;Free (temp);

else buscarMax (arbol.izq, max);arbol.info := max.Info;Free (max);

end if;end suprimirnodo;

Alg

orítm

ica

y P

rogr

amac

ión

II

30

procedure buscarMax (arbol: in out tipoarbol; maxPtr: out tipoarbol) is

begin

if arbol.der = null then MaxPtr:= arbol;

arbol:= arbol.izq;

else buscarMax (arbol.der, maxPtr);

end if;

end buscarMax;

Alg

orítm

ica

y P

rogr

amac

ión

II

31

function Esta (Raiz: in TipoArbol; Buscado: in TipoElem) return Boolean is -- iterativo Ptr: TipoArbol:= Raiz;ValorEnArbol: Boolean:= False; begin

while Ptr /= null and not ValorEnArbol loopif Ptr.Info = Buscado then ValorEnArbol:= True;else if Ptr.Info > Buscado then Ptr:= Ptr.Izq;

else Ptr:= Ptr.Der;end if;

end if;end loop;return ValorEnArbol;

end Esta;

function Esta (Raiz: in TipoArbol; Buscado: in TipoElem) return Boolean is -- recursivobegin

if Vacio(raiz) then return False;else if raiz.Info = Buscado then return True;

else if raiz.Info > Buscado then return Esta(raiz.Izq, buscado);else return Esta(raiz.Der, buscado);end if;

end if;end if;

end Esta;

Alg

orítm

ica

y P

rogr

amac

ión

II

Otras operaciones útiles

32

function Izq (ptr: TipoArbol) return TipoArbol isbegin

return ptr.izq;end izq;

function Der (ptr: TipoArbol) return TipoArbol isbegin

return ptr.der;end der;

function Info (ptr: TipoArbol) return TipoElem isbegin

if Vacio(ptr) then raise ArbolVacio,else return ptr.info;

end Info;

Alg

orítm

ica

y P

rogr

amac

ión

II

Nivel de aplicación

Comparación del ABB con la lista enlazadaordenada. El ABB es una estructura adecuada para muchas

de las mismas aplicaciones de la lista enlazadaordenada. La principal ventaja de usar un ABB esque facilita la búsqueda es especialmenteadecuado para aplicaciones en que el tiempo debúsqueda se debe minimizar o en las que losnodos no serán procesados en orden secuencial.

El ABB ocupa más espacio en memoria que unalista enlazada y los algoritmos para manipularloson más complicados.

33

Alg

orítm

ica

y P

rogr

amac

ión

II

Ejemplo

Función que cuenta los nodos no hoja de unABB.

function Nohoja (Arbol:Tipo_Arbol) return natural is

begin

if Vacio(Arbol) then return 0;

else if not Vacio(Izq(Arbol)) or not Vacio(Der(Arbol)) then

return 1+ Nohoja (Izq(Arbol)) + Nohoja(Der(Arbol));

else return Nohoja (Izq(Arbol)) + Nohoja(Der(Arbol));

end if;

end if;

end Nohoja;

34

Alg

orítm

ica

y P

rogr

amac

ión

II

Recorridos en un ABB

Recorrer un árbol significa visitar sus nodos, seapara imprimir la información de cada uno o pararealizar otro procesamiento.

Para acceder a la información del árbol se debepartir desde la raíz y desde ahí, avanzar hacia laizquierda o la derecha.

Ejemplo: para imprimir los valores del árbol enorden de menor a mayor, primero se imprimenlos valores del subárbol izquierdo de la raíz,luego el valor del nodo raíz y finalmente losvalores del subárbol derecho de la raíz.

35

Alg

orítm

ica

y P

rogr

amac

ión

II

Recorrido InOrden de un ABB

36

Raíz Imprimir segundo

Imprimir al final

Imprimir primero

Alg

orítm

ica

y P

rogr

amac

ión

II


Al “moverse” hacia el subárbol izquierdo, se“pierde” el puntero a la raíz y no se puedevolver atrás. Esto ocurre cada vez que seactualiza el puntero hacia la izquierda.

Considerando que para cada nodo se debeimprimir su subárbol izquierdo, luego el nodoy a continuación su subárbol derecho, ¿quérecurso se puede usar para resolver esa“vuelta atrás”?

37

Alg

orítm

ica

y P

rogr

amac

ión

II


La estructura de datos que resuelve esemodelo de “vuelta atrás” es la pila. Así escomo se recorren las ramas de la izquierdamientras es posible (Izq ≠ Nulo) y se vaapilando el puntero a cada nodo por el quese pase:

mientras P /= Nulo hacercomienza

meter(PilaPun, P)P ← P.Izq

termina38

Alg

orítm

ica

y P

rogr

amac

ión

II


P es Nulo cuando el subárbol izquierdo estávacío. Entonces hay que retroceder hacia laraíz. ¿Cómo se hace?

Se saca de la pila cada puntero, se imprimela información del nodo apuntado por P y secomienza a recorrer el subárbol derechorepitiendo la misma rutina. ¿Cuándo finaliza?Cuando P sea nulo y la pila esté vacía.

39

Alg

orítm

ica

y P

rogr

amac

ión

II

N

E

K

S

Inicio

PilaPun

RaizP

N

E

K

S

PilaPun

Fin del primer bucle while

↑N↑E

P Nulo

N

E

K

S

PilaPun

Sacar y escribir

↑N

P

Salida: E

N

E

K

S

PilaPun

↑N

P

Obtener subárbolderecho

Salida: E

N

E

K

S

PilaPun

↑N

↑K

P Nulo

Bucle while (ir izquierda)

Salida: E

N

E

K

S

PilaPun

↑N

P

Salida: E K

Sacar y escribir

40

Alg

orítm

ica

y P

rogr

amac

ión

II

N

E

K

S

Obtener subarbol derecho

PilaPun

N

E

K

S

PilaPun

P Nulo

N

E

K

S

PilaPun

Sacar y escribir

P

N

E

K

S

PilaPun

↑S

P

Bucle while (ir izquierda)

N

E

K

S

PilaPun

P Nulo

Sacar y escribirN

E

K

S

PilaPun

Salida: E K

↑N

P

Salida: E K N

Ir a la derecha

Nulo

Salida: E K N Salida: E K N

Salida: E K N S Salida: E K N S

Ir a la derecha

P Nulo

41

Alg

orítm

ica

y P

rogr

amac

ión

II

Recorrido Inorden

InOrden: B D E H K M N Q R S T V W Z

RaizN

MHB

KD

E S

R

Q

W

ZV

T

42

Alg

orítm

ica

y P

rogr

amac

ión

II


procedure InOrden (Ptr: in TipoArbol) isbegin -- inorden iterativo

Limpiar (PilaPun);P:= Raiz;loop

while P/= null loopMeter (PilaPun, P);P:= P.Izq;

end loop;-- si existe algo en la pila, sacar, imprimir y mover a la derechaif not Pila.Vacia(PilaPun) then

Sacar (PilaPun,P);Imprimir (P.Info);P:= P.Der;

end if;exit when P=null and Vacia (PilaPun);

end loop;end InOrden;

43

Alg

orítm

ica

y P

rogr

amac

ión

II

Recorridos recursivos del ABB

Recorrido InOrdenDefinición: recorre todos los nodos del ABB,visitando cada nodo entre su subárbol izquierdo y susubárbol derecho. Imprime todos los elementos delABB en orden de menor a mayor.Tamaño: Todos los nodos del árbol.Caso base: P=Nulo.Caso general: Recorrer el subárbol izquierdo en

Inorden.Imprimir Info(P)Recorrer el subárbol derecho en Inorden.

44

Alg

orítm

ica

y P

rogr

amac

ión

II

Recorrido InOrden recursivo

procedure InOrden (Ptr: in TipoArbol) is

begin

if not Vacio(Ptr) then InOrden (Izq(Ptr));

Put (Info(Ptr));

InOrden (Der(Ptr));

end if;

end InOrden;

45

Alg

orítm

ica

y P

rogr

amac

ión

II


Recorrido PreOrdenDefinición: recorre todos los elementos del árbolbinario, visitando cada nodo antes que su subárbolizquierdo y su subárbol derecho.Tamaño: Todos los nodos del árbol.Caso base: P=Nulo.Caso general: Imprimir Info(P)

Recorrer el subárbol izquierdo en PreOrden.Recorrer el subárbol derecho en PreOrden.

46

Alg

orítm

ica

y P

rogr

amac

ión

II

Recorrido Preorden

PreOrden: N E D B K H M S R Q W V T Z47

RaizN

MHB

KD

E S

R

Q

W

ZV

T

Alg

orítm

ica

y P

rogr

amac

ión

II

Recorrido PreOrden recursivo

procedure PreOrden (Ptr: in TipoArbol) is

begin

if not Vacio(Ptr) then Put (Info(Ptr));

PreOrden (Izq(Ptr));

PreOrden (Der(Ptr));

end if;

end PreOrden;

48

Alg

orítm

ica

y P

rogr

amac

ión

II


Recorrido PosOrdenDefinición: recorre todos los elementos del árbolbinario, visitando cada nodo después que susubárbol izquierdo y su subárbol derecho.Tamaño: Todos los nodos del árbol.Caso base: P=Nulo.Caso general: Recorrer el subárbol izquierdo en

PosOrden.Recorrer el subárbol derecho en PosOrden.Imprimir Info(P)

49

Alg

orítm

ica

y P

rogr

amac

ión

II

Recorrido Posorden

PosOrden: B D H M K E Q R T V Z W S N50

RaizN

MHB

KD

E S

R

Q

W

ZV

T

Alg

orítm

ica

y P

rogr

amac

ión

II

Recorrido PosOrden recursivo

procedure PosOrden (Ptr: in TipoArbol) is

begin

if not Vacio(Ptr) then PosOrden (Izq(Ptr));

PosOrden (Der(Ptr));

Put (Info(Ptr));

end if;

end PosOrden;

51

Documents

AlgoritmicaII-Arbol Binario de Busqueda