Download UNIDAD III ESTRUCTURAS DE DATOS
Document related concepts
Transcript
Algoritmos avanzados Ing. Simón Onofre López UNIDAD III ESTRUCTURAS DE DATOS 3.1 CONCEPTOS FUNDAMENTALES 3.1.1 TIPOS DE DATOS Cualquier lenguaje suministra una serie de tipos de datos simples, como son los números enteros, caracteres, números reales. En realidad suministra un subconjunto de éstos, pues la memoria del ordenador es finita. Los punteros (si los tiene) son también un tipo de datos. El tamaño de todos los tipos de datos depende de la máquina y del compilador sobre los que se trabaja. En principio, conocer la representación interna de estos tipos de datos no es necesaria para realizar un programa, pero sí puede afectar en algunos casos al rendimiento. Por otra parte es posible definir otros tipos de estructuras de datos compuestos, entre las cuales se encuentran los arreglos, registros y otros. Los lenguajes de programación (LP) proporcionan herramientas para manejar distintos tipos de datos. Tipos predefinidos: proporcionados por el LP sólo nos preocupamos de su uso Tipos definidos por el usuario: Se puede elegir y definir una estructura de datos de las proporcionadas por el LP para su representación Se debe elegir y definir operaciones de manipulación Se debe garantizar el correcto comportamiento del tipo 3.1.2 ESTRUCTURA DE DATOS Se trata de un conjunto de variables de un determinado tipo agrupadas y organizadas de alguna manera para representar un comportamiento. Lo que se pretende con las estructuras de datos es facilitar un esquema lógico para manipular los datos en función del problema que haya que tratar y el algoritmo para resolverlo. En algunos casos la dificultad para resolver un problema radica en escoger la estructura de datos adecuada. Y, en general, la elección del algoritmo y de las estructuras de datos que manipulará estarán muy relacionadas. Según su comportamiento durante la ejecución del programa distinguimos estructuras de datos: o o Estáticas: su tamaño en memoria es fijo. Ejemplo: arrays. Dinámicas: su tamaño en memoria es variable. Ejemplo: listas enlazadas con punteros, ficheros, etc. Las estructuras de datos que trataremos aquí son los arrays, las pilas y las colas, los árboles, y algunas variantes de estas estructuras. 22 Algoritmos avanzados Ing. Simón Onofre López 3.1.3 TIPOS ABSTRACTOS DE DATOS Los tipos abstractos de datos (TAD) permiten describir una estructura de datos en función de las operaciones que pueden efectuar, dejando a un lado su implementación. Los TAD mezclan estructuras de datos junto a una serie de operaciones de manipulación. Incluyen una especificación, que es lo que verá el usuario, y una implementación (algoritmos de operaciones sobre las estructuras de datos y su representación en un lenguaje de programación), que el usuario no tiene necesariamente que conocer para manipular correctamente los tipos abstractos de datos. Se caracterizan por el encapsulamiento. Es como una caja negra que funciona simplemente conectándole unos cables. Esto permite aumentar la complejidad de los programas pero manteniendo una claridad suficiente que no desborde a los desarrolladores. Además, en caso de que algo falle será más fácil determinar si lo que falla es la caja negra o son los cables. Por último, indicar que un TAD puede definir a otro TAD. Por ejemplo, en próximos apartados se indicará como construir pilas, colas y árboles a partir de arrays y listas enlazadas. De hecho, las listas enlazadas también pueden construirse a partir de arrays y viceversa. 3.2 RECURSIVIDAD La recursión es una técnica para resolver problemas. Muchas veces resulta más fácil desarrollar un algoritmo recursivo que uno iterativo. Definición: Una función f es recursiva si en su cuerpo contiene una aplicación de f, es decir, si se puede activarse a si misma. Si la llamada sucede dentro de la propia función se dice que es directamente recursiva. En cambio si la función llama a otra y esta a su vez llama a la primera se dice que es recursión indirecta. El objetivo del programa recursivo, es realizar una serie de llamadas hasta que la secuencia se define en un punto. Las directrices para una función recursiva son: Cada vez que se hace una llamada recursiva en una función, el programa deberá comprobar que se satisface una condición básica con un determinado parámetro puesto al valor mínimo. Cada vez que se hace la llamada a la función, los parámetros enviados a la misma, deberán ser de algún modo más “simple”, es decir, su valor debe tender a la condición básica. Además por lo general en las funciones recursivas se suelen identificar dos casos: Caso base, que implica el caso de parada de la recursión Caso base, que implica realizar las llamadas recursivas 23 Algoritmos avanzados Ing. Simón Onofre López Ejemplo La función Factorial puede ser desarrollada iterativamente o recursivamente1. Matemáticamente de define como: 1 n! n(n 1) si n 0 ó 1 si n 1 Análogamente su expresión funcional será la siguiente: si n 0 ó 1 1 fac(n) n * fac(n 1) si n 1 Codificación Como función la codificación es la siguiente: Private Function factorial(ByVal n As Integer) As Integer If n = 1 Then factorial = 1 Else factorial = n * factorial(n - 1) End If End Function Prueba Para N=5 Llamadas recursiva Factorial(5)=factorial(4)*5 Factorial(4)=factorial(3)*4 Factorial(3)=factorial(2)*3 Factorial(2)=factorial(1)*2 Factorial(1)=1 Evaluación de resultados Factorial(1)=1 Factorial(2)=factorial(1)*2 = Factorial(3)=factorial(2)*3 = Factorial(4)=factorial(3)*4 = Factorial(5)=factorial(4)*5 = 1*2 =2 2*3 =6 6*4 =24 24*5 =120 24 Algoritmos avanzados Ing. Simón Onofre López Como procedimiento se tiene la siguiente codificación: Private Sub fac(ByVal n As Integer, ByRef resul As Integer) Dim resp_aux As Integer If n = 1 OR n = 0 Then resul = 1 Else fac n - 1, resp_aux resul = resp_aux * n End If End Sub Ejemplo: Otro ejemplo clásico es la secuencia de fibonacci cuyos términos son 1, 1, 2, 3, 5, 8, ... los cuales se determinan por la función: Expresión funcional si n 1 ó 2 1 fib(n) fib(n 1) fib(n 2) si n 2 Codificación Private Function fibonacci(ByVal n As Integer) As Integer If n = 0 Or n = 1 Then fibonacci = 1 Else fibonacci = fibonacci(n - 1) + fibonacci(n - 2) End If End Function Prueba Para fib(5) se tienen las siguientes entradas y salidas. Llamadas recursiva Fibonacci(5)=fibonacci(4)+ fibonacci(3) Fibonacci(4)=fibonacci(3)+ fibonacci(2) Fibonacci(3)=fibonacci(2)+ fibonacci(1) Fibonacci(2)=1 Fibonacci(1)=1 Evaluación de resultados Fibonacci(1)=1 Fibonacci(2)=1 Fibonacci(3)=fibonacci(2)+ fibonacci(1)=1+1=2 Fibonacci(4)=fibonacci(3)+ fibonacci(2)=2+1=3 Fibonacci(5)=fibonacci(4)+ fibonacci(3)=3+2=5 25 Algoritmos avanzados Ing. Simón Onofre López En este caso se puede observar que la solución planteada de fibonacci es impracticable para valores de n grandes. Cada fibonacci() realiza dos llamadas, por lo que el número de llamadas aumenta en proporción geométrica. ¿ Conviene usar recursión siempre?¿ Qué pasa con la memoria? Veamos el caso de implementar la misma secuencia de fibonacci iterativamente: Private Function fiboRec(ByVal n As Integer) As Integer Dim a As Integer, b As Integer, c As Integer, i As Integer a = 0 b = 1 c = 1 Print c For i = 2 To n c = a + b Print c a = b b = c Next i fiboRec = c End Function EL lector podrá verificar la eficiencia de la versión recursiva con respecto de la iterativa 3.2.1 EJERCICIOS RESUELTOS Ejercicio 1 Multiplicar dos números por sumas sucesivas Solución Como es sabido, “la multiplicación es una suma abreviada”, en tal sentido se puede realizar la operación de la siguiente forma: A*B = A+A+A+ . . . . . . . . . +A , Es decir sumar A, B veces Entonces para el caso general: A * B Multi( A, B) i 1 A i 1 A A B B 1 Es decir A*B se puede expresar como la sumatoria desde 1 hasta B de A, lo cual si se saca de la expresión al último termino, el resto continua siendo sumatoria. 26 Algoritmos avanzados Ing. Simón Onofre López El caso base es mucho más simple, nos preguntamos cuál es el valor más qequeño que puede toma B, para que el resultado sea trivial, es posible elegir entre las siguientes alternativas O A*B=A cuando B=1 A*B=0 cuando B=0 Cualquiera de estas expresiones puede representar al caso base. Expresión funcional si B 1 A Multi ( A, B) Multi ( A, B 1) A si B 1 Algoritmo Private Function multiplica(ByVal A As Integer, ByVal B As Integer) As Integer If B = 1 Then multiplica = A Else multiplica = multiplica(A, B - 1) + A End If End Function 27 Algoritmos avanzados Ing. Simón Onofre López Codificación completa Option Explicit Dim num As Integer Dim num2 As Integer Private Function multiplica(ByVal A As Integer, ByVal B As Integer) As Integer If B = 1 Then multiplica = A Else multiplica = multiplica(A, B - 1) + A End If End Function Private Sub Command1_Click() num = Val(Text1.Text) num2 = Val(Text2.Text) MsgBox "El resulatdo es " & multiplica(num, num2), vbCritical, "RESULTADO" End Sub Private Sub Command2_Click() End End Sub Private Sub Text1_KeyPress(KeyAscii As Integer) Select Case KeyAscii Case 13 Text2.SetFocus Case Asc(0) To Asc(9) Case Else KeyAscii = 0 End Select End Sub 28 Algoritmos avanzados Ing. Simón Onofre López Private Sub Text2_KeyPress(KeyAscii As Integer) Select Case KeyAscii Case 13 Command1.SetFocus Case Asc(0) To Asc(9) Case Else KeyAscii = 0 End Select End Sub Ejercicio 2 intercalar los dígitos de dos números, los números tiene la misma longitud. Solución La función modulo nos permite sacar el último digito de cada número y componer un nuevo numero, cuando numA y numB sean de un solo dígito, es decir menores a 10 se habrá llegado al caso base. Expresión funcional si A 10 ó B 10 A *10 B Intercala ( A, B) Intercala ( Adiv10, Bdiv10) *100 ( A mod 10) *10 ( B mod 10) eoc Algoritmo Private Function intercala(ByVal numA As Integer, ByVal numB As Integer) As Double Dim ma As Integer, mb As Integer, nuevoNum As Integer If numA < 10 Then intercala = numA * 10 + numB Else ma = numA Mod 10 mb = numB Mod 10 nuevoNum = ma * 10 + mb intercala = intercala(numA \ 10, numB \ 10) * 100 + nuevoNum End If End Function Prueba Intercala(345,796) = Intercala(34,79)*100 + 56 =3749*100 + 56 = 374956 Intercala(34,79) Intercala(3,7) = Intercala(3,7)*100 + 49 = 37*100 +49 = 3749 = 37 29 Algoritmos avanzados Ing. Simón Onofre López Ejercicio 3 Hallar la sumatoria de los N primero números pares Solución La sumatoria de los n primero números pares está dada por: SumaPares(n) = 2 + 4 + 6 + . . . . . .+ 2*(n-1) + 2*n Sacando el ultimo elemento de la sumatoria, logramos identificar el caso general: SumaPares(n) = SumaPares(n-1)+ 2*n Para el caso general, se considera que valor debe tomar n para generar el primer numero par. Algoritmo Private Function sumaPares(n As Integer) If n = 1 Then sumaPares = 2 Else sumaPares = sumaPares(n - 1) + 2 * n End If End Function Codificación completa Option Explicit Dim num As Integer Private Function sumaPares(ByVal n As Integer) As Integer If n = 1 Then sumaPares = 2 List1.AddItem 2 Else sumaPares = sumaPares(n - 1) + 2 * n List1.AddItem (2 * n) End If End Function 30 Algoritmos avanzados Ing. Simón Onofre López Private Sub Form_Load() Option1.Value = False Option2.Value = True End Sub Private Sub Option1_Click() num = Val(Text1.Text) MsgBox sumaPares(num), vbExclamation End Sub Private Sub Option2_Click() Text1 = "" List1.Clear End Sub Private Sub Option3_Click() End End Sub Ejercicio 4 naturales. Ejemplo: N=1 N=2 N=3 Dado un número entero generar otro número solo compuesto por los números genera genera genera 1 12 123 Expresión funcional si n 1 1 Genera(n) Genera(n 1) *10 n si n 1 Algoritmo Prueba Private Function genera(ByVal n Integer) As Double If n = 1 Then genera = 1 Else genera = genera(n - 1) * 10 + n End If End Function As Para n=5 31 Algoritmos avanzados Ing. Simón Onofre López Llamadas recursiva genera(5) = genera(4) 5 genera(4) = genera(3) 4 genera(3) = genera(2) 3 genera(2) = genera(1) 2 genera(1) = 1 Evaluación de resultados * 10 + genera(1) = 1 genera(2) = genera(1) * 10 + 2 = 1*10+2 = 12 * 10 + genera(3) = genera(2) * 10 + 3 = 12*10+3=123 genera(4) = genera(3) * 10 + 4 = 123*10+4=1234 * 10 + genera(5) = genera(4) * 10 + 5 = 1234*10+5= .....................12345 * 10 + Ejercicio 5 Invertir un vector Solución ini fin 1 2 3 4 5 6 7 La solución consiste en cambiar el primer V(ini) y último V(fin) elementos usando un auxiliar: aux = v(ini) v(ini) = v(fin) v(fin) = aux luego realizar la llamada recursiva de manera de cambiar el segundo V(ini+1) con el penúltimo V(fin-1) elemento: Invierte ini + 1, fin - 1 el proceso se repite mientras ini sea menor o igual que fin. Algoritmo Private Sub Invierte(ByVal ini As Integer, ByVal fin As Integer) Dim aux As Integer If ini < fin Then aux = v(ini) v(ini) = v(fin) v(fin) = aux Invierte ini + 1, fin - 1 End If End Sub Codificación completa 32 Algoritmos avanzados Ing. Simón Onofre López Dim tam As Integer Dim v(1 To 10) As String Private Sub LlenaVector(ByVal n As Integer) Dim i As Integer List1.Clear For i = 1 To n v(i) = InputBox("Ingrese el elemento V[" & i & "] =>", "Ingreso de datos al Vector", 0) List1.AddItem v(i) Next End Sub Private Sub MostrarLista2(ByVal n As Integer) Dim i As Integer List2.Clear For i = 1 To n List2.AddItem v(i) Next End Sub Private Sub Invierte(ByVal ini As Integer, ByVal fin As Integer) Dim aux As String If ini < fin Then aux = v(ini) v(ini) = v(fin) v(fin) = aux Invierte ini + 1, fin - 1 End If End Sub Private Sub Command1_Click() tam = Val(InputBox("Ingrese tamaño del vector ", "TAMAÑO DEL VECTOR", 0)) LlenaVector tam End Sub 33 Algoritmos avanzados Ing. Simón Onofre López Private Sub Command2_Click() Invierte 1, tam MostrarLista2 tam End Sub Private Sub Command3_Click() End End Sub 3.3 ARREGLOS Supongamos que nos enfrentamos a un problema como este: “Una empresa que cuenta con 150 empleados, desea establecer una estadística sobre los salarios de sus empleados, y quiere saber cual es el salario promedio, y también cuantos de sus empleados gana entre $1250.00 y $2500.00”. Si tomamos la decisión de tratar este tipo de problemas con datos simples, pronto nos percataríamos del enorme desperdicio de tiempo, almacenamiento y velocidad. Es por eso que para situaciones de este tipo la mejor solución son los datos estructurados. Un arreglo puede definirse como un grupo o una colección finita, homogénea y ordenada de elementos. Los arreglos pueden ser de los siguientes tipos: o o o De una dimensión. De dos dimensiones. De tres o más dimensiones 3.4 PILAS Una pila (stack) es una colección ordenada de elementos en la cual se pueden insertar nuevos elementos por un extremo y se pueden retirar otros por el mismo extremo; ese estremos se llama ``la parte superior'' de la pila. 34 Algoritmos avanzados Ing. Simón Onofre López Si tenemos un par de elementos en la pila, uno de ellos debe estar en la parte superior de la pila, que se considera ``el más alto'' en la pila que el otro. En la figura 3.1 el elemento F es el más alto de todos los elementos que están en la pila. El elemento D es el más alto de los elementos A,B,C, pero es menor que los elementos E y F. Figura 3.1: Pila con 6 elementos Para describir cómo funciona esta estructura, debemos agregar un nuevo elemento, el elemento G. Después de haber agregado el elemento G a la pila, la nueva configuración es la que se muestra en la figura 3.2 Figura 3.2: Operación de insertar el elemento G en la pila P De acuerdo con la definición, existe solamente un lugar en donde cualquier elemento puede ser agregado a la pila. Después de haber insertado el nuevo elemento, G ahora es el elemento en la cima. Debemos aclarar en qué pila deseamos insertar elementos, puesto que es posible tener más de una pila al mismo tiempo. Cuando se desea retirar un elemento de la pila, solo basta ordenar que sea retirado un elemento; no podemos decir ``retira C de la pila'', porque C no está en la cima de la pila y solamente podemos retirar el elemento que está en la cima. Para que la sentencia ``retira C de la pila'' tenga sentido, debemos replantear las órdenes a algo como: Retira de la pila hasta que el elemento retirado sea C. Y solamente se puede sacar un elemento a la vez. Siguiendo nuestro ejemplo, ahora deseamos retirar de la pila P. La configuración global de la pila es como se muestra en la figura 3.3 35 Algoritmos avanzados Ing. Simón Onofre López Figura 3.3: Operación de retirar de la pila P El concepto de pila es muy importante en computación y en especial en teoría de lenguajes de programación. En lenguajes procedurales como Pascal o C, la pila es una estructura indispensable, debido a las llamadas a función. Resulta que el flujo de instrucciones va de arriba hacia abajo, y cuando ocurre una llamada a alguna función, el estado global del sistema se almacena en un registro y éste en una pila. Así que la pila va a contener todas las llamadas a procedimientos que se hagan. Cuando se termina de ejecutar algún procedimiento, se recupera el registro que está en la cima de la pila. En ese registro están los valores de las variables como estaban antes de la llamada a la función, o algunas pueden haber cambiado si valor, dependiendo del ámbito de las variables. Cada elemento en la pila que es retirado, significa que se ha terminado de ejecutar alguna función. Cuando se termina de ejecutar el programa, la pila de llamadas a subprogramas debe haber quedado en 0 también, de otro modo podría causar algun tipo de error. La manera en cómo entran los datos a la estructura de datos y cómo salen, se denomina fifo, que viene del ingés first in first out (primero en entrar, primero en salir). 3.5 COLAS Las colas son una estructura de datos similar a las pilas. Recordemos que las pilas funcionan en un depósito en donde se insertan y se retiran elementos por el mismo extremo. En las colas sucede algo diferente, se insertan elementos por un extremo y se retiran elementos por el otro extremo. De hecho a este tipo de dispositivos se les conoce como dispositivos ``fifo'' (first in, first out) porque funcionan como una tubería, lo que entra primero por un extremo, sale primero por el otro extremo. En una cola hay dos extremos, uno es llamado la parte delantera y el otro extremo se llama la parte trasera de la cola. En una cola, los elementos se retiran por la parte delantera y se agregan por la parte trasera. 36 Algoritmos avanzados Ing. Simón Onofre López Figura 3.4: Dinámica de una cola. a) estado actual con una cola con tres elementos a,b,c; b) estado de la cola cuando se agrega el elemento d; c) estado de la cola cuando se elimina el elemento a del frente de la cola En la figura 3.4 se muestra una actividad típica de la cola, en donde se muestra que se agregan datos por la parte trasera de la cola y se eliminana datos por el frente de la cola. Si Q es una cola y x es un elemento, se pueden hacer tres operaciones básicas con las colas: o insert(Q,x), que inserta el elemento x en la parte trasera de la cola Q. o x=remove(Q), que almacena en x el valor del elemento retirado de la parte frontal de la cola Q. o empty(Q), que es un predicado de valor booleano, y es true cuando la cola Q tiene 0 elementos, y es false cuando la cola Q tiene al menos un elemento, en cuyo caso, ese único elemento es la parte frontal y la parte trasera de la cola al mismo tiempo. Teóricamente no hay límite para el tamaño de la cola, asi que siempre se debería poder insertar elementos a una cola, sin embargo, al igual que las pilas, normalmente se deja un espacio de memoria para trabajar con esta estructura. Por el contrario, la operación remove solamente se puede hacer si la cola no está vacía. 3.6 LISTAS Una lista es una estructura de datos secuencial. Una manera de clasificarlas es por la forma de acceder al siguiente elemento: o o lista densa: la propia estructura determina cuál es el siguiente elemento de la lista. Ejemplo: un array. lista enlazada: la posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posición de memoria del primer elemento. Además es dinámica, es decir, su tamaño cambia durante la ejecución del programa. 37 Algoritmos avanzados Ing. Simón Onofre López Una lista enlazada o encadenada es una colección de elementos ó nodos, en donde cada uno contiene datos y un enlace o liga. Un nodo es una secuencia de caracteres en memoria dividida en campos (de cualquier tipo). Un nodo siempre contiene la dirección de memoria del siguiente nodo de información si este existe. Un apuntador es la dirección de memoria de un nodo La figura siguiente muestra la estructura de un nodo: El campo liga, que es de tipo puntero, es el que se usa para establecer la liga con el siguiente nodo de la lista. Si el nodo fuera el último, este campo recibe como valor NIL (vacío). A continuación se muestra el esquema de una lista : 3.7 ÁRBOLES 3.7.1 ÁRBOLES BINARIOS A los árboles ordenados de grado dos se les conoce como árboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los árboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos. 3.7.1.1 Representación La representación gráfica de un árbol binario es la siguiente: Hay dos formas tradicionales de representar un árbol binario en memoria: 38 Algoritmos avanzados o o Ing. Simón Onofre López Por medio de datos tipo punteros también conocidos como variables dinámicas o listas. Por medio de arreglos. Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras. Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión. Cada nodo se representa gráficamente de la siguiente manera: 3.7.1.2 Clasificación de Árboles Binarios Existen cuatro tipos de árbol binario:. a. b. c. d. B. Distinto. B. Similares. B. Equivalentes. B. Completos. A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos. a. A. B. DISTINTO Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo: b. A. B. SIMILARES Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente. Ejemplo: 39 Algoritmos avanzados Ing. Simón Onofre López c. A. B. EQUIVALENTES Son aquellos árboles que son similares y que además los nodos contienen la misma información. Ejemplo: d. A. B. COMPLETOS Son aquellos árboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho. 3.7.1.3 Recorrido de un Arbol Binario Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación: INORDEN Recorrer el subarbol izquierdo en inorden. Examinar la raíz. Recorrer el subarbol derecho en inorden. PREORDEN Examinar la raíz. Recorrer el subarbol izquierdo en preorden. recorrer el subarbol derecho en preorden. POSTORDEN Recorrer el subarbol izquierdo en postorden. Recorrer el subarbol derecho en postorden. Examinar la raíz. A continuación se muestra un ejemplo de los diferentes recorridos en un árbol binario. Inorden: GDBHEIACJKF Preorden: ABDGEHICFJK Postorden: GDHIEBKJFCA 40 Algoritmos avanzados Ing. Simón Onofre López 3.7.1.4 Árboles Enhebrados Existe un tipo especial de árbol binario llamado enhebrado, el cual contiene hebras que pueden estar a la derecha o a la izquierda. El siguiente ejemplo es un árbol binario enhebrado a la derecha. ARBOL ENHEBRADO A LA DERECHA. Este tipo de árbol tiene un apuntador a la derecha que apunta a un nodo antecesor. ARBOL ENHEBRADO A LA IZQUIERDA. Estos árboles tienen un apuntador a la izquierda que apunta al nodo antecesor en orden. 3 .7.1.5 Árboles binarios de búsqueda Un árbol de búsqueda binaria es una estructura apropiada para muchas de las aplicaciones que se han discutido anteriormente con listas. La ventaja especial de utilizar un árbol es que se facilita la búsqueda. Un árbol binario de búsqueda es aquel en el que el hijo de la izquierda (si existe) de cualquier nodo contiene un valor más pequeño que el nodo padre, y el hijo de la derecha (si existe) contiene un valor más grande que el nodo padre. Un ejemplo de árbol binario de búsqueda es el siguiente: 41 Algoritmos avanzados Ing. Simón Onofre López 3.7.2 ÁRBOLES GENERALES Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación . Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos. Los árboles pueden ser construidos con estructuras estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas. La definición de árbol es la siguiente: es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ansestro, etc.. Formalmente se define un árbol de tipo T como una estructura homogénea que es la concatenación de un elemento de tipo T junto con un número finito de arboles disjuntos, llamados subarboles. Una forma particular de árbol puede ser la estructura vacía. La figura siguiente representa a un árbol general. Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente de los mismos. Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro. 3.7.2.1 Terminología La terminología que por lo regular se utiliza para el manejo de arboles es la siguiente: 42 Algoritmos avanzados o o o o o o o o o o o Ing. Simón Onofre López HIJO. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y. PADRE. X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y. HERMANO. Dos nodos serán hermanos si son descendientes directos de un mismo nodo. HOJA. Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos). NODO INTERIOR. Es un nodo que no es raíz ni terminal. GRADO. Es el número de descendientes directos de un determinado nodo. GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol. NIVEL. Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1. ALTURA. Es el máximo número de niveles de todos los nodos del árbol. PESO. Es el número de nodos del árbol sin contar la raíz. LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente. 3.7.2.2 Transformación de un Árbol Gral. en un Árbol Binario. En esta sección estableceremos los mecanismos necesarios para convertir un árbol general en un árbol binario. Para esto, debemos seguir los pasos que se describen a continuación: o o o Enlazar los hijos de cada nodo en forma horizontal (los hermanos). Enlazar en forma vertical el nodo padre con el nodo hijo que se encuentra más a la izquierda. Además, debe eliminarse el vínculo de ese padre con el resto de sus hijos. Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda, y así se obtendrá el árbol binario correspondiente 3.8 GRAFOS Un grafo dirigido G consiste en un conjunto de vértices V y un conjunto de arcos o aristas A. Los vertice se denominan también nodos o puntos. Un arco, es un par ordenado de vértices(V,W) donde V es el vértice inicial y W es el vértice terminal del arco. Un arco se expresa como: V-->W y se representa de la siguiente manera: Los vértice de un grafo pueden usarse para representar objetos. Los arcos se utilizan para representar relaciones entre estos objetos. Las aplicaciones más importantes de los grafos son las siguientes: o o o Rutas entre ciudades. Determinar tiempos máximos y mínimos en un proceso. Flujo y control en un programa. 43 Algoritmos avanzados Ing. Simón Onofre López 3.8.1 TERMINOLOGIA o La terminología que manejaremos regularmente para el uso de grafos es la siguiente: o CAMINO.Es una secuencia de vértices V1, V2, V3, ... , Vn, tal que cada uno de estos V1->V2, V2->V3, V1->V3. o LONGITUD DE CAMINO. Es el número de arcos en ese camino. o CAMINO SIMPLE. Es cuando todos sus vértices, excepto tal vez el primero y el último son distintos. o CICLO SIMPLE. Es un camino simple de longitud por lo menos de uno que empieza y termina en el mismo vértice. o ARISTAS PARALELAS. Es cuando hay más de una arista con un vértice inicial y uno terminal dados. o GRAFO CICLICO. Se dice que un grafo es cíclico cuando contiene por lo menos un ciclo. o GRAFO ACICLICO. Se dice que un grafo es aciclíco cuando no contiene ciclos. o GRAFO CONEXO. Un grafo G es conexo, si y solo si existe un camino simple en cualesquiera dos nodos de G. o GRAFO COMPLETO ó FUERTEMENTE CONEXO.Un grafo dirigido G es completo si para cada par de nodos (V,W) existe un camino de V a W y de W a V (forzosamente tendrán que cumplirse ambas condiciones), es decir que cada nodo G es adyacente a todos los demás nodos de G. o GRAFO UNILATERALMENTE CONEXO.Un grafo G es unilateralmente conexo si para cada par de nodos (V,W) de G hay un camino de V a W o un camino de W a V. o GRAFO PESADO ó ETIQUETADO. Un grafo es pesado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso. o VERTICE ADYACENTE. Un nodo o vértice V es adyacente al nodo W si existe un arco de m a n. o GRADO DE SALIDA.El grado de salida de un nodo V de un grafo G, es el número de arcos o aristas que empiezan en V. o GRADO DE ENTRADA.El grado de entrada de un nodo V de un grafo G, es el número de aristas que terminan en V. o NODO FUENTE.Se le llama así a los nodos que tienen grado de salida positivo y un grado de entrada nulo. o NODO SUMIDERO.Se le llama sumidero al nodo que tiene grado de salida nulo y un grado de entrada positivo. 3.8.2 EJEMPLOS DE GRAFOS 081.- Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular. Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular 44 Algoritmos avanzados Ing. Simón Onofre López 2.- Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es 3.- Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn. A continuación pueden verse los dibujos de K3, K4, K5 y K6 Todo grafo completo es regular porque cada vértice tiene grado |V|-1 al estar conectado con todos los otros vértices. Un grafo regular no tiene por qué ser completo. 4.- Un grafo bipartido regular se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices. A continuación ponemos los dibujos de K1,2, K3,3, y K2,5 45 Algoritmos avanzados Ing. Simón Onofre López 3.8.3 REPRESENTACION DE GRAFOS 46