Estructura de Datos, Algoritmos y Matemáticas Discretas

Unidad GuadalajaraUnidad Guadalajara

Estructura de Datos, Algoritmos y Matemáticas Discretas

Félix RAMOSGrupo Ciencias Computacionales

Material original y compilado


z


Objetivos:

1. Ilustrar los conceptos de C

2. Introducir a la complejidad de algoritmos


Algoritmo

Definición: Un algoritmo es un conjunto finito de instrucciones que pueden sirven a resolver un problema si fueron construidas correctamente.

Criterios generales de los algoritmos:

1. Tiene cero o más cantidades de entrada

2. Existe al menos una salida

3. No debe existir claro y no ambiguo

4. En la mayoría de los casos el algoritmo debe terminar en un número finito de pasos.


Ejemplo: ordene un conjunto de enteros n ≥ 1

For (i=0 ; i < n ; i= n ; i++) {Examinar list[i] to list[n-1] y dejar el mínimo en list[min];intercambiar list[i] y list[min];

}


51015122[4][3][2][1][0]

52151210[4][3][2][1][0]

12151052[4][3][2][1][0]

12101552[4][3][2][1][0]

15121052

[4][3][2][1][0]

i = 1

i = 2

i = 3

i = 4

i = 0

Ejemplo: Ordene el siguiente vector


Escriba el programa en CHint: divida el problema en dos partes• Encontrar el mas pequeño • Intercambiar elementos

Aprovechemos este ejercicio para repasar apuntadores.

ptr-y = &y Operador de dirección

x = *ptr-y Operador de referencia

Esto es tenemos dos maneras de acceder a una variable

1. Directamente por su nombre y

2. Por medio del operador de referencia *ptr-y


-34

2362

MemoriaDirección

23592360236123622363236423652366

2358

y

ptr-y


Programa de intercambio/* función que intercambia los valores de dos lugares de memoria indicados por los apuntadores x e y.*/Void swap(int *x, int *y){

int temp;Temp = *x;*x = *y;*y = temp;

}

La manera de llamar esta función es: swap (&a, &b)


Funciones RecursivasUn algoritmo es recursivo si se llama a si mismo (recursión directa) o llama a otras funciones que la invocan a su vez (recursiónindirecta)

Ejemplo: Algoritmo para generar e imprimir todas las permutaciones del conjunto {a, b ,c, d}.

1. a seguido de todas las permutaciones de {b, c, d}.

2. b seguido de todas las permutaciones de {a, c, d}.

3. c seguido de todas las permutaciones de {a, b, d}.

4. d seguido de todas las permutaciones de {a, b, c}.


Algoritmos iterativosAlgoritmo iterativo: Este tipo de algoritmos en general calcula sus valores tomando los valores de la función previamente calculados en pasos anteriores

xk= f(xk-1, xk-2 , …..)

Ejemplo: suma de los cuadrados de los n números

void main (void){

int k, n, sum;

n=10; sum=0;

for(k=1;k<=n;k++)

sum = sum+ k*k;

printf(“sum=%d”, sum);

}


Version RecursivaAlgoritmo recursivo: En la mayoría de los casos la recursiónresulta mas natural pero hay que recordar que tiene un costo.

Ejemplo: suma de los cuadrados de los n números recursivo

void main (void){

int sum;

sum = sumsqr(10);

printf(“sum=%d”, sum);

}

int sumsqr(int i){

if(i>0) return sumsqr(i-1) + i*i;

}


Complejidad

La complejidad nos sirve para ver cuanto cuesta la ejecución de un programa.

Complejidad en espacio: se refiere a la cantidad de memoria necesaria para la ejecución del algoritmo.

Complejidad en tiempo: tiempo necesario para la ejecución del algoritmo.

Talg = Tcomp = Trun


Complejidad

Paso del algoritmo: es un segmento del algoritmo cuyo tiempo de ejecución es independiente de las características de la instancia.

Tamaño del problema: es el numero de pasos que contenga.

Ejemplo: producto de dos matrices A y B de n x n

kl

n

lliki bac ,

1,, ∑

=

=

Paso del Algoritmo: suma o multiplicación.

Tamano del problema:

n3 multiplicaciones

n2(n-1) sumas


ComplejidadEl paso de un algoritmo nos permite calcular la complejidad de un algoritmo. Para el ejemplo anterior podemos calcular la complejidad de la siguiente manera.

C nxn = n3 + n2(n-1) = 2n2(n- o.5) = O(n3) pasos

O() es conocida como notación asintótica o orden de crecimiento

Definición: f(n) = O(g(n)) sii existe una constante positiva c y N tal que:

f(n) ≤ cg(n) ∀n ≥ N


Complejidad Ejemplo: Obtener la O(.) de 2n+3. Tomando c=3, tenemos

2n+ 3 ≤ 3n ∀ n ≥ 3

Por lo que:

2n + 3 = O(n)Esta presentación no es única, i.e. si 2n+3 = O(n), por lo que lo siguiente también es verdadero

2n+3 = O(n2)

2n+3 = O(n3)

2n+3 = O(n4)

…. . . ……


Complejidad Por lo que f(n) = O(g(n)) solo establece que cg(n) es un límite superior al valor f(n) para todo n ≥ N. No quiere decir nada acerca de que tan bueno es este límite.

A fin que la expresión f(n) = O(g(n)) sea informativa, g(n) debe ser tan pequeña una función de, como se pueda! De tal manera que cuando digamos:

2n + 3 = O(n), No podamos decir

2n + 3 = O(n2),Aunque este último también sea correcto.


Complejidad

Terminología comúnmente usada:

O(1) Complejidad ConstanteO(n) Complejidad linealO(n2) Complejidad cuadráticaO(n3) Complejidad cúbicaO(nn) Complejidad exponencial(log n) Complejidad logarítmica

Existen combinaciones mas complicadas por ejemplo:O(n log n), O(n2n), etc


Complejidad

Ejemplo:

for( i = 0; i < n; i++){for( k=0; k < n; k++){

Calcula /* complejidad O(n) */}

}

Por lo cual la complejidad es O(n3)

kl

n

lliki bac ,

1

0,, ∑

−

=

=


Complejidad

Propiedad aditiva: si el algoritmo tiene dos ciclos diferentes:

for( i = 0; i = n; i++){Calcula /* complejidad O(f(n)) */}for( k=0; k = m; k++){

Calcula /* complejidad O(g(m)) */}

Por lo cual la complejidad es O(f(n) + g(m))


Complejidad

Propiedad multiplicativa: si el algoritmo incluye ciclos anidados:

for( i = 0; i = n; i++){for( k=0; k = m; k++){

Calcula} /* complejidad O(g(m)) */

}

Por lo cual la complejidad es:

O(n g(m))


Abstracción de datos

Definición: Un tipo de dato es una colección de objetos y una colección de operadores que le pueden ser aplicados.

Ejemplo: Los datos de tipo entero consisten de los objetos

Int = {0, +1, -1, +2, -2, …. Imax, Imin} y {+, -, *, /, %, etc.}

Imax y Imin son los enteros que pueden ser representados en el sistema que se este usando.


Abstracción de datos

Una Estructura de Datos es la manera en que están organizados los datos Definición: un tipo de dato abstracto (ADT) es un tipo de dato organizado de tal manera que la especificación de los objetos y sus operaciones están separadas de la representación de los objetos.

Razón de ADT es que pueden usar cualquier maquina y lenguaje

Ejemplo: El ADT Set esta definido como varios números diferentes con operaciones que pueden incluir: Crear, Insertar, Remover, Unir, Insertar, etc.

Definición: Une estructura de datos es la manera en que los datos están organizados


Estructura de DatosUna estructura de datos puede implementarse en CEjemplo: Estructura de datos address

Hasta este punto no se han creado variables


Para declarar una variable info de address se escribe:

struct address info;

Para referenciar miembros de una estructura se usa el operador punto. Por ejemplo, para asignar el valor 10 al elemento number se escribe:

info.number = 10;

