Teoría de Estructuras de Datos (Copia) PDF

Factores de Calidad:  Factores externos: cualidad del software que puede ser detectada por un usuario (sin conocer el código fuente).  Factores internos: cualidad del software que puede ser percibida por el programador (conociendo el código fuente).  Correctitud...

Factores de Calidad:  Factores externos: cualidad del software que puede ser detectada por un usuario (sin conocer el código fuente).  Factores internos: cualidad del software que puede ser percibida por el programador (conociendo el código fuente).  Correctitud: el programa respeta la especificación (para una entrada dada produce la salida esperada).  Robustez: el programa es capaz de manejar entradas no contempladas por la especificación (se espera que se degrade graciosamente). Ejemplo: recibe un entero negativo cuando espera un positivo. Crítica en situaciones industriales.  Extensibilidad: capacidad de agregarle funcionalidad al software.  Portabilidad: habilidad del software con mínimo cambio en otro hardware o sistema operativo.  Reusabilidad: capacidad de usar el código en la construcción de otros programas.  Eficiencia: capacidad del software de requerir pocos recursos de computo (tiempo de CPU y memoria).  Facilidad de uso: capacidad del software para ser usador por usuarios con distinta habilidad. Excepciones: Las excepciones son eventos inesperados que ocurren durante la ejecución de un programa. Puede ser resultado de una condición de error o una entrada incorrecta. En POO las excepciones son objetos “lanzados” por un código que detecta una condición inesperada. Las excepciones “capturadas” por otro código que repara la situación (o el programa termina con error en ejecución). En Java las excepciones son subclases de la clase Exception. Los métodos deben especificar en su signatura las excepciones que pueden lanzar. Una excepción se lanza desde una sentencia “throw” void método( parámetros formales ) { try { ……. sentencia_que_puede_producir_excepción(); ……. } catch( tipo_excepcion e ) { código para manejar la excepción e } Finally { codigo que siempre se ejecuta } } Interfaces: Una interfaz es una colección de declaraciones de métodos (y sin atributos) que luego van a ser implementados por una o más clases. Una clase que implementa una interfaz debe implementar todos los métodos provistos por la interfaz. Clases Wrapper: En ocasiones es muy convenientes tratar a los datos primitivos (int, boolean, etc) como objetos. Las clases wrapper se usan como cualquier otra. Genericidad: Una clase genérica permite encapsular una estructura cuyo comportamiento es independiente del tipo de las componentes. Permite definir esquemas de clases que pueden instanciarse de varias maneras.  Genericidad paramétrica: un tipo genérico es un tipo que no es definido en compilación sino en tiempo de ejecución y permite definir una clase en fusión de parámetros formales de tipo que abstraen los tipos de algunos datos internos de una clase. Dada una clase genérica vamos a instanciar algunos objetos usando parámetros actuales de tipo. Estructuras de Datos: Una estructura de datos es una forma de organizar un conjunto de datos (elementales o no). Cada una de las unidades que la componen se denomina celda. En general se accede a la estructura de datos globalmente o a cada una de las celdas que la componen en forma particular. Así como las estructuras de datos se crean con el objetivo de facilitar la manipulación de datos individualmente como un todo. Desde la perspectiva de su representación en memoria, una estructura de datos es una colección de variables organizadas de alguna manera. Algoritmo: Un algoritmo es una secuencia de pasos que al ejecutarse permiten realizar una tarea en una cantidad finita de tiempo. Tiempo de ejecución: Es el tiempo de corrida de un programa sobre una maquina en particular y para una determinada muestra de datos de entrada.  Orden de tiempo: Es una función T(n) que se asocia al programa (n = tamaño de entrada). Esta función representa el número de instrucciones ejecutarse sobre una maquina ideal. Las ventajas de esta función son: Se independiza la evolución de aspectos ajenos al algoritmo y puede calcularse sobre el algoritmo sin necesidad de implementarlo previamente. El tiempo de ejecución de un algoritmo depende de la cantidad de operaciones primitivas realizadas, estas toman tiempo constantes (arbitrario) porque dependes del compilador y hardware subyacente.   Notación asintótica (Big-Oh): sean F(n) y G(n) dos funciones de los naturales a los reales, F(n) es O(G(n)) si y solo si existe un c real mayor que 0 y un n0 natural mayor que 1 tales que F(n)=n0 (se lee F(n) es big-oh de G(n) o F(n) es orden de G(n))  Regla de la suma: Si f1(n) es O(g1(n)) y f2(n) es O(g2(n)) entonces f1(n) + f2(n) es O(max(g1(n),g2(n)).  Regla del producto: Si f1(n) es O(g1(n)) y f2(n) es O(g2(n)) entonces f1(n)*f2(n) es O(g1(n)*g2(n)).  Big‐Omega: Sean f(n) y g(n) funciones de los naturales en los reales. f(n) es Ω(g(n)) ssi existen c real positivo y n0 natural tales que f(n) ≥ cg(n) para todo n ≥ n0.  Big‐Theta: Sean f(n) y g(n) funciones de los naturales en los reales. f(n) es ϴ(g(n)) ssi f(n) es (g(n)) y f(n) es Ω(g(n)). Nota: Big‐Theta quiere decir c1g(n) ≤ f(n) ≤ c2g(n)  Reglas para calcular T(n) a partir del código fuente de un algoritmo: Paso 1: Determinar el tamaño de la entrada n. Paso 2: Aplicar las siguientes reglas en forma sistemática: TP(n) = constante si P es una acción primitiva TS1;…;Sn(n) = TS1(n) + … + TSn(n) Tif B then S1 else S2(n) = TB(n) + max(TS1(n),TS2(n)) Tfor(m;S)(n)=m*TS(n) donde m=cant_iteraciones(for(m;S)) Twhile B do S (n)=m*(TB(n) + TS(n)) donde m=cant_iteraciones(while B do S) Tcall P(n) = TS(n) donde procedure P; begin S end Tf(e)(n) = Tx:=e(n) + TS(n) donde function f(x); begin S end  Cálculo de tiempo de algoritmo recursivo: Paso 1: Determinar la entrada Paso 2: Determinar el tamaño de la entrada Paso 3: Definir una recurrencia para T(n) Paso 4: Obtener una definición no recursiva para T(n) Paso 5: Determinar orden de tiempo de ejecución Paso 6: Hacer prueba por inducción para ver que las expresiones para T(n) de (3) y (4) son equivalentes. ED - Arreglos y listas: Secuencias: Una secuencia de elementos [a1,a2,…,an] tiene: - Una longitud n - Primer elemento (a 1) - Cada elemento ai (i=2,…,n-1) tiene siguiente a i-1 - Cada elemento ai(i=2,…,n) tiene previo a i+1 - Los elementos son homogéneos (del mismo tipo) Formas de representar una secuencia: - Arreglos - Archivos - Lista enlazada Secuencia: Implementación con arreglo Ventajas: El arreglo reside en memoria principal. El arreglo es homogéneo. Recuperar una componente toma orden uno. Desventajas: El arreglo tiene un tamaño máximo. Insertar un elemento tiene orden lineal en la cantidad de elementos del arreglo. Eliminar un elemento tiene orden lineal en la cantidad de elementos del arreglo. Secuencia: Implementación con archivos Ventajas: El archivo es homogéneo. El archivo no tiene tamaño acotado. Desventajas: El archivo reside en memoria secundaria. Recuperar un registro tiene orden lineal (en archivos secuenciales). Insertar un elemento tiene orden lineal. Eliminar un elemento tiene orden lineal. Secuencia: Implementación con lista Una lista enlazada es una colección de nodos que considerado juntos forman un orden lineal. En una lista simplemente enlazada cada nodo es un objeto que almacena una referencia a un elemento y una referencia, llamada siguiente, a otro nodo.  Lista doblemente enlazada: cada nodo conoce un elemento, el nodo anterior y el nodo siguiente. Hay dos maneras de implementar una lista doblemente en lazada, una es manteniendo referencia al primer y último elemento, o bien usando nodos centinela al principio y al final para evitar casos especiales al insertar y eliminar.   Lista circular: cada nodo conoce al nodo siguiente y el último nodo conoce al primero TDA pila: Es una colección de objetos actualizada usando una política LIFO (last in – firts out) Operaciones: - Push(e): inserta el elemento e en el tope de la pila. - Pop(): elimina el elemento del tope de la pila y lo entrega como resultado. Si se aplica a una pila vacía se produce una situación de error. - isEmpty(): retorna verdadero si la pila no contiene elementos y falso en caso contrario. - top(): retorna el elemento del tope de la pila. Si se aplica a una pila vacía produce una situación de error. - size(): retorna un entero natural que indica cuantos elementos hay en la pila. Aplicaciones de la pila:  Navegador web: registro de páginas visitadas  Editor de texto: implementación de mecanismo de tecla retroceso y escape  Ejecución de procedimientos y funciones: organización de los registros de activación  Validación de código HTML  Compilación de una expresión y cálculo de su valor: paso de notación infija a postfija Implementación: Usando un arreglo: El tipo de la pila es guardado en una variable t, donde t es el índice en la pila. Cuando t =-1 la pila esta vacía. La cantidad de elementos es t+1. Cada método corre en tiempo constante O(1). Se mantiene una constante CAPACITY para indicar el tamaño total del arreglo. Al escoger un numero arbitrario de CAPACITY, generalmente grande, se está ocupando un espacio en memoria que seguramente no se va a utilizar. Por el contrario, si se quieren agregar elementos a la pila se lanzara una excepción, o bien puede aumentarse el tamaño del arreglo. Esta implementación con un arreglo es muy útil cuando se tiene un valor estimado de la cantidad de elementos que se agregaran a la pila Usando una estructura enlazada: el tope de la pila está en la cabeza de la estructura. Las operaciones son en tiempo constante O(1) y el espacio ocupado en memoria es O(n) donde n es la cantidad de elementos de la estructura. Todas las inserciones y retiros se hacen desde la cabeza de la estructura TDA Cola: Es una colección de objetos actualizada siguiendo una política FIFO (first in – first out) Operaciones:  Enqueue(e): pone el elemento e al final de la cola.  Dequeue(): elimina el elemento del frente de la cola y lo retorna. Si la cola esta vacía se produce un error.  Front(): retorna el elemento del frente de la cola. Si la cola esta vacía de produce un error.  isEmpty(): retorna verdadero si la cola no contiene elementos y falso en caso contrario.  size(): retorna un entero natural que indica cuantos elementos hay en la cola. Aplicaciones:  Colas de pedidos para atención por orden de llegada.  Buffer de entrada salida.  Socket (estructura de datos para comunicar dos programas): un programa inserta (encola) datos en el socket y otro programa los consume (desencolando). Implementaciones: Usando arreglo circular: la variable f indica el primer elemento de la cola, es decir el primero en ser removido, la variable r señala la próxima celda habilitada del arreglo. La cola esta vacía cuando f=r. para evitar índices fuera del arreglo se utiliza el arreglo circular en donde las variables f y r pasan a la posición 0 del arreglo después de haber llegado al final, esto se hace usando mod n, donde n es la longitud del arreglo. La cola no puede tener más de n-1 elementos. El tamaño de la cola es (n-f+r) al igual que la pila con arreglo solo es eficiente cuando conocemos una cantidad aproximada de los elementos que contendrá la cola. El tiempo de ejecución de la operaciones son todos de O(1). Usando estructura enlazada: el frente de la cola está en la cabeza de la lista. Se remueve por la cabeza y se ingresan por la cola. El tiempo de ejecución son de O(1) TDA ArrayList (vector): Implementa una secuencia S=[X1,X2,…,Xn] de elementos de tipo genérico E, donde n es la longitud de S. la posición de cada elemento es un entero i entre 0 y n-1, tal que la posición de X1 es 0, la de X2 es 1, … , la de Xn es n-1 Operaciones:  isEmpty(): retorna verdadero si la lista no contiene elementos y falso en caso contrario.  size(): retorna un entero natural que indica cuantos elementos hay en la lista.  get(i): retorna el elemento i-esimo de la lista; ocure un error si isize-1.  set(i,e): reemplaza con e al elemento i-esimo; ocure un error si isize-1.  Add(i,e): agrega un elemento e a la posición i; ocure un error si isize-1.  Remove(i): elimina el elemento i-esimo de la lista. TDA lista (node list o linked list) Para implementarlo usaremos estructura simple o doblemente enlazada, además de la posición de nodo en lugar de un índice para referirnos a la “ubicación” de un elemento en la lista. Posiciones: para abstraer y unificar las diferentes formas de almacenar elementos en varias implementaciones de una lista, introducimos el concepto de “Position”. Este esquema determina que cada posición almacena un elemento y existe un método para obtenerlo. Operaciones:  First(): retorna la posición del primer elemento de la lista; lanza error si la lista esta vacía.  Last(): retorna la posición del último elemento de la lista; lanza error si la lista está vacía.  Prev(p): retorna la posición que precede al elemento en la posición p; lanza error si p=first.  Next(p): retorna la posición del elemento que sigue al elemento en la posición p; lanza error si p=last.  set(p,e): reemplaza el elemento en la posición p con e; retornando el elemento que estaba antes en la posición p.  addFirst(e): inserta un nuevo elemento e como primer elemento.  addLast(e): inserta un nuevo elemento e como último elemento.  addBefore(p,e): inserta un nuevo elemento e antes de la posición p.  addAfter(p,e):inserta un nuevo elemento e luego de la posición p.   remove(p): elimina y retorna el elemento en la posición p invalidando dicha posición. Segunda implementación: con lista simplemente en lazada y celda de encabezamiento (nodo dummy). Esta implementación usa posición indirecta, que es, la posición P i del elemento i es la dirección del nodo anterior al nodo que contiene a i. Ventajas:  addBefore y addAfter tiene orden O(1)  no hay casos especiales como testear que se inserta al principio de la lista o la lista está vacía ya que siempre está al menos la celda de encabezamiento. Desventajas:  addLast, Last y Prev siguen teniendo orden lineal en la cantidad de elementos de la lista. Tercera implementación: Usa una lista simplemente enlazada y mantiene una referencia al primer y último elemento, la posición puede ser directa (sin nodo dummy) o indirecta (con nodos dummy). Ventajas:  addLast(e) y last() tienen orden O(1). Desventajas:  hay casos especiales cuando se elimina al principio y al final, sobre todo cuando la lista mide 1.  prev(p) sigue siendo de orden lineal en la cantidad de elementos de la lista (hay que recorrer desde el principio). Cuarta implementación: Usa una lista doblemente enlazada con referencia al primer y último nodo y dos celdas de encabezamiento (una al principio y otra al final) Ventajas:  cada nodo conoce el siguiente nodo y al nodo anterior.  todas las operaciones tienen orden 1.  Desventajas:  mayor uso de espacio. Iteradores: Un iterador es un patrón de diseño que abstrae el recorrido de los elementos de una colección. Un iterador consiste en una secuencia S, un elemento “actual” corriendo sobre S, y una manera de avanzar al siguiente elemento de S, haciéndolo el nuevo elemento actual. Métodos de un elemento iterador:  hasNext(): testea si hay elementos para recorrer en el iterador.  next(): retorna el siguiente elemento del iterador. Operaciones para una colección iterable:  Iterator(): retorna un iterador para los elementos de la colección. Árbol: Un árbol T se define como un conjunto de nodos almacenando elementos tales que los nodos tienen una relación padre-hijo, que satisface:  Si T no es vacío, tiene un nodo especial, llamado la raíz de T, que no tiene padre.  Cada nodo V de T diferente de la raíz tiene un único nodo padre W.  Cada nodo con padre w es hijo de W. Definición recursiva Un árbol T es:  Vacío (no tienen nodos).  Es un nodo R (llamado la raíz de T) y un conjunto (posiblemente vacío) de árboles T1,T2,…,Tk cuyas raíces R1,R2,…,Rk son hijos de R. Definición recursiva de árbol no vacío:  Un nodo hoja R llamado raíz de T.  Es un nodo R (llamado la raíz de T) y un conjunto (posiblemente vacío) de árboles T1,T2,…,Tk cuyas raíces R1,R2,…,Rk son hijos de R. Relaciones entre nodos - Nodos hermanos: dos nodos con el mismo padre se llaman hermanos. - Nodos externos u hojas: un nodo V es externo si no tiene hijos. - Nodo interno: un nodo V es interno si tiene uno o más hijos (esto incluye a la raíz). - Ancestro(u,v): un nodo U es ancestro de un nodo V si U es igual a V o U ancestro del padre de V. - Ancestro propio: un nodo U es ancestro de un nodo V si U es distinto a V y U ancestro del padre de V. - Descendiente(u,v): un nodo U es descendiente de V si V es un ancestro de U. - Descendiente propio(u,v): u descendiente propio de v si u es descendiente de V y u es distinto de V. - Sub-árbol: el sub-árbol de T con raíz en el nodo V es el árbol consistiendo de todos los descendientes de V. - Arco: un arco de un árbol T es un par de nodos (u,v) tales que u es padre de v o viceversa. - Camino: un camino de T es un secuencia de nodos tales que cualquier par de nodos consecutivos en la secuencia forman un arco. Arboles Ordenados: Un árbol se dice ordenado si existe un orden lineal para los hijos de cada nodo, es decir, se puede identificar el primer hijo, el segundo hijo y así sucesivamente. Tal orden se visualiza de izquierda a derecha de acuerdo a tal ordenamiento. Métodos de Árbol: Position:  Element(): retorna el objeto almacenado en esta posición. Métodos de acceso:  Root(): retorna la raíz del árbol, lanza error si el árbol esta vacío.  Parent(v): retorna el padre de V, y lanza error si v es la raíz.  Children(v): retorna una colección iterable conteniendo los hijos del nodo v, si el árbol es ordenado, children los mantiene en orden. Si v es una hoja children(v) es vacía. Métodos de consulta:  isInternal(v): testea si v es un nodo interno.  isExternal(v): testea si v es una hoja.  isRoot(v): testea si v es la raíz. Métodos genéricos:  size(): retorna el número de nodos del árbol.  isEmpty(): testea si el árbol tiene o no nodos.  Iterator(): retorna un iterador con los elementos ubicados en los nodos del árbol.  Position(): retorna una colección iterable de los nodos del árbol.  Replace(v,e): reemplaza con e y retorna el elemento ubicado en V. Metodos de modificación:  createRoot(e): crea un nodo raíz con rotulo e.  addFirstChildren(p,e): agrega un primer hijo al nodo p, con rotulo e.  addLastChildren(p,e): agrega un último hijo al nodo p, con rotulo e.  addBefore(p,rb,e): agrega un nodo con rotulo e como hijo de un nodo padre p dado. El nuevo nodo se agregara antes de otro nodo hermano rb también dado.  addAfter(p,lb,e): agrega un nodo con rotulo e como hijo del padre p dado. El nuevo nodo se agregara a continuación de otro nodo lb también dado.  removeExternalNode(p): elimina la hoja p.  removeInternalNode(p): elimina el nodo interno p. los hijos del nodo eliminado lo reemplazaran en el mismo orden en el que aparecen. La raíz se puede eliminar si tiene un único hijo.  removeNode(p): elimina el nodo p. Profundidad y altura:  Profundidad de un nodo v en un árbol T: Es la longitud del camino desde la raíz de T hasta el nodo v, es igual a la cantidad de ancestros propios de v. Algoritmo: Profundidad(T,v) si v es la raíz de T entonces retornar 0 sino retornar 1+Profundidad (T,w) donde w es el padre de v en T Tiempo de ejecución: es del orden de dv donde dv es la profundidad de v en T.  Longitud de un camino: es la cantidad de arcos de un camino.  Altura de un nodo V en un árbol T: Es la longitud del camino más largo a una hoja en el subárbol con raíz V.  Primera solución: Altura(T) h←0 para cada vértice v en T hacer si b es una hoja en T entonces h←max(h,profundidad(T,v)) retornar h Tiempo de ejecución: Taltura(n) es igual a O(n2).  Segunda solución: Altura(T,v) si v es una hoja en T entonces retornar 0 sino h←0 para cada hijo w de v en T hacer h←max(h,altura(t,w)) retornar 1+h Tiempo de ejecución: Taltura(n) es igual a O(n2).  Altura de un árbol T: la altura del nodo raíz de T. Recorridos: un recorrido de un árbol T es una manera sistemática de visitar todos los nodos de T. Los recorridos básicos son:  Preorden: En el recorrido preorden de un árbol T, la raíz r de T se visita primero y luego se visitan recursivamente cada uno de los subárboles de r. si el árbol es ordenado los subárboles se visitan en el orden en el que aparecen. Algoritmo: preorden(T,v) visitar(T,v) para cada hijo w de v en T hacer preorden(T,w) Tiempo de ejecución: si n es la cantidad de nodos del árbol T, el tiempo de ejecución de preorden es O(n), asumiendo una visita de O(1). Es decir, preorden corre en tiempo lineal en el tamaño del árbol.  Postorden: En el recorrido postorden de un árbol T, la raíz r de T se visita luego de visitar recursivamente cada uno de los subárboles de r. si el árbol es ordenado los subárboles ser visitan en el orden en el que aparecen. Algoritmo: Postorden(T,v) para cada hijo w de v en T hacer Postorden(T,W) Visitar(T,v) Tiempo de ejecución: si el árbol T tiene n nodos entonces el tiempo de postorden es O(n) asumiendo una visita de O(1).  Inorden: En el recorrido inorden (o simétrico) de un árbol T con raíz r, primero se recorre recursivamente el primer hijo de la raíz r, luego se visita la raíz y luego se visita recursivamente al resto de los hijos de r. Si el árbol es ordenado se visitan en el orden en que aparecen. Algoritmo: Inorden(T,v) si v es hoja en T entonces Visitar(T,v) sino w←primer hijo de v en T inorden(T,w) visitar(T,v) mientras w tiene hermanos en T hacer w←hermano de w en t inorden(T,w)   Por niveles: o Nivel: es un subconjunto de nodos que tienen la misma profundidad. o Recorrido por niveles: visita todos los nodos con profundidad p antes de recorrer todos los nodos de p+1. Algoritmo: Niveles(T) Cola←new cola() Cola.enqueue(t.root()) Cola.enqueue(null) //esto sirve para detectar el fin de línea mientras not cola.isEmpty() hacer v←cola.dequeue() si v es distinto de null entonces vistar(T,v) para cada hijo w de v en T hacer cola.enqueue(w) sino imprimir fin de línea //acción al terminar un nivel si not cola.isEmpty() entonces cola.enqueue(null) Tiempo de ejecución: sea hi la cantidad de hijos del nodo i T(n)= c1+Σni=1 (c2+c3hi)=c1+c2n+c3(n-1)=O(n). Representación de arboles - Del padre: cada nodo conoce solo a su rotulo y al padre. - Representación lista de hijos: cada nodo conoce su rotulo (elemento) y la lista de sus nodos hijos. El árbol conoce el nodo raíz del árbol. - Padre + lista de hijos [GT]: el árbol conoce la raíz. Cada nodo conoce el rotulo, la lista de nodos hijos y el nodo padre. - Hijo extremo izquierdo - hermano derecho: cada nodo conoce su rotulo y la identidad de su hijo extremo izquierdo y de su hermano derecho (se puede combinar con la representación del padre de ser necesario).  Representación con arreglo (HEI-HD): Arboles Binarios: Un árbol binario es un árbol ordenado que cumple: 1. Cada nodo tiene a lo sumo dos hijos. 2. Cada nodo hijo es o bien, hijo izquierdo o hijo derecho. 3. El hijo izquierdo precede al hijo derecho en el orden de los hijos del nodo. Un subárbol que tiene como raíz al hijo izquierdo, se llama subárbol izquierdo, análogamente para el derecho. En un árbol binario propio, cada nodo tiene 0 o 2 hijos. Si un árbol binario no es propio entonces es impropio. Aplicaciones: Sirve para representar los resultados asociados a un conjunto de preguntas con respuesta “si” o “no”. Cada nodo interno se asocia con una pregunta. Se comienza en la raíz y con cada pregunta se va a la izquierda o a la derecha dependiendo de la respuesta. Cuando se llega a una hoja se tiene un resultado al cual se llega al partir de las respuestas dados en los ancestros de la hoja.  Una expresión aritmética puede representarse con un árbol binario. Las hojas almacenan constantes o variables. Los nodos internos almacenan los operadores (+,-,*,/): Crear un arbol de exprecion aritmetica (parsing): Algoritmo: Parse(exp) si exp no tienen una operación entonces retornar un árbol vinario hoja conteniendo exp sino op←ultimo_operador(exp) T1←parse(izqueirda(exp,op)) T2←parse(derecha(exp,op)) retornar un árbol binario con op como rotulo de la raíz y T 1 y T2 como hijos izquierdo y derecho respectivamente Calcular un árbol de expresión aritmética: cada nodo en un árbol de expresión tiene un valor asociado:  Si el nodo es externo, si valor es el de la variable/constante.  Si el nodo es interno, su valor está definido por la aplicación de la operación a los valores de sus hijos. Algoritmo: Evaluar(árbol_exp) si árbol_exp es una hoja entonces retornar el valor del rotulo de árbol_exp sino op←rotulo de raíz de árbol_exp v1 ←evaluar(left(árbol_exp)) v2 ←evaluar(right(árbol_exp)) retornar aplicar(op,v1,v2) Definición recursiva de Árbol Binario Un árbol binario T es o bien vacío, o consiste de:  Un nodo r llamado la raíz de t que contiene un rotulo.  Un árbol binario, llamado el subárbol izquierdo de T.  Un árbol binario, llamado el subárbol derecho de T. Operaciones de ABB (el árbol binario es una especialización de Tree que además soporta los métodos de acceso adicionales):  Left(v):Retorna el hijo izquierdo de v y ocurre un error si v no tiene hijo izq.  Right(v): Retorna el hijo der de v y ocurre un error si v no tiene hijo der.  hasLeft(v): Testea si v tiene hijo izquierdo.  hasRight(v): Testea si v tiene hijo derecho. Métodos de modificación:  addRoot(e): (o createRoot(e)) agrega un nodo raíz con rotulo e, lanza error si ya hay una raíz.  insertLeft(v,e): crea un nodo w hijo izquierdo de v con rotulo e, lanza error si v ya tiene hijo izquierdo.  insertRight(v,e): análogo a insertLeft.  remove(v): elimina el nodo v (si v tiene un hijo, reemplaza a v por su hijo, si v tiene 2 hijos, entonces ocurre un error).  attach(v,T1,T2): setea T1 como hijo izquierdo de v y T2 como hijo derecho de v (error si v no es hoja). Representación de árbol binario con arreglos La componente 0 no se usa. La raíz se almacena en la componente 1. El hijo izquierdo de la componente i se almacena en la componente 2*i. El hijo derecho de la componente i se almacena en la componente 2*i+1. Puede haber componentes vacías si el árbol no es lleno (propio) capitulo 7 [GT]. Cola con prioridad: Una cola con prioridad almacena una colección de elementos que soporta:  inserción de elementos arbitraria.  eliminación de elementos en orden de prioridad (el elemento de 1ra prioridad puede ser eliminado en cualquier momento). Nota: una cola con prioridad almacena sus elementos de acuerdo a su prioridad relativa y no expone una noción de “posición” a sus clientes. Clave vs prioridad - Clave: atributo de un individuo que sirve para identificarlo en un conjunto de individuos. Ejemplo: DNI, nuero de libreta, numero de afiliado, etc. - Prioridad: atributo de un individuo que sirve para pesar al individuo en un conjunto de individuos Ejemplo: promedio de un alumno, cantidad de dinero depositado en el banco por un cliente, cantidad de años que una persona es cliente de un negocio. Comparación de claves con órdenes totales: una cola con prioridad necesita un criterio de comparación ≤ que sea un orden total para poder resolver siempre la comparación entre prioridades. ≤ es un orden total si y solo si:  Reflexivo: k ≤ k (se relaciona consigo mismo, o sea contiene la identidad).  Antisimétrico: si K1 ≤ K2 y K2 ≤ K1 entonces K1 = K2.  Transitiva: k1≤k2 y k2≤k3, entonces k1≤k3. TDA Cola con prioridad: Una cola con prioridad es una colección de elementos, llamados valores, los cuales tienen asociado una clave que es provista en el momento que el elemento es insertado. Un par clave- valor insertado en una cola con prioridad se llama una entrada (k, v). Operaciones fundamentales:  Insert(k,v): inserta un valor v con clave k en PQ  RemoveMin(): Retorna y remueve de PQ una entrada con la clave más pequeña  Size(): Retorna el número de entradas en PQ  isEmpty(): testea si p es vacío  min(): retorna (pero no remueve) una entrada de PQ con la clave más pequeña Implementaciones:  lista no ordenada:  Insert: Se inserta al principio de la lista.  Min, removeMin: Para hallar el mínimo o removerlo es necesario recorrer toda la lista.  lista ordenada:  Insert: Para insertar en forma ordenada es necesario recorrer toda la lista en el peor caso.  Min, removeMin: El mínimo es el primer elemento de la lista. Cola con prioridad implementada con Heap: Un heap es un árbol binario que almacena una colección de entradas en sus nodos y se satisface dos propiedades adicionales:  Propiedad de orden del heap (árbol parcialmente ordenado): en un heap T, para cada nodo v distinto de la raíz, la clave almacenada en v es mayor o igual que la clave almacenada en el padre de v.  Propiedad de árbol binario completo: un heap T con altura H es un árbol binario completo si los nodos de los niveles 0, 1, 2,…, h-1 tiene 2 hijos y el nivel h-1 todos los nodos internos estas a la izquierda de las hojas y hay a lo sumo un único nodo con un hijo (que debe ser izquierdo). Propiedad de un heap: Un heap T con n entradas tiene una altura h = piso(log n) Demostración: como t es completo, - La cantidad n de nodos mínima será con el nivel h-1 lleno y un nodo en el nivel h: n ≥ 1+2+4+…+2h-1+1 = 2h-1+1 = 2h Luego, es h ≤ log2n. - La cantidad n de nodos es máxima cuando el nivel h está lleno: n ≤ 1+2+4+…+2h = 2h+1-1 Luego, h≥log2(n+1)-1 Por lo tanto, como h es entero, entonces h = piso(logn) Aplicación Heap Sort: Su objetivo es ordenar un arreglo A de N enteros en forma ascendente. Algoritmo: HeapSort(a,n) cola ← new ColaConPriodidad() para i ← 0..n-1 hacer cola.insert(a[i]) para i ← 0..n-1 hacer a[i] ← cola.removeMin() Tiempo de ejecución: Theapsort(n) = O(n.log2(n)) Mapeo Un mapeo permite almacenar elementos de tal manera que puedan ser localizados rápidamente usando una clave. Un elemento generalmente tiene información útil además de su clave. Por ejemplo, un alumno tiene clave Libreta pero almacena nombre, fecha de nacimiento, dirección, teléfono, correo electrónico, etc. Un mapeo puede ser interpretado como una función de dominio K y codominio V. Un mapeo puede ser interpretado como un conjunto de entradas (k,v) donde k tiene tipo K y v tiene tipo V. Operaciones de TDA Mapeo Dado un mapeo M: - Size(): Retorna el número de entradas M. - isEmpty(): Testea si M es vacío. - get(k): si M contiene una entrada e con clave igual a k, retorna el valor de e. En caso contrario retorna null. - Put(k,v): Si M no tiene una entrada con clave k, entonces agrega una entrada (k,v) a M y retorna null. Si M ya tiene una entrada e con clave k, reemplaza el valor con v en e y retorna el valor viejo de e. - Remove(k): remueve de M la entrada con clave k y retorna su valor. Si M no tiene entrada con clave k, retorna null. Si M no tiene entrada con clave k, retorna null. - Keys(): Retorna una colección iterable de las claves en M. Keys().Iterator() retorna un iterador de valores. - Entries(): Retorna una colección iterable con la entradas de M. Entries().iterator() retorna un iterador de entrada. Diccionarios Un diccionario almacena pares clave-valor (k,v) (como los mapeos). Las claves son de tipo K y los valores de tipo V genéricos (como los mapeos). A diferencia de los mapeos, un diccionario puede almacenar claves repetidas. Existen dos tipos de diccionarios: - Diccionarios no ordenados: las claves solo se comparan por igual. - Diccionarios ordenados: hay una relación de orden total definida para las claves Operaciones: Dado un diccionario D no ordenado:  Size(): retorna el número de entradas de D.  isEmpty(): testea si D está vacío.  find(k): si D contiene una entrada e con clave igual a k, entonces retorna e, sino retorna null.  findAll(k): retorna una colección iterable conteniendo todas las entradas con clave igual a k.  insert(k,v): inserta en D una entrada e con clave k y valor v y retorna la entrada e.  remove(e): remueve de D una entrada e, retornando la entrada removida. Ocurre un error si e no está en D.  entries(): retorna una colección iterable con las entradas clave-valor de D. Tabla Hash: Una de las formas más eficientes de implementar un mapeo o diccionario es en ciertos casos usando una tabla hash. Aunque, como vimos antes, el tiempo de ejecución de las operaciones de un mapeo con n entradas y una tabla hash es de O(n), las tabla hash puede usualmente hacer que las operaciones sean O(1). En general, una tabla hash consiste de dos componentes, un arreglo de buckets y una función hash - Hash abierto: consiste en mantener en cada componen de esta tabla hash una lista de entradas. Las colisiones determinan más de un elemento en cada lista. Para buscar, insertar o eliminar una entrada a partir de una clave, aplicamos la función hash sobre dicha clave, accedemos de forma constante al bucket y recorremos la lista de entradas  arreglo de buckets: un arreglo de cubetas para implementar una tabla de hash es un arreglo A de n componentes, donde cada celda de A es una colección de pares clave-valor  función de hash H: dada una clave k y un valor v, h de k es un entero en el intervalo [0,n-1] tal que la entrada (k, v) se inserta en la cubeta A[H(k)]  colisión: dada 2 claves k1 y k2 tales que k1 ≠k2, se produce una colisión cuando H(k1)=H(k2) (las entradas de una cubeta tienen claves colisionadas) Hashin con claves genéricas - Paso 1 (hash code): dada una clave k, obtener un número entero llamado código de hash a partir de K. - Paso 2 (función de compresión): a partir del código de hash obtener un valor entre 0 y n-1 (módulo de n ó [(ai+b)mod p]mod n donde ay b son enteros al azar y p es un primo mayor a n). Distribución uniforme: todos los eventos tienen la misma probabilidad. Distribución uniforme de claves: la probabilidad de que una clave termine en un bucket determinado es constante y es igual a 1/n donde n es la cantidad de buckets de la tabla hash. - Hash cerrado: En hash cerrado se tiene un arreglo de N buckets. Cada bucket almacena a lo sumo una entrada. Dada la clave k y un valor v la función de hash H indica cual es la componente H(k) del arreglo en la cual se almacena la entrada (k,v). Dada dos claves k1 y k2 tales que k1 ≠k2, si H(k1)=H(k2) entonces se produce una colisión. Políticas para la resolución de colisiones: - Lineal (Lineal Probing): si tratamos de insertar una entrada en un bucket A[i] que ya está ocupado (H(k)=i), entonces tratamos de colocarlo en A[(i+1) mod N] y si ya está ocupado A[(i+2) mod N] y asi sucesivamente hasta encontrar un lugar libre. Este método conserva espacio pero complica a la hora de remover. Además la búsqueda a través de muchas celdas de la tabla hash ralentiza el proceso de búsqueda considerablemente. - Cuadrática (quadratic Probing): involucra iterablemente tratar en los buckets A[(i+f(j))modN] donde j es 0,1,2,… y f(j)=j2. Aunque N sea primo esta estrategia podría no encontrar un bucket vacío en A si el arreglo de buckets esta medio lleno. - Hash doble (Double Hashing): elegimos una segunda función hash H2, y si H mapea alguna entrada a un bucket ocupado, entonces se trata con los buckets A[(i+f(j))modN] donde j es 0,1,2,… y f(j)=j*H2(k). la segunda función hash no debe estar evaluada en 0. Una opción común es H2(k)=q-(k mod q) para algún numero primo qk entonces return buscar(k, hijo izquierdo nodov) sino //clave(nodov) 1 hacer f1 ← Q.min().key(); T1 ← Q.removeMin(); f2 ← Q.min().key(); T2 ← Q.removeMin(); Crear un Nuevo árbol binario T con hijo izquierdo T 1 e hijo derecho T2 Insertar T en Q con prioridad f1+f2 retornar el árbol Q.removeMin() Arboles Balanceados  AVL: Es un árbol binario de búsqueda con una restricción para mantener una altura del árbol proporcional al logaritmo de la cantidad de nodos del árbol. El tiempo de búsqueda, inserción y borrado en un árbol binario de búsqueda es lineal en la altura del árbol. Entonces, si n es la cantidad de elementos de un árbol T, tendríamos así que T(n) = O(log2(n)). Propiedad del balance de la altura Para cada nodo interno v de T, las alturas de los hijos difieren a lo sumo en 1. Cualquier ABB que satisface esta propiedad se dice Árbol AVL.  Como un AVL es un árbol binario de búsqueda, la operación de búsqueda no sufre alteraciones. Las únicas operaciones a modificar son la de inserción y eliminación, las cuales deben verificar que se cumpla la propiedad de balance al finalizar la operación. Luego de cada modificación en un nodo, rebalancearán los hijos de dicho nodo en O(1) por medio de las llamadas “rotaciones”. Las modificaciones se hacen desde la hoja donde se insertó el nodo hacia la raíz siguiendo el camino de las llamadas recursivas. Rotaciones Rotación izq-izq (Simple izquierda) Rotación izq-der (doble izquierda) Rotación der-der (simple derecha)  Rotación der-izq (doble derecha) Eliminación en un AVL Es idéntica a la de un ABB pero en este caso, cada vez que se sale de la recursión es necesario verificar de qué lado se eliminó un nodo para realizar el rebalanceo.  Árbol 2-3: Un árbol 2-3 es un árbol tal que cada nodo interno (no hoja) tiene dos o tres hijos, y todas las hojas están al mismo nivel. La definición recursiva es: T es un árbol 2-3 de altura h si  T es vacío (es decir de altura -1)  T es de la forma Donde n es un nodo y Ti y Td son árboles 2-3, cada uno de altura h-1. Ti se dice “subárbol izquierdo” y Td “subárbol derecho”.  T es de la forma Donde n es un nodo y Ti, Tm y Td son árboles 2-3, cada uno de altura h-1. Ti se dice “subárbol izquierdo”, T m se dice “subárbol medio” y Td “subárbol derecho”. Propiedad: Si un árbol 2-3 no contiene ningún nodo con 3 hijos entonces su forma corresponde a un árbol binario lleno. Árbol 2-3 de búsqueda Un árbol 2-3 es un árbol 2-3 de búsqueda si T es un árbol 2-3 tal que:  T es vacío (es decir de altura -1)  T es de la forma n contiene una clave k, y k es mayor que las clases de Ti, k es menor que las claves de Td, Ti y Td son árboles 2-3 de búsqueda.   T es de la forma n contiene dos claves k1 y k2, y k1 es mayor que las claves de Ti, k1 es menor que las claves de Tm, k2 es mayor que las claves de Tm, k2 es menor que las claves de Td. Ti, Tm y Td son árboles 2-3 de búsqueda. Reglas de Búsqueda o Si n tiene dos hijos, entonces contiene una entrada o Si n tiene tres hijos, entonces contiene dos entrada o Si n es una hoja, entonces contiene una o dos entrada Algoritmo Recuperar( T, clave ) --> valor R ← raíz de T sI clave está en R entonces retornar valor igual a valor asociado a la entrada sino si R es una hoja entonces retornar nulo // Falla sino si R tiene una entrada entonces k ← la clave de R si clave < k entonces retornar Recuperar( Ti(T), clave ) sino retornar Recuperar( Td(T) clave ) sino si R tiene dos entradas entonces k1 y k2 ← las claves de R si clave < k1 entonces retornar Recuperar( Ti(T), clave ) sino si clave < k2 entonces retornar Recuperar( Tm(T), clave ) sino retornar Recuperar( Td(T), clave ) Insertar en un Árbol 2-3 de búsqueda Para insertar un valor X en un árbol 2-3, primero hay que ubicar la hoja L en la cual X terminará primero hay que ubicar la hoja L en la cual X terminará. Si L contiene ahora dos valores, terminamos. Si L contiene tres valores, hay que partirla en dos hojas L1 y L2. L1 se  queda con el valor más pequeño, L2 con el más grande, y el del medio se manda al padre P de L. Los nodos L1 y L2 se convierten en los hijos de P. Si P tiene sólo 3 hijos (y 2 valores), terminamos. En cambio, si P tiene 4 hijos (y 3 valores), hay que partir a P igual que como hicimos una hoja sólo que hay que ocuparse de sus 4 hijos. Partimos a P en P1 y P2, a P1 le damos la clave más pequeña de los dos hijos de la izquierda y a P2 le damos la clave más grande y los dos hijos de la derecha. Luego de esto, la entrada que sobra se manda al padre de P en forma recursiva. El proceso termina cuando la entrada sobrante termina en un nodo con dos entradas o el árbol crece 1 en altura (al crear una nueva raíz).  Árboles 2-3-4: Un árbol 2-3-4 tiene hojas con 1,2 o 3 claves, y sus nodos internos contienen:  1 clave y 2 hijos  2 claves y 3 hijos  3 claves y 4 hijos Todas las hojas tienen la misma profundad. Inserción en un árbol 2-3-4: Es igual que en un árbol 2-3 excepto que cuando hay overflow (4 claves en un nodo), se parte el nodo y van 2 claves al nodo izquierdo y 1 clave al nodo de la derecha, la tercera clave va al padre y así sucesivamente. Capítulo 10 de [GT]  Árboles Red-Black: Un árbol Red-Black es un tipo especial de árbol binario de búsqueda en el que cada nodo tiene un atributo de color cuyo valor es rojo o negro. Además de los requisitos impuestos a los árboles binarios de búsqueda convencionales, se deben satisfaces las siguientes reales para tener un árbol Red-Black válido:  Todo nodo es o bien rojo o bien negro.  La raíz es negra.  Todas las hojas (Null) son negras.  Todo nodo rojo debe tener dos hijos negros.  Cada camino desde un nodo dado a sus hojas descendientes contiene el mismo número de nodos negros. El camino más largo desde la raíz hasta una hoja no es más largo que dos veces el camino más corto desde la raíz a una hoja. Ordenamiento Dado un arreglo a de n componentes enteras a, a, …, a[n-1] se desea obtener una permutación de a tal que a ≤ a ≤ … ≤ a[n-2] ≤ a[n-1].  Multipasada: O(n2) o Selección (selection sort): Haremos n-1 pasadas sobre el arreglo a. En la pasada i- ésima, encontraremos el i-ésimo menos elemento del arreglo y lo intercambiaremos con a[i].  o Burbuja (bubble sort) o intercambio (Exchange sort): En cada pasada el burbuja mira dos elementos adyacentes y los intercambia si están fuera de orden. En cada pasada, el mayor elemento del arreglo queda al final del sub-arreglo que se está ordenando. Son necesarias n-1 pasadas (ya que el primer elemento queda ordenado gratis). o Inserción (insertion sort): Es equivalente a la forma de ordenar un mazo de cartas. Se comienza con un mazo vacío y uno desordenado. Cada carta se trata de insertar en la posición correcta. Entonces, en un momento dado, una parte del mazo está ordenada y se trata de insertar la siguiente carta de la porción desordenada del mazo en la posición correcta. Terminamos cuando la porción desordenada está vacía.  Merge sort: O(n*log2(n)): o Caso recursivo: Partir el arreglo en dos, ordenar recursivamente cada mitad y luego hacer la mezcla de cada mitad ordenada en un gran arreglo ordenado. o Caso base: El arreglo tiene 0 o 1 componente entonces está ordenado.  Heap sort: O(n*log2(n)) Algoritmo Heap Sort (a,n) cola ← new ColaConPrioridad() para I ← 0..n-1 hacer cola.insert(a[i]) para I ← 0..n-1 hacer a[i] ← cola. removeMin()  Quick sort: Quick Sort en promedio corta el arreglo por la mitad, como no hace el Merge, en promedio es más eficiente que el Merge sort con una complejidad de O(n*log2(n)). Sin embargo, el peor caso se da cuando se quiere ordenar un arreglo ordenado, se invoca recursivamente con una parte que mide 1 y la otra n-1, dando una complejidad de O(n2). Algoritmo Quick Sort si la lista es no vacía entonces 1. Dividir la lista en dos de tal manera que los ítems en la primera mitad vengan antes que los ítems en la segunda mitad. 2. Ordenar con Quick Sort la primera mitad. 3. Ordenar con Quick Sort la segunda mitad. Serialización La serialización implica salvar el estado actual de un objeto en un stream y luego poder recuperar el objeto equivalente de tal stream. Archivos de accesos directo Los archivos de acceso directo (Random Access File) permiten:  Leer los registros de un archivo en cualquier orden.  Modificar un registro cualquiera sin necesidad de reescribir todo el archivo.  Agregar un registro nuevo al final del archivo. Tendremos una operación más que se llama seek que recibe el número de byte al que hay que mover el puntero de archivo para realizar la próxima operación de lectura o escritura. Para utilizar seek es necesario conocer el tamaño del registro del archivo subyacente. Archivos Indizados (o Indexados) Los archivos indexados tuenen un orden virtual determinado por el ordenamiento de una clave. - Implementación de archivos indexados o Por cada tabla, hay al menos dos archivos:  Un archivo de datos donde cada registro tiene tamaño fijo.  Un archivo de índice; un mapeo de clave en número de registro (contiene además la cantidad de registros del archivos de datos).  Cada clave extra de búsqueda requiere otro índice (pero no otro archivo de datos, como por ejemplo, buscar/ordenar alumnos por legajos, DNI, nombre, etc). - Implementaciones para el índice o Arreglo ordenado  Búsqueda en orden logarítmico  Las actualizaciones implican reordenar el arreglo en orden n*log(n). o Árbol binario de búsqueda  Puede denegar en orden lineal para buscar y actualizar pero se espera orden logarítmico. o AVL, 2-3  Buscar y actualizar en orden logarítmico. o Árbol B y B+  Para grandes volúmenes de datos las opciones anteriores no son viables.  El árbol b generaliza la idea del árbol 2-3 con un gran número M de claves en cada nodo.  El árbol B+ almacena entradas (clave, valor) sólo en las hojas, los nodos internos almacenan solo claves que sirven para guiar la búsqueda. Árbol B El árbol B generaliza la idea del árbol 2-3 con un número M de claves en cada nodo. El tiempo de búsqueda y actualización es proporcional al log M(cantidad de claves). Se puede desperdiciar espacio en os nodos. Árbol B+ El árbol B+ almacena entradas (clave, valor) sólo en las hojas, los nodos internos almacenan solo claves que sirven para guiar la búsqueda. Síntesis Estructura de Datos Ventajas Desventajas - Inserción rápida. - Búsqueda y eliminación lenta. Arreglo - Acceso rápido si el índice es - Tamaño fijo. conocido. - Búsqueda más rápida con - Inserción y eliminación lenta. Arreglo Ordenado respecto a los arreglos no - Tamaño fijo. ordenados. - Rápido acceso al elemento - Acceso lento a los demás Pila tope. elementos de la estructura. - Rápida inserción. - Rápido acceso al elemento - Acceso lento a los demás Cola frente. elementos de la estructura. - Rápida inserción.  - Rápida eliminación e - Búsqueda lenta. Lista Enlazada inserción. - Rápida búsqueda, inserción - Algoritmo de eliminación Árbol Binario y eliminación (si el árbol complejo. esta balanceado). Árbol Red-Black - Rápida búsqueda. - Implementación compleja. - Rápida inserción y Árbol eliminación. - Rápida búsqueda, inserción - Su implementación es y eliminación. compleja. Árbol 2-3-4 - El árbol se mantiene siempre balanceado. - Muy rápido acceso si la - Eliminación lenta. clave es conocida. - Acceso lento si la clave es Tabla Hash - Rápida inserción. desconocida. - Utilización de memoria ineficiente. - Rápida inserción y - Acceso lento a los demás eliminación. elementos. Heap - Acceso directo al mayor elemento. - Muchas situaciones de la - Algunos algoritmos son lentos Grafo vida real son resueltos con y muy complejos. grafos.