Tópicos I

Unidad I

Arboles de búsqueda

Semana 1

Árboles, montículos y grafos

Objetivos Generales

Entender el manejo, uso de algoritmos y estructuras de datos avanzados, haciendo énfasis en los algoritmos de internet, seguridad y redes.

Objetivo Específico

Implementar algoritmos utilizando estructura de datos avanzadas.

Objetivo Instruccional

Implementar algoritmos de búsqueda en arboles binarios.

Para la mayoría de los problemas existen varios algoritmos diferentes. ¿Cómo elegir uno que conduzca a la mejor implementación?

Normalmente los problemas a resolver tienen un “tamaño” natural (en general, la cantidad de datos a procesar), al que se denominara N y en función del cual se tratara de describir los recursos utilizados (con frecuencia, la cantidad de tiempo empleado).

El punto de interés es el estudio del caso medio, es decir, el tiempo de ejecución de un conjunto “tipo” de datos de entrada, y el del peor caso, el tiempo de ejecución para la configuración de datos de entrada mas desfavorable.

El primer paso del análisis de un algoritmo es establecer las características de los datos de entrada que utilizara y decidir cual es el tipo de análisis mas apropiado.

Pasos a considerar en el análisis de algoritmos

Idealmente, seria deseable poder obtener, para cualquier distribución de probabilidad de las posibles entradas, la correspondiente distribución de los tiempos empleados en la ejecución del algoritmo. Pero no es posible alcanzar este ideal para un algoritmo que no sea trivial, de manera que, por lo regular, se limita el desarrollo estadístico intentando probar que el tiempo de ejecución es siempre menor que algún “limite superior” sea cual sea la entrada, e intentando obtener el tiempo de ejecución medio para su entrada “aleatoria”.

El segundo paso del análisis de un algoritmo es identificar las operaciones abstractas en las que se basa, con el fin de separar el análisis de la implementación.

Pasos a considerar en el análisis de algoritmos

Así, por ejemplo, se separa el estudio del número de comparaciones que realiza un algoritmo de ordenación del estudio para determinar cuantos microsegundos tarda una computadora concreta en ejecutar un código de maquina cualquiera producido por un compilador determinado para el fragmento de código if (a[i] < V)…

El primero dependerá de las propiedades el algoritmo, mientras que el segundo dependerá de las propiedades de la computadora.

El tercer paso del análisis de un algoritmo es analizarlo matemáticamente, con el fin de encontrar los valores del caso medio y del peor caso para cada una de las cantidades fundamentales.

Pasos a considerar en el análisis de algoritmos

No es difícil encontrar un limite superior del tiempo de ejecución de un programa – el reto es encontrar el mejor limite superior, aquel que se encontraría si se diera la peor entrada posible –. Esto produce el peor caso: el caso medio normalmente requiere un análisis matemático mas sofisticado.

Clasificación de los algoritmos

La mayoría de los algoritmos tienen un parámetro primario N, normalmente el numero de elementos de datos a procesar, que afecta muy significativamente al tiempo de ejecución.

El parámetro N podría ser el grado de un polinomio, el tamaño de un archivo a ordenar o en el que se va a realizar una búsqueda, el número de nodos de un grafo, etc.

Proporcionalidad del tiempo de ejecución de un algoritmo

Proporcionalidad Características

1 La mayor parte de las instrucciones de la mayoría de los programas se ejecutan una vez o muy pocas veces (constante)

Log N Cuando el tiempo de ejecución de un programa es logarítmico, este será ligeramente ms lento a medida que crezca N.

N Cuando el tiempo de ejecución de un programa es lineal, eso significa generalmente que para cada elemento de entrada se realiza una pequeña cantidad de procesos.

N log N Este tiempo de ejecución es el de los algoritmos que resuelven un problema dividiéndolo en pequeños subproblemas, resolviéndolos independientemente, y combinando después las soluciones.

N2 Cuando el tiempo de ejecución de un algoritmo es cuadrático, solo es practico para problemas relativamente pequeños.

N3 Un algoritmo que procesa tríos de elementos de datos (por ejemplo un bucle anidado triple) tiene un tiempo de ejecución cubico y no es útil mas que en problemas pequeños.

2N Pocos algoritmos con un tiempo de ejecución exponencial son susceptibles de poder ser útiles en la practica, aunque aparecen de forma natural al aplicar el método de la “fuerza bruta” en la resolución de problemas.