Para referenciar miembros declarados como cadenas de caracteres se usa el mismo operador punto.

info.city ;


Ejemplo: Para signar la cadena Hamilton a City

printf (“ Teclee Ciudad”);

gets (info.city);

Al ejecutar el programa si se teclea Hamilton, entonces se asignara el valor deseado a la variable


Arreglos y EstructurasArreglos como ADT

Matemáticamente, un arreglo de una dimensión es un vector:

a = [a0, a1, a2, …., an-1]T

Un arreglo de dos dimensiones es una matriz:


Arreglos y EstructurasObviamente, empilando las columnas de la matriz A en otro vector

b = [a0,0, a1,0, …., an-1,0, a0,1, …an-1,1, …, an-1,n-1 ]T

De esta manera un arreglo de dos dimensiones se representa como uno de una dimensión. Las variables no han cambiado, únicamente su especificación y la especificación de las operaciones.

⇒ Los arreglos son un ADT

En C, la declaración de un arreglo de una dimensión es:

Int list [5]; /* declaración de un arreglo de 5 enteros */

Int *plist; /* declaración de un arreglo de 5 apuntadores a enteros */


Arreglos y EstructurasInt list [5] define un arreglo de 5 enteros:

list[0], list[1], list[2], list[3], list[4]

De la misma manera Int *plist; define un arreglo de 5 apuntadores a enteros a

plist[0], plist[1], plist[2], plist[3], plist[4]

La dirección de list[0] se llama dirección de base.

Las variables list y plist[0] ambas designan la dirección de base de list[0]

list+i

Es un apuntador a list[i]


Arreglos y Estructuras¿list+i = plist[i]?

Si lo son ¿a que apuntan?

En general y sin importar el tipo del arreglo list[i],

list+i = &list[i]

*(list+i) = list[i]

Un arreglo de dos dimensiones se declara:

Int matr[10][10]

Arreglos de mas de dos dimensiones se declaran

Int mdarray[5][10][4][7];


Arreglos y EstructurasEstructuras

Las estructuras agrupan datos que pueden tener diferente tipo:

Ejemplo: estructura empleado

struct employee

{

char name[20];

int age;

float salary;

};




Ejemplo: estructura empleado

struct employee

{

char name[20]; /* tipo char */

int age; /* tipo int */

float salary; /* tipo float */

};




Ejemplo: estructura empleadostruct employee

{

char name[20]; /* tipo char */

int age; /* tipo int */

float salary; /* tipo float */

};

Una vez hecha la declaración es posible declarar variables (person) que contienen los tres tipos de datos diferentes.

struct employee person1, person2;


Arreglos y EstructurasUna vez hecha la declaración es posible declarar variables (person) que contienen los tres tipos de datos diferentes.

struct employee person1, person2;

Ahora si asignamos valores determinados a person1 la siguiente es posible

person2 = person1;

Que hace que todos los elementos de person2 tengan los mismos valores que los elementos de person1.


Arreglos y EstructurasEs posible definir arreglos de estructuras, declarando las variables de la estructura como variables. struct employee{char name[20]; int age;float salary;};Struct employee person[9]; /* arreglo de estructuras */Para seleccionar un elemento particular se utiliza el operador punto.


Arreglos y EstructurasEs posible definir arreglos de estructuras, declarando las variables de la estructura como variables. struct employee{char name[20]; int age;float salary;};Struct employee person[9]; /* arreglo de estructuras */Para seleccionar un elemento particular se utiliza el operador punto.


Arreglos y EstructurasEs posible incluir una estructura dentro de otra estructura:.

dateinfo es un nuevo Data Type, y es usado cuando la segunda estructura es definida.


Arreglos y EstructurasPara referenciar los miembros de la estructura received se usa el operador doble punto. Por ejemplo para la instancia letter anterior:

letter.date.dayletter.date.monthletter.date.year


Arreglos y EstructurasEstructuras auto referenciadas: Cuando una estructura contiene una o mas componentes los cuales son apuntadores a la misma estructura.


Arreglos y Estructuras


ADT Polinomio Considere el siguiente polinomio:

K gradoak coeficientes

Ejemplo:

A1(x) = 1+ 3x + 10x2 +4x3 + 2x4

A2(x) = 1+ 8x7 +2x100

Para almacenar estos polinomios es suficiente almacenar sus parámetros: coeficientes y grado


ADT Polinomio

Para almacenar los coeficientes, un arreglo 1D es útil

El segundo vector es ralo.

Si almacenamos los vectores en arreglos a1[4] y a2[100], el segundo polinomio que es ralo, desperdicia mucha memoria ya que se almacenan 97 ceros

6 ceros 92 ceros

A1(x) = 1+ 3x + 10x2 +4x3 + 2x4

A2(x) = 1+ 8x7 +2x100


ADT Polinomio Para solucionar este problema, podemos uara el ADT polinomio siguiente:

Con esta representación no es necesario almacenar información redundante, es decir los coeficientes cero


ADT Polinomio Implementación del ADT polinomio usando C:

N es el número de coeficientes diferentes de cero.


ADT Polinomio Es posible introducir arreglos de estructuras ADTpolinomio:

N es el número de coeficientes diferentes de cero y M es el número de polinomios.


ADT Polinomio

Para seleccionar y acceder una variable particular del arreglo de estructuras ADT polinomio, usamos el operador punto.

pol [i].coef[k]

pol [i].expon[k]

Con i=0, ….,M-1;k==,….,N-1


ADT Cadena Una cadena “string” es un arreglo de caracteres:

S = s0,s1, …, sN-1

Donde si son los caracteres tomados del conjunto de caracteres del lenguaje de programación.

Si N=0 entonces S es la cadena vacía.

En C, las cadenas son representadas como arreglos de caracteres que terminan con el carácter null o vació \0

Ejemplo: Representar la palabra “student” como una cadena


ADT Cadena

En C, la cadena anterior puede determinarse por:

char s[] = {“student”}

Para imprimirla en su totalidad

printf(“string =%s”,s);

Para imprimir cualquier elemento

printf(“s[i] = %c”, s[i]);

Cualquier iesimo carácter será impreso si 0 ≤ i ≤ 7


ADT Cadena

Concatenación de cadenas: para concatenar cadenas utilizamos la función strcat. Por ejemplo concatenar “good” y “student” e insertar el carácter espacio entre ellas:

char s[]= student;

char p[] = “good”;

strcat(p,s);

La cadena resultante “good student” queda almacenada en p[]


ADT Pilas y Colas

Una pila es un arreglo o lista con elementos ordenados en el cual todas las inserciones y borrados son realizados en un extremo llamado tope.

Dada una pila: S= [s0,s1,…,sn-1]

Tenemos: s0 elemento base o bottom

sn-1 elemento tope

si elemento al tope de si-1


ADT Pilas y Colas

Inserción y borrado de elementos de una pilaPush b Push c Push d Pop d Pop c


ADT Pilas y Colas

ADT cola: es un arreglo (lista) con elementos ordenados in el cual todas las inserciones toman lugar en un extremo llamado frente o cabeza y todas las eliminaciones en el otro extremo llamado trasero o cola

Dada una cola: Q = [q0, q1, …, qn-1]

Decimos por convención que: q0 frente o cabeza

qn-1 trasero o cola

in b in cin d

out out o


ADT Pilas y Colas

Ejemplo: Calendario de trabajo

Un típico ejemplo de uso de colas es la cola de trabajo de un sistema operativo con iguales prioridades.

Características de la cola de trabajo:● Los trabajos son procesados en el orden de llegada● Para eliminar trabajos posteriores, se deben eliminar los trabajos previos● Ya que los trabajos entran y dejan el sistema, la cola se recorre gradualmente a la derecha.● Cuando el tamaño máximo de la cola es alcanzado, la cola entera debe ser corrida a la izquierda, de tal manera que el índice del elemento frente se vuelva cero.


ADT Pilas y Colas

cabeza cola Comentarios


ADT Pilas y Colas

Ya que recorrer arreglos puede ser costoso por el tiempo que se consume, la lista circular puede ser una opción cuando el tiempo es muy importante.

Cola vacía Cola llena Cola llenaCola no vacía

Frente = 0Cola = 0

Frente = 5Cola = 4

Frente = 0Cola = 7

Frente = 0Cola = 3


ADT Pilas y Colas

J1, J2 y J3 se insertan

J1 y J2 se borran y J4,J5, J6 yJ7 se insertan

J8 y J9 se insertan

J3 y J4 se borran .


ADT Pilas y Colas

En una cola circular:

• Un elemento en blanco se deja para macar el frente

• La operación módulo se usa para transformar un arreglo convencional en una representación circular

• No es necesario correr la cola

La operación mod N es utilizada para denotar la extensión periódicaŷ[n] de la secuencia y[n]:

ŷ[n] = y[n mod N]


ADT Listas

Acerca de la representación secuencial

Para implementar colas y pilas empleamos arreglos y un mapeo secuencial. Sin embargo borrar e insertar con esta clase de mapeo es costoso en tiempo.

Una dificultad adicional resulta cuando tenemos que almacenar los mismos elementos usando diferentes tipos de ordenamiento (i.e. la lista de correos debe de almacenarse por fecha, por correspondiente, por tema, etc.) Si se almacenan usando estos criterios habrá un desperdicio de espacio. Por otra parte si los almacenamos en un solo arreglo entonces se tendrá que hacer un movimiento importante de datos, por lo cual tendremos un importante uso de tiempo.


ADT Listas Representación ligada

La representación ligada en comparación con la representación secuencial, no requieren que la representación de elementos sucesivos de una lista sean localizados uno después del otro en la memoria. La idea de la representación ligada es almacenar la dirección del siguiente elemento. De esta manera cada nodo de la lista contendrá dos elementos que son un valor y una dirección (apuntador) al siguiente elemento.

Operadores C:

& Operador dirección

* Operador de deferencia


ADT Listas

Tener más de una liga porInformación es posible. Por ejemplo: los e-mailsPueden ser ligados por Tamaño o fecha


ADT Listas Ejemplo simple con variable y su apuntador

int i, *pi; /* i es un entero, pi es un apuntador a entero */

i = 10; /* valor asignado a i directamente*/

pi = &i ; /* dirección de i asignada a pi */

*pi = 10; /*a valor asignado a i indirectamente */

Inserción y borrado

Tengamos los items a, b, c y d y la lista ligada [a, b, d]. Queremos insertarc entre b y d y luego borrar b.


ADT Listas


ADT Listas Ejemplo: Lista de enteros a, b, c:


ADT Listas

Lista final


ADT Listas Polinomios como listas ligadas

Deseamos representar el polinomio

como una lista ligada

Exponentes enterosCoeficientes no cero

Por ejemplo:


ADT Listas

Nodo de un polinomio

Representación polinomial


ADT Listas Listas doblemente ligadas

Listas ligadas tienen problemas porque solo facilitan su recorrido en la dirección de las ligas. Como hacer si nos localizamos en un nodo especifico de la lista y nos queremos mover al nodo precedente. Las listas doblemente ligadas ayudan a resolver este problema

nodo de una estructura doblemente ligada

Ejemplo de una lista doblemente ligada


ADT Árbol Los árboles son estructuras muy importantes pues reflejan alguna realidad

Árbol genealógico


ADT Árbol Terminología y Descripción:

Definición: Un árbol es un conjunto finito de uno más nodos tales que:

• Existe un nodo especial llamado raíz

• Los nodos restantes están divididos en n≥0 conjuntos disjuntos T1, ..Tndonde cada uno de estos conjuntos es un árbol y es llamado sub-árbol de la raíz.


ADT Árbol Terminología y Descripción:

Un nodo es la unidad de información y de ramas hacia otros nodos.

• El grado de un nodo es el número de sub-árboles de un nodo

• El grado de un árbol es el grado máximo de los nodos en el árbol

• La hoja o nodo Terminal es un nodo con grado cero

