Estructuras de Datos

¿Mantener un árbol equilibrado implica que cada nodo de los subárboles izquierdo y derecho tengan exactamente la misma altura?. Verdadero. Falso.

Para conseguir un orden O(log n) en la búsqueda dentro de un árbol equilibrado, es necesario que la diferencia de altura entre el subárbol izquierdo y derecho de cada nodo sea como máximo 1. Verdadero. Falso.

Un árbol completo cumple la condición de que cada nodo tenga subárboles izquierdo y derecho con la misma altura. Verdadero. Falso.

La condición estricta de igualdad de alturas en subárboles izquierdo y derecho es comúnmente utilizada para implementar árboles AVL. Verdadero. Falso.

Mantener un árbol equilibrado mejora la eficiencia de búsqueda porque reduce la altura del árbol. Verdadero. Falso.

Un árbol AVL es un árbol binario de búsqueda en el que las alturas de los subárboles izquierdo y derecho de cada nodo pueden diferir en más de una unidad. Verdadero. Falso.

El factor de equilibrio o balanceo de un nodo en un árbol AVL se calcula restando la altura del subárbol derecho de la altura del subárbol izquierdo. Verdadero. Falso.

En un árbol AVL, el factor de equilibrio de cada nodo puede ser 0, 1 o -1. Verdadero. Falso.

Si el factor de equilibrio de un nodo en un árbol AVL es 2, el árbol todavía está equilibrado. Verdadero. Falso.

El factor de equilibrio se calcula como la altura del subárbol derecho menos la altura del subárbol izquierdo. Verdadero. Falso.

Un árbol AVL es similar a un árbol binario de búsqueda (ABB), pero además mantiene un factor de equilibrio en cada nodo. Verdadero. Falso.

El árbol AVL es un tipo de árbol binario que no requiere mantener un balance entre los subárboles. Verdadero. Falso.

La diferencia principal entre un ABB y un árbol AVL es que el ABB no garantiza balanceo, mientras que el AVL sí. Verdadero. Falso.

El factor de equilibrio en un árbol AVL se calcula para decidir si un nodo necesita ser reequilibrado. Verdadero. Falso.

La operación de búsqueda en un árbol AVL es igual a la de un ABB, ya que no modifica la estructura del árbol. Verdadero. Falso.

Los recorridos inorden, preorden y postorden en un árbol AVL son distintos a los de un ABB. Verdadero. Falso.

Al insertar un nodo en un árbol AVL, primero se realiza la inserción como en un ABB, y luego se verifica y repara el equilibrio si es necesario. Verdadero. Falso.

La operación de borrado en un árbol AVL es más simple que en un ABB porque el árbol se equilibra automáticamente. Verdadero. Falso.

Insertar en un árbol AVL puede afectar el factor de equilibrio de varios nodos. Verdadero. Falso.

La inserción en un árbol AVL se realiza exactamente igual que en un árbol binario de búsqueda (ABB), hasta que se detecta un posible desequilibrio. Verdadero. Falso.

Si al insertar un nuevo nodo en un árbol AVL se rompe el equilibrio, este se puede restaurar mediante rotaciones con coste O(n). Verdadero. Falso.

El desequilibrio en un árbol AVL tras una inserción solo puede producirse a lo largo del camino desde el nodo insertado hasta la raíz. Verdadero. Falso.

Una vez realizada una rotación tras la inserción en un AVL, puede que aún sea necesario seguir reequilibrando otros nodos hacia arriba. Verdadero. Falso.

El coste de insertar un nodo en un AVL, incluyendo el reequilibrado, es O(log n). Verdadero. Falso.

Los desequilibrios en un árbol AVL se corrigen mediante rotaciones. Verdadero. Falso.

Existen exactamente cuatro tipos de rotaciones que se aplican para resolver todos los posibles desequilibrios en un árbol AVL. Verdadero. Falso.

Cada tipo de desequilibrio en un nodo 'a' tras una inserción corresponde a un único tipo de rotación específica. Verdadero. Falso.

La rotación doble consiste en aplicar dos rotaciones simples consecutivas para corregir un desequilibrio más complejo. Verdadero. Falso.