• Estructuras linealesSon flexibles pero son secuenciales, un elemento detrás de otro. Vectores, listas.

• Estructuras no lineales–Junto con los arboles, los grafos son estructuras de datos no lineales

–Superan las desventajas de las listas

–Sus elementos se pueden recorrer de distintas formas, no necesariamente uno detrás de otro

Son muy útiles para la búsqueda y recuperación de información

ARBOLESEstructura que organiza sus elementos formando jerarquías: PADRES e HIJOS

Un subárbol de un árbol Es cualquier nodo del árbol junto con todos

sus descendientes

Los elementos de un árbol se llaman nodos Si un nodo p tiene un enlace con un nodo m,

p es el padre y m es el hijo Los hijos de un mismo padre se llaman: hermanos

A

B

D E

C

F

Todos los nodos tienen al menos un padre, menos la raíz: A

Si no tienen hijos se llaman hoja: D, E, F y C

B

D E F

TERMINOLOGIA Camino: Secuencia de nodos conectados

dentro de un árbol Longitud del camino: Es el número de nodos

menos 1 en un camino Nivel de un árbol: Es el número de nodos

entre la raíz y el nodo mas profundo del arbol Altura del árbol: Es el nivel mas alto del

árbol Un árbol con un solo nodo tiene altura 1

Nivel (profundidad) de un nodo: Es el número de nodos entre el nodo y la raíz.

Grado(aridad) de un nodo: Es el número de hijos del nodo

Grado(aridad) de un árbol: Máxima aridad de sus nodos

A

B

D E

C

F

TAD ARBOL: Definición Informal• Valores:

– Un nodo puede almacenar contenido y estar enlazado con sus árboles hijos (pueden ser dos o varios)

• Operaciones: Dependen del tipo de árbol, pero en general tenemos:– Vaciar o inicializar el Arbol

• void Arbol_Vaciar (Arbol *A);– Eliminar un árbol

• void Arbol_Eliminar(Arbol *A);– Saber si un árbol esta vacío

• bool Arbol_EstaVacio(Arbol A);– Recorrer un árbol

• void PreOrden(Arbol A)• void EnOrden(Arbol A)• void PostOrden(Arbol A)

Tipo Abstracto Datos

TAD ARBOL: Definición Formal

<arbol> ::= <<NULL>> | <nodo><nodo> ::= <contenido>{<arbol>}<contenido> ::=

<<dato>>{<<dato>>}

Tipo especial de árbol– Cada nodo no puede tener mas de

dos hijos

Un árbol puede ser un conjunto– Vacío, no tiene ningún nodo

– O constar de tres partes:

• Un nodo raíz y

• Dos subárboles binarios: izquierdo y derecho

La definición de un árbol binario es recursiva– La definición global depende de si

misma

A

B C

D

A

B C

D E

H I

F G

J

RAIZ

Sub. Izq.

Sub. Der.

ARBOLES BINARIOS LLENOS Un árbol de altura h, esta lleno si:

– Todas sus hojas están en el nivel h– Los nodos de altura menor a h tienen siempre

2 hijos

Sea T un árbol– Si T esta vacío,

• Entonces T es un árbol binario lleno de altura 0

– Si T no esta vacío, y tiene h>0• Esta lleno si los subárboles de la raíz, son

ambos árboles binarios llenos de altura h-1

ARBOLES BINARIOS COMPLETOS

Un árbol de altura h esta completo si:– Todos los nodos hasta el nivel h-2

tienen dos hijos cada uno y

– En el nivel h-1, si un nodo tiene un hijo derecho, todas las hojas de su subarbol izquierdo están a nivel h

Si un árbol esta lleno, también esta completo

OTROS• Un árbol equilibrado es cuando

– La diferencia de altura entre los subárboles de cualquier nodo es máximo 1

• Un árbol binario equilibrado totalmente– Los subárboles izquierdo y derecho de cada

nodo tienen las misma altura: es un árbol lleno

• Un árbol completo es equilibrado– Por definición

• Un árbol lleno es totalmente equilibrado– Por definición

RECORRIDOS

Recorrer es:– Visitar todos los elementos de una estructura

Como recorrer un árbol– Hay tantos caminos, ¿cual escoger?– Existe tres recorridos típicos• Nombrados de acuerdo a la posición de la raíz