• El nivel de un nodo es definido permitiendo inicialmente que la raíz se encuentre al nivel uno

• El hijo de un nodo esta definido como la raíz (nodo) del sub-árbol

• La profundidad de un árbol es el nivel máximo de cualquier nodo en el árbol.


ADT Árbol raíz

rama

nodo

hoja

nivel


ADT Árbol

abuelo

padre

hijo

hermanos


ADT Árbol Ejemplo1: Aplicación de los árboles en codificación de fuente discreta.

Cuando los símbolos fuente no son igualmente probables, un método de codificación eficiente es usar un código de longitud variable. Donde los códigos más cortos de palabra son usados para codificar los símbolos más frecuentes. Está filosofía es usada en el código Morse también.


ADT Árbol Se necesita codificar y transmitir el siguiente texto que involucra cuatro símbolos a1, a2, a3, a4. Considere los siguientes tres códigos diferentes.


ADT Árbol El código 1 no es decodificable unívocamente ⇒ no es propio.

El código 2 es decodificable unívocamente e instantáneamente. Se puede representar este código a través de los nodos terminales del siguiente árbol

El código 3 es decodificable unívocamente, pero no es instantáneamente. Este tiene otra estructura de árbol.


ADT Árbol Otra manera de representación del código de palabras es embeberlas en un árbol completo. Por ejemplo: El código 2 puede ser embebido en el siguiente árbol binario:


ADT Árbol Representación de árboles en forma de lista.

Considere el árbol:

Representación en forma de lista.A[B[E, F[K, L]],C[G],D[H, I, J[M]]]


ADT Árbol Para su implantación necesitamos el concepto de ligas múltiples:

Por ejemplo para el nodo A anterior necesitamos:

Para cada nodo, podemos crear una representación similar y asírepresentar el árbol completo como una


ADT Árbol Por ejemplo, el arbol de grado dos:

Puede ser representado como la siguiente lista:


ADT Árbol Con la representación anterior, solo es posible moverse hacia abajo, es decir de padrea a hijos.

Para poderse mover en ambas direcciones, es necesario tener ligas de los padres a los hijos y también de los hijos a los padres ⇒ el uso de listas doblemente ligadas.

Por ejemplo para el nodo B, el elemento de lista doblemente ligada es:


ADT Árbol Otro ejemplo de árbol de grado 2

Corresponde la siguiente lista doblemente ligada.


ADT Árbol Representación Hijo Izquierdo-Hermano Derecho (LCRS) Tomando en cuenta el orden de los nodos/ramas del árbol. Observamos lo siguiente:• Cada nodo tiene solo un hijo mas a la izquierda y hermano mas a la derecha• Es apropiado seleccionar el orden de los nodos basándonos en como el dibujo del árbol.Por ejemplo, el árbol de la izquierda se puede re dibujar en la forma LCRS


ADT Árbol

Similarmente a la representación convencional en forma de listas para árboles, la representación LCRS puede también ser escrita en la forma de lista.

El elemento básico de lista ligada es:


ADT Árbol

Árbol Binario Definición: Un árbol binario es un conjunto finito de nodos que consitende una raíz y dos subárboles ordenadosObservaciones: • El grado de cualquier nodo no debe exceder dos• Para árboles binarios, distinguimos entre árboles derecho e izquierdo.Ejemplo: los dos árboles siguientes son diferentes.


ADT Árbol BinarioPropiedad 1: El número máximo de nodos en el nivel i de un árbol binario es 2 i-1

Propiedad 2: El número máximo de nodos en un árbol binario de profundidad k es 2k – 1

Nivel 1

Nivel 2

Nivel 3Profundidad = 3Número de nodos = 7


ADT Árbol Binario

Propiedad 3: Para cualquier árbol binario no vacío, si n0 es el número de nodos hoja y n2 es el número de nodos de grado 2, entonces:

n0 = n2 + 1Prueba: Sea n1 el número de nodos de grado uno y n el número total de nodos. Ya que el grado máximo de nodos es dos, tenemos:

n = n0 + n1 + n2 (1)Ahora, cuente el número de ramas nb. Observe que cualquier nodo

