Pseudocódigo el algoritmo que permite insertar un valor en un árbol binario de búsqueda

TF:1

Asumiendo ke se permita usar almace. Extra, ejecutar la comp. Como un torneo de elimi. Simple, manteniendo un registro de las entradas derrotadas por cada ganador en el camino. (Número bajo gana). Cuando se obtiene un ganador total, solo hay que identificar al ganador entre τlgnτ concursantes superados por el ganador gral. // Revisando esto, no se necesita mem. Adicional, si uno reorganiza la lista. Imple. El torneo de eliminación simple de la siguiente manera://Suponer que los núm's son a₀, a₁,..., a_n-1 . En la primera pasada comparar  con para ; si , intercambiarlos. En la seg. Pasada comparar  con  para  ; si , intercam. El par  con el par . En la i-esima pasada comparar  con para ; si , intercam. Los bloques de longitud  empezando en  y . Esto continua mientras , i.E, hasta ; por lo tanto, si la última pasada es la m-ésima pasada, entonces , o . El núm. Más pequeño en el conjunto es ahora a₀, y cada otro número en el conjunto ha perdido exacta. Una compa., por lo ke se han hecho n-1 compa's.//Los núm's ahora son  para i=0,...,m-1 son los núm's que perdieron a a₀ en las compa's directas; cada núm. En el conjunto que no es a₀ ni uno de estos m núm's pierde una compa. Directa con uno de estos m núm's y por lo tanto no puede ser el seg. Núm. Más pequeño en el conjunto. Por lo tanto, el seg. Núm. Más pequeño es el más pequeño de los  para i=0,...,m-1. Hay m de estos núm., por lo que se necesitan m-1 compa's para encontrar el más pequeño. El algorit en conjunto toma: (n-1)+(m-1)=n-1+τlgnτ-1=n+ τlgnτ-2 compa's.

TF: 2. A)

Para lograr esta cota nlog(logn). Se puede utilizar una clase especial de árboles binarios conocidos como árboles rojo – negro (RB Tree). Son aquellos que cuentan con información extra en los nodos (nodo padre, nodo hijo izq., nodo hijo der., color, etc) y son un árbol binario de búsqueda equilibrado, es decir, intentan mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento. El árbol rojo-negro tiene la propiedad de insertar, buscar y borrar en un tiempo O(logn) para el peor de los casos, y donde n es el número de elementos del árbol.

El algoritmo consistirá en recorrer el arreglo (S) e insertar cada elemento en el árbol, pero con una restricción, si se detecta un elemento duplicado no se inserta, únicamente se cuenta, agregando un campo “Contador” en el nodo. Y cada que haya un valor repetido solo se aumenta el contador, no se inserta como nuevo nodo.

Al hacer esto el árbol RB tendrá O(k) valores distintos. Por lo tanto, la complejidad de insertar un elemento tomará O(log(logn)) , y al insertar todos los elementos tomará  O(nlog(logn)).

Recorrer el árbol en orden y duplicar cada uno de los elementos dependiendo del campo “Contador” tomaría O(n), obteniendo el arreglo ordenado.

b) No se viola la cota inferior de O(nlogn) para el problema anterior debido a que la complejidad  se encuentra por arriba del límite, y esto es porque tenemos conocimiento de los valores distintos en el arreglo , es decir, .

TF: 4

Tomar cualquier arista  i que ocurre en T pero no en  R y eliminar de T para formar T'. Suponer que k conecta dos vértices α y β. Puesto que T es un árbol, el borrar i significa que uno de α y β sería desconectado del árbol. Recorrer T para determinar cuál es, digamos que fue α. Luego buscar en R para una arista  que conecta directamente a β y a través del cual se puede llegar a α. Es decir, alguna arista  que está en el camino entre α y β. Agregarlo a  para formar , lo cual es un árbol  donde ,  y  El hecho que  no puede ocurrir en  garantiza progreso hasta la solución. Puesto que cualquier árbol es distinto de  a lo más por la eliminación de una arista y la inclusión de otra arista, lo cual este algoritmo hace en cada paso, la secuencia de árboles que este algoritmo encuentra es óptimo. Es decir, no se puede encontrar una secuencia con menos pasos porque este algoritmo ya hace el mayor progreso que se puede hacer en cada paso. La complejidad de este algoritmo es . Para resolver cada uno de los  árboles intermediarios, necesita hacer una búsqueda a lo peor de todas las aristas  para encontrar uno que ocurre en  pero no en , otra de  para encontrar el vértice huérfano, y otra de  para encontrar la nueva arista está en el camino entre α y β en .

TF: 6. A)

Inicializar las var. C=0 , s=-1 y asumir que el algorit. Va a regresar el resul. Ordenado en un arreglo A. C representa una cuenta temporal y s sería 0 si el último elemento visto fue un cero, 1 si es uno, y -1 si es desconocido. Para cada pareja de elementos n_i y n_(i+1) con i=0,1,…,n-1 considéresé lo sigui. Si n_i < n_(i+1) ="" entonces="" se="" sabe="" que="" n_i="0," n_(i+1)="1" porque="" es="" la="" única="" combinación="" que="" satisface="" este="" escenario.="" si="" n_i="">n_(i+1)   entonces n_i=1, n_(i+1)=0. Entonces, en el primer caso agregar un cero a A y asignar s=1, luego proceder a evaluar la siguiente pareja. En el segundo caso, asignar c=c+1 y s=0, es decir, c es una cuenta del núm. De unos que faltan agregar a A. Si ninguno de los casos anteriores ha ocurrido, es decir, si s=-1 y n_i= n_(i+1), no hay manera de determinar si ambos son ceros o unos. Asignar c=c+1 y proceder a evaluar la sigui. Pareja. Es decir, c ahora es una cuenta del núm. De elementos de un valor desconocido, o uno o cero. La primera vez que asigna s a cualquier valor que no sea s=-1, si lo asigna a s=1 significa que el primer elemento en la comp. Fue un cero, y todos los números desconocidos antes también. Entonces agregar c ceros a A y reiniciar c=0. Si s=0, y dejar c sin modificaciones y seguir con el algori. Es decir, todos los núm's desconocidos fueron unos y c ahora tiene una cuenta del núm. De unos que falta agregar a A . Nótese que una vez que s≠-1 nunca va a volver a ser -1 por el resto del algoritmo. O sea, si n_i= n_(i+1) y s=0 entonces en la comparación previa el último elemento fue un cero estos dos elementos son ceros también. Por eso, agregar un cero a A. Si n_i= n_(i+1) y S=1 son unos, entonces asignar c= c+1 . Cuando i=n-1, agregar c unos a A.  Nótese que si i=n-1 y s=-1 el arreglo ya está ordenado y no hay que hacer nada, simplemente asignar la serie a A. // b)Formar parejas entre los números. Es decir, comparar  x_0 con x_1,x_2,x_3 donde  x_i es el i-ésimo número en la serie i=1,…,n .  A diferencia del algorit. Anterior, no compara x_1 con x_2. Hay cuatros resultados posibles, 00, 01, 10, y 11 según la lógica descrita en la parte anterior. 

TF: 6(continu)

Obsérvese que en los escenarios 01 y 10 se puede decir que hay un 0 y un 1 en la pareja, pero en los otros escenarios no. Puesto que cada número tiene la misma probabilidad de ser 1 que de ser 0, entonces cada uno de los escenarios tiene la misma probabilidad de ocurrir. La probabilidad de que ocurra uno de los casos 01 o 10 es 0,5. Entonces al promedio, la mitad de las parejas da información sobre cuantos unos y cuantos ceros hay. En las parejas restantes, ambos enteros tienen el mismo valor. Por eso, solamente es necesario determinar el valor de uno de esos enteros para determinar el valor de ambos. Tomar el primer entero en cada pareja y formar nuevas parejas entre ellos. Puesto que después del primer paso hay n/2 enteros desconocidos, que hemos tomado la mitad de ellos para formar parejas, y que las parejas son de la forma x_0 con x_1, x_2 con x_3 entonces hay n/8 parejas en el segundo paso y el mismo número de comp's.. Entre estas parejas nuevas lo mismo va a ocurrir, que los resultados para la mitad de ellos van a revelar sus valores y la mitad no. Entonces se vuelve a aplicar este paso hasta que se conozcan todos los valores de los enteros. Si llega a una situación donde el resultado para todas las parejas son iguales, por ejemplo, cuando solamente hay una pareja restante, compara el primer entero x_i en cada pareja contra algún entero que ya conoce el valor, x_k. Si son iguales es trivial determinar el valor de la pareja. Si x_k  = 0, x_i  < x_k="" entonces="" x_i ="1" y="" si x_k ="1,"  x_k =""> x_i entonces x_i  = 0. Puesto que el primer paso requiere O(n=2) comparaciones y cada paso después requiere un cuarto del número de comparaciones del paso anterior, la complejidad es de O(n/2 + n/8 + n/32 + ...) o O(2n=3). // Nótese que cada comparación revela información y nunca vuelve a comparar dos elementos. Es decir, o revela exactamente los valores de los dos elementos, o revela información que se puede utilizar más tarde para hacer lo mismo. Puesto que no es posible revelar información sin evaluar un elemento al menos una vez, y que no repetimos comparaciones, este algoritmo es óptimo.