Las rotaciones en un árbol AVL pueden modificar toda la estructura del árbol. Verdadero. Falso.

Una rotación simple a la derecha se aplica cuando el desequilibrio ocurre tras insertar en el subárbol izquierdo del hijo izquierdo de un nodo. Verdadero. Falso.

Cuando bal(a) = 2 y bal(izq(a)) = 1, se debe aplicar una rotación simple a la izquierda. Verdadero. Falso.

El caso 1 de desequilibrio en AVL se denomina también caso izquierda-izquierda. Verdadero. Falso.

La rotación simple a la derecha reduce el factor de equilibrio de un nodo que tenía bal(a) = 2. Verdadero. Falso.

La rotación simple a la derecha puede generar desequilibrio en otros nodos fuera del subárbol afectado. Verdadero. Falso.

El caso 4 en un árbol AVL ocurre cuando se inserta en el subárbol derecho del hijo derecho de un nodo. Verdadero. Falso.

Cuando bal(a) = -2 y bal(der(a)) = -1, se debe aplicar una rotación simple a la derecha. Verdadero. Falso.

La rotación simple a la izquierda se utiliza para corregir desequilibrios en el lado derecho del árbol AVL. Verdadero. Falso.

La rotación simple a la izquierda corresponde al caso derecha-derecha. Verdadero. Falso.

Una rotación simple a la izquierda modifica toda la estructura del árbol AVL. Verdadero. Falso.

Cuando un nodo a pierde un subárbol por la derecha (como el nodo b), su factor de equilibrio debe incrementarse. Verdadero. Falso.

Si el subárbol Z (nuevo subárbol derecho de a) es más alto que Y, el balance de a se ve afectado negativamente. Verdadero. Falso.

El nodo b gana altura por la izquierda al recibir al nodo a como hijo. Verdadero. Falso.

Si el subárbol X (nuevo hijo izquierdo de b) es más alto que Y, entonces el factor de equilibrio de b se ajusta con bal(b) += bal(a). Verdadero. Falso.

Si los subárboles Y y Z tienen la misma altura, entonces el balance de a no cambia. Verdadero. Falso.

Las rotaciones dobles se aplican en los casos en que una rotación simple no es suficiente para corregir el desequilibrio. Verdadero. Falso.

Los casos 2 y 3 de desequilibrio en AVL se resuelven con una sola rotación simple. Verdadero. Falso.

Una rotación doble es la combinación de dos rotaciones simples aplicadas en orden. Verdadero. Falso.

En el caso izquierda-derecha (caso 2), primero se realiza una rotación simple a la derecha y luego una a la izquierda. Verdadero. Falso.

Las rotaciones dobles resuelven casos en los que el crecimiento ocurre en el subárbol interior del hijo del nodo desequilibrado. Verdadero. Falso.

El caso 2 de rotación en un árbol AVL se produce cuando se inserta en el subárbol derecho del hijo izquierdo de un nodo. Verdadero. Falso.

El desequilibrio en el caso 2 provoca que el factor de equilibrio de k3 sea igual a -2. Verdadero. Falso.

En el caso 2, una rotación doble izquierda-derecha es necesaria para reequilibrar el árbol. Verdadero. Falso.

La clave para resolver el caso 2 es que el nodo k2 (nieto del desequilibrado) pase a ser la nueva raíz del subárbol. Verdadero. Falso.

El caso 2 se puede resolver eficazmente con una única rotación simple a la derecha. Verdadero. Falso.

El caso 2 en AVL se resuelve con dos rotaciones: una a la izquierda en k1 y otra a la derecha en k3. Verdadero. Falso.

La rotación izquierda en k1 y la derecha en k2 solucionan correctamente el desequilibrio del caso 2. Verdadero. Falso.

En el caso 2, después de realizar las rotaciones, el nodo k2 se convierte en la raíz del subárbol reequilibrado. Verdadero. Falso.

El orden correcto de las rotaciones en el caso 2 es: primero a la derecha en k1, luego a la izquierda en k3. Verdadero. Falso.

El objetivo de las rotaciones dobles es corregir desequilibrios generados por inserciones en subárboles internos. Verdadero. Falso.