excepto la raíz corresponde a la rama que llega a el. De esta manera nb = n – 1 (2)


ADT Árbol Binario

Todas lar ramas inician únicamente de nodos de grado uno o dos, así:• Únicamente una rama se origina de un nodo de grado uno• Dos ramas se originan de nodos de grado dosPor lo que:

nb = n1 + 2n2 (3)De 2 y 3

n = nb + 1 = n1 + 2n2 + 1 (4)Restando 4 de 1, obtenemos finalmente:

0 = n0 + n1 + n2 – n1 -2n2 – 1= n0 – n2 -1 ⇒ n0 = n2 + 1 probado


ADT Árbol Binario

Nodos de grado 2

Nodos hoja


ADT Árbol Binario Problema: Suponga que tenemos k secuencias ordenadas en orden creciente. ¿Como unimos estas secuencias en una secuencia única ordenada?

Idea: Examinar las listas en paralelo y sacar el elemento más pequeñoy ponerlo al final de una nueva secuencia tota. Recorra las secuencias involucradas después de que cada elemento sea sacado.


ADT Árbol Binario

Basandonos en el concepto de árbol binario conmpleto, podemos representar un árbol por medio de un arreglo 1secuencial


ADT Árbol Binario

Basándonos en el concepto de árbol binario completo, podemos representar un árbol por medio de un arreglo 1D secuencial.

Obviamente esto se puede emplear para representar cualquier árbol binario completo.


ADT Árbol Binario

Representar árboles binarios completos con arreglos esta bien, sin embargo para árboles no llenos significa desperdicio de espació. En este caso la representación ligada es una buena opción.


ADT Árbol Binario

Representación con ligas de un nodo de árbol binarios


ADT Árbol Binario

Recorridos o visitas de árbol binario, consiste en visitar una sola vez cada nodo del árbol.Los recorridos son importantes para las operaciones de búsqueda, inserción y borrado.En el programa de recorrido de funciones, es deseable tratar todos los nodos de la misma manera.Definamos las siguientes operaciones:

V VisitarI Ve a la IzquierdaD Ve a la Derecha


ADT Árbol Binario

Existen seis posibles combinaciones para aplicar estas operaciones que son:{IVD, IDV, VID, VDI, DVI, DIV}Adoptando la convención de que siempre recorrer izquierda antes que derecha del conjunto anterior tenemos:{IVD, IRV, VID} que son los recorridos que conocemos

VID Pre-orden,IDV Post-ordenIVD En orden


ADT Árbol Binario

Pre-orden ABC ABDECFGPost-orden BCA DEBFGCAEn orden BAC DBEAFCG


ADT Árbol Binario

Los compiladores usan estructuras árbol para pre-procesar almacenar y calcular expresiones:

a - b(c / d + e / f)


ADT Árbol Binario

(a / b) cd + e

¿En orden?

a/b * c * d + e


ADT Árbol Binario

Definición: Un heap máximo es un árbol binario completo en el cual el valor de la llave de cualquier nodo no es mas pequeña que el valor de la llave de sus hijosDefinición: Un heap mínimo es un árbol binario completo en el cual el valor de la llave de cualquier nodo no es mas grande que el valor de la llave de sus hijos

Heap máximo Heap mínimo


ADT Árbol Binario

Ejercició: Implemente una cola de prioridades, en la cual se borra el elemento de máxima (mínima) prioridad, se pueda insertar un elemento de cualquier prioridad. De la complejidad de su algoritmo.

Inserción


Árbol Binario de Búsqueda

Definición: Un árbol binario de búsqueda es un árbol binario que satisface las siguientes propiedades:

• Todos los elementos tienen un identificador único.• Los identificadores del subárbol izquierdo deben ser menores que los identificadores del subárbol derecho. • Los identificadores del subárbol derecho deben ser mayores que el de la raíz.• Los subárboles izquierdo y derecho deben ser también árboles binarios de búsqueda.



Binario de búsqueda No binario de búsqueda

¿Por qué? 144