– Preorden: raíz - subarbol izq. - subarbol der.– Enorden : subarbol izq. - raíz - subarbol der.– Postorden : subarbol izq. - subarbol der. - raíz

EJEMPLO PREORDEN

GG-DG-D-BG-D-B-AG-D-B-A-CG-D-B-A-C-E

G

D K

B E H M

A C F J

I

L

G

1D

2B

3A

4

C

5

E

6F

7

G-D-B-A-C-E-F

K

8

G-D-B-A-C-E-F-K

H

9

G-D-B-A-C-E-F-K-H

J

10

G-D-B-A-C-E-F-K-H-J

I

11

G-D-B-A-C-E-F-K-H-J-I

M

12

G-D-B-A-C-E-F-K-H-J-I-M

L

13

G-D-B-A-C-E-F-K-H-J-I-M-L

1. Visitar raiz2. Preorden al Subarbol Izq.3. Preorden al Subarbol Der.

AB y NODOAB: Definición Formal

<ab>::= nulo | <nodoab><nodoab>::=<contenido> + <izq> + <der><izq>::=<ab><der>::=<ab><contenido>::<<dato>>|{<<dato>>}

AB Y NODOAB: Declaración• Un árbol binario: es conjunto de nodos

– Solo se necesita conocer el nodo raíz

• Cada nodo

– Tiene Contenido y

– Dos enlaces: árbol hijo izquierdo, árbol hijo derecho

• Un nodo hoja, es aquel cuyos dos enlaces

apuntan a null

• De un árbol solo se necesita conocer su raíz

– La raíz, que es un nodo, puede definir al árbol

typedef struct NodoAB{Generico G;NodoAB *izq, *der;

}NodoAB;

typedef struct NodoAB *AB;

NODOAB: Operaciones

Son elementos de un árbol que: – Almacenan información (contenido), – Conocen hijo izquierdo y derecho, ambos son nodos

Operaciones Básicas– Crear un nuevo nodo hoja

• NodoAB *NodoAB_CrearHoja(Generico G);

– Eliminar hoja existente• void NodoAB_Eliminar (NodoArbol **A);

– Saber si el nodo es o no hoja• bool NodoAB_EsHoja(NodoArbol *p);

NODOAB: Mas Operaciones

Consultas de los campos de un nodo– Generico NodoAB_ConsultaContenido(NodoAB *nodo);

– NodoAB *NodoAB_Izq (NodoAB *nodo);

– NodoAB *NodoAB_Der(NodoAB *nodo);

Cambiar los campos de un nodo– void NodoAB_SetContenido (NodoAB *nodo , Generico G);

– void NodoAB_SetIzq(NodoAB *nodo, NodoAB *enlace);

– void NodoAB_SetDer(NodoAB *nodo, NodoAB *enlace);

AB: CREAR NODO HOJA

Se debe crear un nodo nuevo: un nodo hoja

NodoAB *NuevaHoja(Generico G){NodoAB *nuevo;nuevo = (NodoAB *)malloc(sizeof(NodoAB));nuevo->G = G;nuevo->izq = NULL;nuevo->der= NULL;return nuevo;

}

AB: Mas Operaciones• Eliminar

– AB_Eliminar(AB *A);• Estado del Arbol

– bool AB_EstaVacio(AB A);• Añadir y remover nodos

– void AB_InsertarNodo(AB *A, NodoAB *nuevo)– NodoAB *AB_SacarNodoxContenido(AB *A, Generico G,

Generico_fnComparar fn);– NodoAB * AB_SacarNodoxPos(AB *A, NodoAB *pos);

• Busqueda por contenido– NodoArbol *AB_Buscar(AB A, Generico G, Generico_fnComparar fn

);• Recorridos

– void AB_PreOrden(AB A);– void AB_PosOrden(AB A);– void AB_EnOrden(AB A);

AB: Creando e Instanciando

Un Arbol Vacío, es aquel cuyo nodo raíz apunta a NULL

void AB_Vaciar(AB *A){*A = NULL;

}

Para crear una variable tipo Arbol, y empezarla a usar:

Instanciarlo (crear variable) Vaciar el árbol

Para añadirle una hoja al árbol, crear hoja:

AB A;AB_Vaciar(&A);

A = NodoAB_CrearHoja(Generico_CrearEntero(1)); 1A

RECORRIDOS: Implementación• Como ya se reviso, las operaciones de recorrido

son recursivas• Ejemplo: EnOrden

– Recorrer EnOrden al subarbol izquierdo– Visitar nodo raiz– Recorrer EnOrden al subarbol derecho

• En todo algoritmo recursivo debemos buscar dos casos:– Básico, en que momento termina la recursividad– Recursivo, donde la función se llama a si misma

Caso Básico Si AB_EstaVacio(raiz)

Terminar de recorrer

Caso Recursivo Si !AB_EstaVacio(raiz)

AB_EnOrden(raiz->izq);Mostrar raiz->IAB_EnOrden(raiz->der);

OPERACION ENORDEN

void AB_EnOrden(AB A, Generico_fnImprimir imprimir){if(!AB_EstaVacio(A)){

AB_EnOrden(A->izq,imprimir); imprimir(A->G);AB_EnOrden(A->der,imprimir);

}}

A

B C

D E F GD

1

B

2E

3

A

4

F

5

C

6

G

7Arbol Vacio!, Terminar

APLICACIÓN: Evaluación de Expresiones

• Ya se sabe lo de las expresiones– InFija, operador en medio

– PreFija, operador antes de dos operandos

– PosFija, operador luego de dos operandos

• Para evaluar una expresión dada, podríamos– Pasarla a posfija y usar solo pilas

– Pasarla a posfija y usar pilas y un árbol de expresión

ARBOL DE EXPRESION

• Arboles que representan expresiones en memoria– Todos los operadores tienen dos operandos

• La raiz puede contener el operador

• Hijo izq: operando 1, Hijo derecho: operando 2

– Ejemplo:

(a+b)+

a b

(a+b)*c+

a b

c

*

Ejercicio en Clase

• Construya arboles de expresión para:(X+(Y*Z)) * (A-B)

• Deducir la expresión del siguiente A.B.+

a *

b -

+

c d

Evaluar una expresión aritmética en infija

La expresión se transforma a la expresión posfija– Esto, ya sabemos como hacerlo

Crear un árbol de expresión– Para esto se va a usar una pila y un árbol de

caracteres

Usando el árbol, evaluar la expresión

Crear un árbol de expresión

• Los operandos serán siempre nodos hoja del árbol

• Los operadores serán nodos padre

A*B-C*D+H AB*CD*-H+

A

B *

BA

C

D

*

DC

-

*

DC

*

BA

H

+

-

*

DC

*

BA

H

Evaluación de la expresión postfija

• Lo ideal es recuperar los dos operandos, el operador, y ejecutar la opción

• ¿Que recorrido es el ideal?– PostOrden

+

-

*

DC

*

BA

H

Para evaluar el árbol:

Si el árbol tiene un solo nodo y este almacena un operando

El resultado de la evaluación es el valor de ese operando

Si no

1. Res1 = Evaluó subarbol izquierdo

2. Res2 = Evaluó subarbol derecho

3. Recupero la info de la raiz y efectuo la operación allí indicada, entre Res1 y Res2

AA y BA * B(A * B) y C(A * B) y C y D(A * B) y (C*D)(A * B) - (C*D)(A * B) - (C*D) y H(A * B) - (C*D) + H

Árbol binario de búsqueda• Los elementos en un árbol

– Hasta ahora no han guardado un orden

– No sirven para buscar elementos

• Los arboles de búsqueda– Permiten ejecutar en ellos búsqueda

binaria

– Dado un nodo:

• Todos los nodos del sub. Izq. Tienen una clave menor que la clave de la raíz

• Todos los nodos del sub. Der. Tienen una clave mayor que la clave de la raíz

4

5

9

6

30

41

75

55

4 85

TAD ABB: Definición

Valores: – Conjunto de elementos – Dado un nodo p,

• Los nodos del árbol izquierdo almacenan valores mayores al de p

• Los nodos del árbol derecho almacenan valores menores al de p

Operaciones– Son las mismas operaciones que para un AB– Pero en este caso ya tenemos reglas suficientes que nos

indican como:• Insertar• Sacar • Buscar

<abb>::= NULL | <abb_nodo><abb_nodo>::=<clave>+<contenido>+<izq>+<der><izq>::=<abb><der>::=<abb><clave>::<<dato>>|{<<dato>>}<contenido>::<<dato>>|{<<dato>>}

typedef struct ABB_Nodo{Generico clave, G;ABB_Nodo *izq, *der;

}ABB_Nodo;

Crear con clave

• Como el nodo ahora tiene un campo clave– Cambian un poco las operaciones del nodo

