UNIVERSIDAD TECNOLÓGICA LA SALLE.
ULSA- LEÓN
Estructura de datos
DOCENTE: Ing. Aaron Cisneros
Tema:
Arboles AVL
Nombre: Nemman Eduardo Zuniga Zamora.
3° Año y Grupo 1- IMS – Modalidad: Diurno
Fecha: 24 de noviembre del 2023
MISO (Múltiple Input Single
Output) - "Entrada múltiple,
salida única". Cuando el
sistema
tiene varias entradas y una
salida
Para la explicación de este código vamos a iniciar con una función llamada max
La función max toma dos enteros, a y b, como parámetros y devuelve el valor
máximo entre ellos. Aquí hay una descomposición más detallada:
- int max(int a, int b): Esta línea define una función llamada max que toma dos
enteros como entrada (a y b) y devuelve un entero.
- return (a > b) ? a : b; Esta es una expresión ternaria que compara a y b. Si `a`
es mayor que b, la expresión devuelve a; de lo contrario, devuelve `b`. En otras
palabras, esta línea retorna el valor máximo entre a y b.
La función getHeight devuelve la altura de un nodo dado en el árbol AVL.
- struct TreeNode* node: Recibe un puntero al nodo del cual se quiere obtener
la altura.
-Si el nodo es NULL (es decir, no hay nodo), la función devuelve 0 ya que la
altura de un nodo nulo es cero.
- Si el nodo no es nulo, devuelve la altura almacenada en el campo height
del nodo. Este campo es actualizado durante las operaciones de inserción y
rotación para mantener la propiedad de equilibrio del árbol.
La función getBalanceFactor calcula y devuelve el factor de equilibrio de un
nodo en el árbol AVL.
- struct TreeNode* node: Recibe un puntero al nodo del cual se quiere obtener
el factor de equilibrio.
- Si el nodo es NULL, es decir, no hay nodo, la función devuelve `0` ya que
no hay nodos para comparar.
- Si el nodo no es nulo, resta la altura del subárbol derecho (getHeight(node-
>right)) de la altura del subárbol izquierdo (getHeight(node->left)). El resultado
es el factor de equilibrio del nodo.
Estas funciones son fundamentales para el mantenimiento y la verificación del
equilibrio en un árbol AVL. La función `getHeight` proporciona la altura de un
nodo, y `getBalanceFactor` utiliza esta información para calcular el factor de
equilibrio del nodo, lo que es crucial para determinar si se necesita una rotación
para restaurar el equilibrio del árbol.
En rotateRight, el nodo x (hijo izquierdo de y) se convierte en la nueva raíz, y y
se convierte en su hijo derecho. En rotateLeft, el nodo y (hijo derecho de x) se
convierte en la nueva raíz, y x se convierte en su hijo izquierdo. Estas
rotaciones se realizan para mantener el equilibrio en un árbol AVL después de
ciertas operaciones de inserción.
La función insertNode inserta un nuevo nodo con el valor dado en el árbol AVL
con raíz en root. También se encarga de mantener el equilibrio del árbol
mediante rotaciones si es necesario.
struct TreeNode* root: Es el nodo raíz del árbol en el que se va a realizar la
inserción.
int value: Es el valor que se quiere insertar en el árbol.
Si el árbol está vacío (`root == NULL`), crea un nuevo nodo con el valor dado y
lo devuelve como la nueva raíz. Este nuevo nodo tiene altura 1.
- Si el árbol no está vacío, realiza la inserción estándar de BST (árbol de
búsqueda binaria) para colocar el nuevo nodo en la posición adecuada en
función de su valor.
- Después de la inserción, obtiene el factor de equilibrio del nodo actual
mediante getBalanceFactor.
- Si el factor de equilibrio indica un desequilibrio (menor a -1 o mayor a 1),
realiza las rotaciones necesarias (rotateRight o rotateLeft) para restaurar el
equilibrio.
- Devuelve la raíz actualizada después de la inserción.
La función está diseñada para mantener el árbol AVL equilibrado después de
cada inserción. El equilibrio se controla mediante la actualización de las alturas
de los nodos y la realización de rotaciones cuando sea necesario.