TF:7

a) Para la solución de este primer inciso, debido a que no tiene valores duplicados. Se propone utilizar un arreglo con tamaño n, Lo cual llenarlo tomaría O(n) tiempo. Realizar una búsqueda (A[i]) podría ejecutarse en O(1), y del mismo modo una inserción en el arreglo (A[i]=v). Para remover un dato se puede utilizar un valor específico como NUL, lo cual funcionaria en un tiempo contante O(1).

b) Para este inciso se puede utilizar un árbol de búsqueda y utilizar una lista doblemente ligada para el sucesor y predecesor. Es decir,

Cada nodo tiene un puntero a su entrada en la lista doblemente ligada. La búsqueda, el mínimo y máximo no sufren cambios, por lo tanto siguen en un tiempo de O(logn). El que importa sería la inserción y eliminación. Por lo tanto, suponer que el nodo 6 no está insertado todavía, se hace un recorrido transversal de la lista hasta el nodo 4. Se sabe que el nodo 6 se colocará a la derecha. Lo importante es verificar que sucede con la lista doblemente ligada, la cual permite sin problemas acceder al sucesor y predecesor de algún nodo con el fin de hacer la eliminación e inserción en tiempo lineal O(n).

TF:8

Para este ejercicio, es necesario utilizar un Árbol Binario Balanceado. Comenzar con un árbol binario de modo que todas sus hojas sean elementos de la matriz en el mismo orden. Enseguida, para cada nodo que no abandone el árbol, asignarle un valor que sea la suma de sus valores de nodo secundarios. Por ejemplo, un árbol con solo 2 nodos hoja de valor 1 y 2 tendrá un valor de 3 en la raíz.  Dado que hay  nodos del tipo hoja en un árbol con  nodos; esto toma  tiempo para construir el árbol.

Add(i,y)- Agrega el valor  al i-ésimo número.

Dirigirse hacia el i-ésimo nodo el el árbol; luego ir desde ese nodo hasta la raíz del árbol y asegurarse de agregar el valor  a cada uno de los nodos que se encuentre.

 – Devuelve la suma de los primeros números .

Encontrar el camino al i-ésimo nodo y dirigirse hacia este elemento desde la raíz del árbol. Cada vez que haya un giro hacia la derecha en el árbol, agregar el valor del hijo izquierdo de ese nodo a la suma acumulada. Cuando se llegue al nodo hoja de interés, añadir su valor a la suma acumulada (y también recordar que se debe agregar su contraparte izquierda también si es un elemento secundario derecho.)

Ambas operaciones toman pasos  ya que esa es la altura del árbol binario.

TF:9

Considéresé un árbol de altura 3. Es decir, tiene una raíz que tiene hijos, y esos hijos tienen hijos, pero no hay otra generación de hijos posteriormente. Obsérvese que el conjunto independiente de peso máximo de este árbol es el máximo entre un conjunto que contiene la raíz y todos los hijos de sus hijos, o un conjunto que incluye solamente los hijos de la raíz. Ahora obsérvese que, si sí hay una cuarta generación o nivel, entonces en vez de incluir simplemente todos los hijos de la raíz por los pesos de los hijos sería mejor considerar el peso del conjunto independiente de peso máximo de cada hijo. Es decir, en vez de elegir un nodo por su peso, se elige por el peso de su conjunto independiente de peso máximo. Nótese que para un sólo vértice un tal conjunto es simplemente a sí mismo, y para un árbol de altura 2 es el máximo entre solamente la raíz o la suma del peso de los conjuntos de sus hijos. Entonces la recurrencia para árboles de altura de 3 o mayor, es:

donde C(T) es el conjunto independiente de peso máximo del árbol T, w(v) es el peso del vértice v,t_r es el vértice raíz de T,   S(T,t_r,i) es el subárbol de T quien es raíz es el i-ésimo hijo de t_r,n es el número de hijos de tr,   t_ri es el i-ésimo hijo de t_r y m es el número de hijos que tiene t_ri . Puesto que para calcular esta recurrencia basta visitar cada vértice solamente una vez con programación dinámica, la complejidad de este algoritmo es O(|T|) dónde |T| es el número de vértices en T o lineal.

TF: 11

a) Para este primer punto se propone la construcción de una matriz de orden , la cual al ser construido tomaría un tiempo de . Sin embargo, una de las carácterísticas que debe tener es que sea simétrica. Por ejemplo:

Sea la serie de número:  la matriz sería de la siguiente forma:

Matriz simétrica, lo que significa que , por lo tanto, permite encontrar el valor más pequeño en . Ya que cada valor en  es igual a Lo cual tomaría acceder a un elemento un tiempo constante .

TF: 11. B)

La idea principal para este punto es construir una representación multiresolución de la entrada, con cada nodo capaz de responder a la consulta para la parte de la secuencia de entrada. Un árbol de dichos nodos hace posible responder rápidamente a consultas arbitrarias cubriendo el rango de consultas con rangos cubiertos por nodo.

Construir un árbol binario en el que cada nodo contiene el valor más bajo para un rango de índices. El nodo raíz abarcar toda la secuencia de entrada. Los nodos del nodo de la raíz abarcan las mitades de la parte izquierda y derecha de la secuencia de entrada, así sucesivamente. Cada nodo de tipo hoja abarca un “rango” de elemento único de entrada, siendo el valor “más bajo” en ese rango el valor correspondiente a esa posición en la secuencia de entrad. El número total de nodos es el árbol es .

La función de consulta es recursiva, comenzando desde la raíz:

• Si el rango de la consulta coincide exactamente con el intervalo abarcado por el nodo actual, regresa el valor del nodo actual.
• Si el rango de la consulta cae totalmente dentro de la mitad izquierda, regresa el resultado de llamar a la función de consulta en el hijo izquierdo.
• De lo contrario, regresa el menor de los resultados de llamar a la función de consulta en el hijo izquierdo y derecho.

La función de consulta visitará como máximo 2 nodos de hoja y se ejecutará en tiempo .

TF: 12

Considerar el siguiente ejemplo:

El árbol de expansión mínimo está marcado con las aristas de línea gruesa. Y estamos interesados en el camino entre B y D, así como en el peso b. Si b es menor que 5, el MST (árbol de expansión mínimo) no es el más corto. Esto podría cambiar el MST pero también depende, ya que podríamos formar el gráfico desde B à D à C en lugar de B à C à D. Sería nuestro MST si  , por ejemplo . Por lo tanto, el MST no es el camino más corto si .

TF:14

Para dar solución a este problema, en primer lugar se necesita que    sea potencia de 2. Si no lo es, se complica la búsqueda, y además se pueden agregar renglones a   para que en total haya  elementos relativamente rápido . Así que se asumirá que  para la  dado el problema. Se recorre la columna  de , o sea que se haría un recorrido de Se llevarán 2 contadores  y  , 2 listas  y , y si  es cero, se incrementa  en uno y se agrega  a ; si es uno, incrementamos  en uno y se agrega  a . Al final se tendría o bien que , o que  ; porque , es decir, significa que es par, y entonces en el rango  hay un par más que impares. Entonces si hace falta un par, habrá igual número de pares que de impares; y si falta un impar, habrá menos impares que pares. // Entonces ya sabiendo que nos falta un par o un impar, vamos a repetir el proceso, pero en la k-1-ésima columna, y recorriendo solo los elementos de la lista correspondiente (B₁ o B₂). El tamaño de la lista B_1 y B_2 se reduce a la mitad en cada ciclo; cuando llegue a tamaño uno, tendremos en la lista correspondiente el índice de un número A que tiene todos los bits iguales a nuestro número perdido, excepto el primero (por esto es que necesitamos que n=2^k). Entonces le cambiamos el primer bit a este elemento, y tendremos el número perdido.