Árbol Binario de Búsqueda Búsqueda en un Árbol Binario:a) Compare el valor buscado a con el valor

del identificador de la raízb) Si la comparación es positiva termina la

búsqueda.a) Si a es mas pequeño que el valor del

identificador de la raíza) Moverse al siguiente nivel

izquierdob) Si a es más grande que el

identificador de la raíza) Moverse al siguiente nivel a la

derecha.


Árbol Binario de Búsqueda Inserción en un Árbol Binario:a) Busque en el árbol para asegurarse que

el elemento no está ya en el árbol.b) Si búsqueda es positiva no insertarc) En otro caso

a) Inserte a como el hijo derecho o izquierdo del nodo donde termino la búsqueda.


Árbol Binario de Selección Árbol de selección:Definición: Un árbol de selección es un árbol binario donde cada nodo

representa el más pequeño de sus dos hijos.Aplicaciones: Ordenamiento y selecciónConcepto: Involucrar los elementos de la secuencia ordenada en un

torneo de juego


Árbol Binario de Selección


Árbol Binario de SelecciónComplejidad

1 comparación

2 comparaciones

4 comparaciones

●●●

n/2 comparaciones


Árbol Binario de Seleccióncomplejidad total = 1 + 2 + 4 + 8 + …. + n/2

Esta es la progresión geométrica con p = log2n términos y q = 2 , con esto

ai = qai-1

La suma de la progresión geométrica a1, …ap esta dada por:

Sn =

Ahora, tomando en cuenta que a1 =1, q=2, y p = log2n podemos calcular la complejidad total como:

Complejidad total = 2log2n – 1 = n-1 = O(n)

a1 (qp - 1)q - 1


Árbol Binario de SelecciónProblema: suponga que tenemos K secuencias ordenadas en orden

decreciente. Como unir esas secuencias en una única secuencia ordenada?

Idea: Examinar toadas las secuencias en paralelo, y sacar al arreglo final el valor más pequeño, correr los elementos de la secuencia de donde se extrajo el elemento.



Secuencias originales Paso1: sacar 2 y correr la secuencia1.

Paso2: sacar 3 y correr la secuencia 4.

Paso3: sacar 5 y correr la secuencia2.









Paso11: sacar 40 y 65




Secuencias iniciales

Secuencia resultante.


Árbol Binario de SelecciónProblema: Usando los árboles de ordenamiento proponga un algoritmo

para realizar la tarea anterior.




Secuencias originales


























Proceso terminado


Árbol Binario de SelecciónLos árboles de selección pueden tener un grado mayor a 2.


BosquesDefinición: Un bosque es un conjunto de n ≥ 0 árboles disjuntos

Bosque de tres árboles


BosquesEl concepto de bosque esta fuertemente relacionado al de árbol ya que

si removemos la raíz de un árbol obtenemos un bosque.

El bosque anterior lo obtenemos eliminando la raíz de este árbol


BosquesOtro ejemplo, es eliminando un nodo diferente de la raíz.

Eliminando este nodo obtenemos un bosque


BosquesTransformación de un bosque en un árbol binario. Primero transforme cada árbol en la forma Hijo Izquierdo hermano derecho.


BosquesTransformación de un bosque en un árbol binario. Segundo: Los árboles transformados son ligados por medio del campo hermano del nodo raíz.


BosquesOtro ejemplo:

Primer paso:


BosquesOtro ejemplo:


Árboles y ConjuntosEl árbol puede ser empleado para representar conjuntos. Por simplicidad asumimos que incluirán números {0, 1, 2, 3, .. , n-1}

En la practica, estos números pueden ser los índices de una tabla de símbolos que almacenan algunos elementos reales.

Por ejemplo: si n=10 y consideramos tres conjuntos disjuntos:

S1 = {0, 6, 7, 8}

S2 = {1, 4, 9}

S3 = {2, 3, 5}

176

Date post:	16-Oct-2021
Category:	Documents
Upload:	others
View:	14 times
Download:	0 times

Estructura de Datos, Algoritmos y Matemáticas Discretas

Documents