El caso 3 de rotación en un árbol AVL es simétrico al caso 2. Verdadero. Falso.

En el caso 3, el desequilibrio se produce en el nodo k1, con bal(k1) = -2. Verdadero. Falso.

La solución al caso 3 es realizar una rotación a la derecha en k3, seguida de una rotación a la izquierda en k2. Verdadero. Falso.

El nodo k2 se convierte en la nueva raíz del subárbol tras realizar las rotaciones en el caso 3. Verdadero. Falso.

El caso 3 ocurre cuando se inserta en el subárbol izquierdo del hijo derecho del nodo desequilibrado. Verdadero. Falso.

Al borrar un nodo en un árbol AVL, se debe reorganizar la información desde la hoja eliminada hasta la raíz. Verdadero. Falso.

Para eliminar un dato X en un árbol AVL, el proceso es diferente al de un ABB porque no se busca el dato X primero. Verdadero. Falso.

Después de eliminar un nodo, se debe verificar el factor de equilibrio en cada nodo del camino hacia la raíz. Verdadero. Falso.

En la eliminación de nodos en árboles AVL, puede ser necesario realizar más de una rotación para reequilibrar el árbol, a diferencia de la inserción. Verdadero. Falso.

Si el factor de equilibrio de un nodo después de la eliminación es 2 o -2, se debe proceder a realizar rotaciones para equilibrar. Verdadero. Falso.

Las rotaciones simples y dobles utilizadas para la inserción también se aplican durante el borrado en un árbol AVL. Verdadero. Falso.

Existe un caso nuevo en la eliminación cuando el nodo a borrar tiene dos hijos de la misma altura. Verdadero. Falso.

En el caso en que un nodo a borrar tiene dos hijos de igual altura, se puede resolver con una rotación simple a la derecha o a la izquierda. Verdadero. Falso.

En el caso especial de dos hijos de igual altura, siempre se debe realizar una rotación doble. Verdadero. Falso.

El uso de rotaciones simples a derecha o izquierda para el caso especial evita que el árbol quede desequilibrado tras la eliminación. Verdadero. Falso.

El tiempo de búsqueda en un árbol AVL es O(log n). Verdadero. Falso.

La inserción en un árbol AVL tiene un tiempo promedio de O(n). Verdadero. Falso.

Al insertar un nodo en un árbol AVL, trazar el camino desde el nuevo nodo hasta la raíz y comprobar las alturas tiene un coste O(log n). Verdadero. Falso.

Comprobar la diferencia de alturas y realizar una rotación en un nodo durante la inserción en un AVL tiene coste O(1). Verdadero. Falso.

El razonamiento sobre el coste de la inserción en AVL se aplica también al borrado, siendo también O(log n). Verdadero. Falso.

Los árboles AVL resuelven el problema de la eficiencia en la búsqueda. Verdadero. Falso.

Los árboles AVL permiten iterar fácilmente hacia delante o hacia atrás en el árbol. Verdadero. Falso.

Los recorridos recursivos en árboles AVL permiten iterar hacia delante y hacia atrás sin problemas. Verdadero. Falso.

La STL utiliza árboles rojo-negro que mantienen punteros al nodo padre para solucionar el problema de iteración. Verdadero. Falso.

Es interesante trabajar diferenciando la clave del dato y permitiendo claves repetidas, tal y como hace la STL. Verdadero. Falso.

Los árboles AVL son muy rápidos para realizar búsquedas. Verdadero. Falso.

Para que un árbol AVL sea rápido en la búsqueda, no es necesario que esté equilibrado. Verdadero. Falso.

Las rotaciones simples y dobles se utilizan en árboles AVL para mantener el equilibrio. Verdadero. Falso.

Las rotaciones simples en un árbol AVL tienen un coste constante O(1). Verdadero. Falso.

Un árbol AVL desbalanceado puede llegar a tener tiempo de búsqueda O(n). Verdadero. Falso.

Las rotaciones dobles en AVL se usan cuando el desequilibrio se encuentra en el hijo derecho del hijo izquierdo o viceversa. Verdadero. Falso.