TF: 14.(Continuación)

La complejidad del algoritmo es . El primer ciclo  toma tiempo , y el siguiente  se ejecuta de la siguiente manera: la primera vez, dentro de él se ejecuta un  anidado que se ejecuta  veces; la segunda vez, el  anidado se ejecuta  ve ces; la tercera vez  veces. En general para la k-ésima ejecución, se ejecuta  veces pero , entonces . En conclusión, el número total de operaciones que se hacen es:  

TF: 15

Necesitamos construir una pila de altura máxima. A través de los siguientes pasos: //
1. Generar 3 rotaciones a todas las cajas. El tamaño de la matriz de rotación llega a ser 3 veces el tamaño de la matriz original. Para simplificar, considerar que la profundidad siempre es menor o igual que el ancho. //
2. Ordenar las cajas 3n generados anteriormente en orden decreciente del área base. //
3. Después de ordenar las cajas, el problema es el mismo que el de LIS* con la siguiente propiedad de subestructura óptima: //  Máxima altura de pila posible con la caja  en la parte superior de la pila
 donde  y  y .
Si no hay tal  entonces

4. Para obtener la altura máxima general, devolvemos max(MSH(i)) donde  0< i=""><> //LIS:
 Este problema se resuelve con Programación Dinámica. Consiste en encontrar la longitud de la subsecuencia más larga de una secuencia dada de modo que todos los elementos de la subsecuencia se clasifiquen en orden creciente. Por ejemplo, la longitud de LIS para {10, 22, 9, 33, 21, 50, 41, 60, 80} es 6 y LIS es {10, 22, 33, 50, 60, 80}. // Sea arr[0 ... N-1] el arreglo de entrada y  L(i) la longitud de la terminación de LIS en el índice i de manera que arr[i] sea el último elemento de la LIS. Entonces, L(i) puede escribirse recursivamente como: // L (i)= 1 +max (L(j)) donde 0 Para encontrar el LIS para una matriz dada, necesitamos devolver max(L(i)) donde  0< i="">Por lo tanto, vemos que el problema de LIS satisface la propiedad óptima de la subestructura ya que el problema principal se puede resolver usando soluciones a subproblemas.

TF: 16. =T#4: 9 TF:17

Para la resolución de este problema se toma el algoritmo de Graham Scan:// El primer paso de este algoritmo consiste en encontrar el punto con la menor coordenada ordenada (menor coordenada en el eje y). Si hay más de un punto que cumpla esta condición, se escoge el punto con menor coordenada en el eje x. A este punto se lo nombra por la letra P. Este paso es de complejidad O(n), donde n es el número de puntos del problema. // Después, considerar que los puntos ya están ordenados. Para agilizar el proceso, se puede omitir el cálculo del ángulo ya que es suficiente con hallar su cotangente. // El algoritmo continúa tratando secuencia de puntos ordenados según el ángulo creciente. Para cada punto se calcula si el movimiento desde los dos anteriores es un "giro a derecha" o un "giro a izquierda". Si el movimiento es dextrógiro, indica que el segundo punto de la terna no es parte de la envolvente convexa y debe dejar de considerarse en los cálculos y tomar el siguiente. Cuando se halla un giro a izquierda, el algoritmo pasa a calcular el siguiente punto. En caso de que existan puntos alineados pertenecientes a la envolvente, los centrales pueden ser descartados o considerados como parte de la misma.   No es necesario calcular el ángulo entre tres puntos para saber si es un giro a derecha o a izquierda, pues puede conocerse ese dato con una sola operación aritmética. Para tres puntos (x1, y1), (x2, y2), (x3,y3) , se puede calcular el producto vectorial de los dos vectores definidos por las coordenadas (x1, y1), (x2, y2), (x3,y3), de tal manera que el resultado se obtiene con la ecuación (x1-y1), (x2-y2), (x3-y3) . Si el resultado es 0, los puntos están alineados, si es positivo, el giro es a izquierdas y, si es negativo, el giro es a derecha.  // Finalmente, con este proceso se vuelve al punto P de partida, momento en el que el algoritmo está completado y sólo quedan los puntos pertenecientes a la envolvente convexa correctamente ordenados. Y debido a que no hubo un ordenamiento previo, el algoritmo toma un tiempo O(n).

TF: 18

El plano del árbol de expansión mínimo para la distancia Euclidiana:

a) Se demuestra que el conjunto de aristas del EMST (Euclidian Mínimum Spanning Tree) está contenido en el conjunto de aristas de la triangulación de Delaunay.

- Objetivo: Cada arista que no esté en una triangulación de Delaunay tampoco está en ningún EMST.

- La naturaleza del árbol de expansión mínimo: La arista de mayor peso en cualquier ciclo no estará en el árbol de expansión mínimo.

- Triangulación de Delaunay: Si hay un circulo con dos de los puntos de entrada en su límite que no contiene otros puntos de entrada, la línea entre esos dos puntos es una arista de cada triangulación de Delaunay.

Para triángulos obtusos, la arista más grande no debe estar en EMST. Sin embargo, para la propiedad de triangulación Delaunay, se debe considerar la existencia del límite entre ellos (arista compartida de Voronoi).

Supongamos que no hay ninguna arista entre  y  en Delaunay. Luego, para cualquier círculo que pase por  y , existe un punto  dentro del círculo. De punto  a , la distancia entre ellos debe ser menor que la distancia entre  y . Al mismo tiempo, en el EMST,  tres puntos constituirán un triángulo obtuso, donde  es la arista más grande.

TF:18(continu)

b) Para encontrar el algoritmo de EMST en tiempo O(nlogn), considerar los siguientes pasos: //
1. Encontrar todas las aristas en tiempo O(nlogn) usando la triangulación de Delaunay. Triangulación de Delaunay: Un algoritmo útil para calcular triangulaciones de Delaunay puede ser a partir del diagrama de Voronoi de un conjunto de puntos. Conviene señalar que la complejidad de un buen algoritmo para construir un diagrama de Voronoi es de O (n log n) en el peor de los casos, y que la conversión a Delaunay es lineal, por lo que éste algoritmo podría ser bastante rápido en contra de lo que se podría pensar en un principio.// Para realizar la conversión de un diagrama de Voronoi a una triangulación de Delaunay, es suficiente con recordar y aplicar las propiedades de ambos diagramas: // • Cada triángulo de la triangulación de Delaunay se corresponde con un vértice de Voronoi (dual), que además coincide con el circuncentro del triángulo // •Cada vértice de la triangulación se corresponde con una única regíón de Voronoi.// •Cada arista de la triangulación puede calcularse a partir de una arista de Voronoi, ya que son perpendiculares entre sí. //
2. Realizar esto hasta 3n-6 aristas, usando el algoritmo de Kruskal en MST en tiempo O(ElogE), donde E=O(3n-6). // Algoritmo Kruskal

•Se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado.

•Se crea un conjunto C que contenga a todas las aristas del grafo.

•Mientras C es no vacío.//- Eliminar una arista de peso mínimo de C.// -Si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol.// - en caso contrario, se desecha la arista //// •Al acabar el algorit., el bosque tiene un solo componente, el cual forma un árbol de expansión mín. Del grafo. //
3.Por lo tanto, resultando al final un algorit. Con un tiempo total O(nlogn).

TF: 19

Para resolver este problema hay que considerar el siguiente algoritmo:

1. Hay que construir un Diagrama de Voronoi utilizando el algoritmo de Fortune, está basado en barrer el plano con una línea horizontal y calcular el diagrama de Voronoi a medida que la línea se desplaza. Esto toma .
2. Para cada celda  hay que verificar la celda vecina , y posteriormente calcular la . Las aristas del diagrama de Voronoi se obtienen en , y para cada verificación de arista solo se necesita . Por lo tanto, en total este paso se da en .

Es importante demostrar que la celda abierta por cada punto solo será la celda vecina más cercana, de lo contrario no cumple con la definición del Diagrama de Voronoi. En conclusión, el algoritmo total se ejecuta en .