• Ejemplo

NodoAB *NuevaHoja(Generico clave, Generico contenido){NodoArbol *nuevo;nuevo = malloc(sizeof(NodoArbol));nuevo->clave = clave;nuevo->G = contenido;nuevo->izq = NULL;nuevo->der= NULL;return nuevo;

}

CREACION DE UN ABB• Un árbol de búsqueda debe mantener

– A la derecha valores mayor a la raíz– A la izquierda valores menor a la raíz

• Ejemplo:– Construya árbol con los siguientes elementos:

• 8, 3, 1, 20, 10, 5, 4

8

3

1

20

105

4

Ejercicio en clase

• Construya el árbol para almacenar:12, 8, 7, 16, 11

?

Búsqueda de un nodo• Dada una clave, devolver el nodo

que la contiene• Se comienza en la raíz

– Si el árbol esta vacío• No se encontró

– Si clave buscada es igual a la clave del nodo evaluado• Se encontró

Si no• Si la clave buscada es mayor a la del

nodo evaluado– Buscar en el subarbol derecho

• Si no– Buscar en el subarbol izquierdo

8

3

1

20

105

4

Buscar(raiz,5)

55

Buscar(raiz,25)

No existe

Implementación de la búsqueda

NodoABB *ABB_Buscar(ABB A, Generico clave, Generico_fnComparar comp){

if(ABB_EstaVacio(A)) return NULL;

if(f(clave, A->clave) == 0) return A;

if(f(clave, A->clave) > 0))

return ABB_Buscar(A->der, clave, comp);

else

return ABB_Buscar(A->izq, clave, comp);

}

Inserción de un nodo

• Muy parecido a la búsqueda

• Debo insertar en la posición correcta– El árbol debe mantener sus

propiedades

• Pasos:– Crear una nueva hoja

– Buscar en el árbol donde ponerla

– Enlazar el nuevo nodo al árbol

8

3

1

20

105

4

Insertar(raiz,15)

15>8…der

15<20…izq

15>10…der

Insertar aqui

15

Implementación de la inserción

bool ABB_Insertar(ABB *A, NodoABB *nuevo, Generico_fnComparar f){

if(!ABB_EstaVacio(*A)){

if(f(nuevo->clave, (*A)->clave) >0)

ABB_Insertar((*A)->der, nuevo,f);

else if(f(nuevo->clave, (*A)->clave) <0)ABB_Insertar((*A)->izq,nuevo,f);

elsereturn FALSE;

} else{//Si esta vacio, alli insertar*A = nuevo;

}return TRUE;

}

Eliminación de un nodo

• Es mas compleja que la inserción• Al sacar un nodo del árbol

– El árbol debe mantener sus propiedades– El árbol debe reajustarse

• Pasos:– Buscar el nodo p que se va a eliminar– Si el nodo a eliminar tiene menos de dos hijos

• Subir el nodo hijo a la posición del nodo eliminado

Si no• Ubicar el nodo q con la mayor de las claves

menores• Reemplazar contenido de p con el del nodo q• Eliminar el nodo q que se encontró en el

primer paso

34

18

6

90

28

25

20

100

Eliminar(raiz,34)

34

nmayor

28

28

Implementación de sacar un nodo

NodoABB *ABB_SacarNodoxContenido(ABB *A, Generico clave, Generico_fnComparar fn) {NodoABB *p, *tmp = *A;if(ABB_EstaVacio(*A)) return NULL;if(fn((*A)->clave, clave) < 0)

return(ABB_SacarNodoxContenido(&(*A)->der, clave, fn));

else if(fn((*A)->clave, clave) >0)return(ABB_SacarNodoxContenido(&(*A)->izq, clave,

fn));

if((*A)->der == NULL)(*A) = (*A)->izq;

else if((*A)->izq == NULL)(*A) = (*A)->der;

elsetmp = ABB_SacarRaiz(A);

return tmp;}

REVISAR…Métodos de búsqueda elementales:

– Búsqueda secuencial– Búsqueda binaria– Búsqueda por árbol binario– Búsqueda directa en arboles binarios

Métodos de ordenación elementales:

– Ordenación por selección– Ordenación por inserción– Ordenación de burbuja– Ordenación de shell– Ordenación rápida (Quicksort)

Tópicos I

Unidad I

Arboles de búsqueda

Semana 1

Árboles, montículos y grafos