Algoritmos y Estructura de Datos

Los árboles AVL son un tipo de árbol binario de búsqueda que se autobalancea para mantener una altura óptima y garantizar una complejidad de tiempo de inserción, eliminación y búsqueda de O(log n). Esto significa que, incluso si se insertan o eliminan muchos elementos del árbol, la altura del árbol seguirá siendo logarítmica en función del número de nodos, lo que garantiza un rendimiento rápido para estas operaciones.

Para garantizar el balance del árbol, cada nodo del árbol AVL tiene un factor de balance, que es la diferencia entre la altura de su hijo izquierdo y su hijo derecho. Si el factor de balance de un nodo es mayor que 1 o menor que -1, se realiza una rotación en el árbol para equilibrarlo.

Inserción:

Para insertar un elemento en un árbol AVL, debes seguir los mismos pasos que para insertar en un árbol binario de búsqueda. Después de insertar el elemento, debes ajustar el factor de balance de cada nodo a lo largo del camino desde la raíz hasta el nodo insertado. Si el factor de balance de un nodo es mayor que 1 o menor que -1 después de la inserción, debes realizar una rotación en el árbol para equilibrarlo.

                    

                        
// Estructura de nodo para árbol AVL
struct Node {
  int key;
  int balance;
  Node *left;
  Node *right;

  Node(int k) : key(k), balance(0), left(nullptr), right(nullptr) {}
};

// Clase para árbol AVL
class AVLTree {
 public:
  // Constructor
  AVLTree() : root_(nullptr) {}

  // Método para insertar un elemento en el árbol
  void Insert(int key) {
    root_ = Insert(root_, key);
  }

 private:
  // Método recursivo para insertar un elemento en el árbol
  Node* Insert(Node* node, int key) {
    // Caso base: si el nodo es null, insertamos el elemento aquí
    if (node == nullptr) {
      return new Node(key);
    }

    // Si el elemento es menor que el nodo actual, lo insertamos en el hijo izquierdo
    if (key < node->key) {
      node->left = Insert(node->left, key);
    } else {  // Si el elemento es mayor o igual, lo insertamos en el hijo derecho
      node->right = Insert(node->right, key);
    }

    // Actualizamos el factor de balance del nodo
    UpdateBalance(node);

    // Si el factor de balance es mayor que 1 o menor que -1, realizamos una rotación para equilibrar el árbol
    if (node->balance > 1 || node->balance < -1) {
      node = Balance(node);
    }

    // Devolvemos el nodo
    return node;
  }
}
                    
                

Eliminación:

Para eliminar un elemento de un árbol AVL, debes seguir los mismos pasos que para eliminar en un árbol binario de búsqueda. Después de eliminar el elemento, debes ajustar el factor de balance de cada nodo a lo largo del camino desde la raíz hasta el nodo eliminado. Si el factor de balance de un nodo es mayor que 1 o menor que -1 después de la eliminación, debes realizar una rotación en el árbol para equilibrarlo.

Búsqueda:

Para buscar un elemento en un árbol AVL, debes seguir los mismos pasos que para buscar en un árbol binario de búsqueda. Esto significa que debes comparar el elemento que estás buscando con cada nodo del árbol mientras avanzas hacia abajo a través del árbol. Si el elemento que estás buscando es menor que el nodo actual, debes ir al hijo izquierdo del nodo; si es mayor, debes ir al hijo derecho. Continúas este proceso hasta encontrar el elemento o hasta llegar a un nodo vacío, lo que indica que el elemento no se encuentra en el árbol.

La complejidad de la búsqueda en un árbol AVL es O(log n), ya que la altura del árbol es logarítmica en función del número de nodos. Esto significa que, incluso si el árbol tiene muchos nodos, la búsqueda será rápida y eficiente.

Link de apoyo