El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Árboles AVL

Siguiente ►
►

Introducción a los Árboles AVL

Los árboles AVL son un tipo de árbol binario de búsqueda (BST) que se auto-balancean. Fueron los primeros árboles binarios de búsqueda auto-balanceados y fueron nombrados así por sus inventores, Adelson-Velsky y Landis. La propiedad clave de un árbol AVL es que para cada nodo, la diferencia de altura entre sus subárboles izquierdo y derecho no puede ser mayor que uno. Esta propiedad asegura que las operaciones de búsqueda, inserción y eliminación se realicen en tiempo logarítmico.

Propiedades de los Árboles AVL

  1. Balanceo: La diferencia de altura entre los subárboles izquierdo y derecho de cualquier nodo no puede ser mayor que uno.
  2. Altura: La altura de un árbol AVL con n nodos es O(log n).
  3. Rotaciones: Para mantener el balanceo, los árboles AVL utilizan rotaciones simples y dobles.

Rotaciones en Árboles AVL

Para mantener el balanceo, los árboles AVL utilizan cuatro tipos de rotaciones:

  1. Rotación Simple a la Derecha (Right Rotation):

    • Se utiliza cuando un nodo se inserta en el subárbol izquierdo del subárbol izquierdo.
        y                               x
   / \     Right Rotation          /  
         x   T3   – – – – – – – >        T1   y 
 / \       < - - - - - - -            / 
       T1  T2     Left Rotation             T2  T3

  2. Rotación Simple a la Izquierda (Left Rotation):

    • Se utiliza cuando un nodo se inserta en el subárbol derecho del subárbol derecho.
      x                            y
 /  \     Left Rotation       /  
       T1   y   – – – – – – – >     x   T3
    /  \   < - - - - - - -  /  
          T2   T3                 T1   T2

  3. Rotación Doble a la Izquierda-Derecha (Left-Right Rotation):

    • Se utiliza cuando un nodo se inserta en el subárbol derecho del subárbol izquierdo.
        z                               z                           x
   / \                            /   \                        /  \ 
  y   T4  Left Rotation (y)      x    T4  Right Rotation (z)  y    z
 / \      – – – – – – – – – >   /  \      – – – – – – – – – > / \  / 
       T1   x                          y    T3                      T1  T2 T3 T4
    /  \                       /  
          T2   T3                    T1   T2

  4. Rotación Doble a la Derecha-Izquierda (Right-Left Rotation):

    • Se utiliza cuando un nodo se inserta en el subárbol izquierdo del subárbol derecho.
        z                            z                            x
   / \                          / \                          /  \ 
  T1   y   Right Rotation (y)  T1   x   Left Rotation (z)   z    y
      / \  – – – – – – – – – >    /  \  – – – – – – – – – > / \  / 
            x   T4                      T2   y                    T1  T2 T3 T4
    /  \                            /  
          T2   T3                         T3   T4

Implementación de Árboles AVL

A continuación, se presenta una implementación básica de un árbol AVL en Python:

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def get_height(self, root):
        if not root:
            return 0
        return root.height

    def get_balance(self, root):
        if not root:
            return 0
        return self.get_height(root.left) - self.get_height(root.right)

    def right_rotate(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y

    def left_rotate(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y

    def insert(self, root, key):
        if not root:
            return Node(key)
        elif key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
        balance = self.get_balance(root)

        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)
        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    def pre_order(self, root):
        if not root:
            return
        print("{0} ".format(root.key), end="")
        self.pre_order(root.left)
        self.pre_order(root.right)

# Ejemplo de uso
avl_tree = AVLTree()
root = None
keys = [10, 20, 30, 40, 50, 25]

for key in keys:
    root = avl_tree.insert(root, key)

print("Preorden del árbol AVL:")
avl_tree.pre_order(root)

Explicación del Código

  1. Clase Node: Define un nodo del árbol AVL con atributos key, left, right y height.
  2. Clase AVLTree: Contiene métodos para manejar el árbol AVL:
    • get_height: Devuelve la altura de un nodo.
    • get_balance: Calcula el factor de balanceo de un nodo.
    • right_rotate y left_rotate: Realizan las rotaciones necesarias para mantener el balanceo del árbol.
    • insert: Inserta un nuevo nodo en el árbol y realiza las rotaciones necesarias para mantener el balanceo.
    • pre_order: Realiza un recorrido en preorden del árbol.

Ejercicio Práctico

Ejercicio: Implementa una función para eliminar un nodo en un árbol AVL y ajusta el balance del árbol después de la eliminación.

Solución:

def delete_node(self, root, key):
    if not root:
        return root

    elif key < root.key:
        root.left = self.delete_node(root.left, key)
    elif key > root.key:
        root.right = self.delete_node(root.right, key)
    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp

        temp = self.get_min_value_node(root.right)
        root.key = temp.key
        root.right = self.delete_node(root.right, temp.key)

    if root is None:
        return root

    root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
    balance = self.get_balance(root)

    if balance > 1 and self.get_balance(root.left) >= 0:
        return self.right_rotate(root)
    if balance > 1 and self.get_balance(root.left) < 0:
        root.left = self.left_rotate(root.left)
        return self.right_rotate(root)
    if balance < -1 and self.get_balance(root.right) <= 0:
        return self.left_rotate(root)
    if balance < -1 and self.get_balance(root.right) > 0:
        root.right = self.right_rotate(root.right)
        return self.left_rotate(root)

    return root

def get_min_value_node(self, root):
    if root is None or root.left is None:
        return root
    return self.get_min_value_node(root.left)

Conclusión

En esta sección, hemos aprendido sobre los árboles AVL, sus propiedades y cómo se mantienen balanceados mediante rotaciones. También hemos implementado un árbol AVL en Python y discutido cómo insertar y eliminar nodos mientras mantenemos el balance del árbol. Los árboles AVL son fundamentales para asegurar que las operaciones de búsqueda, inserción y eliminación se realicen en tiempo logarítmico, lo que es crucial para aplicaciones que requieren un rendimiento eficiente.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados