Implementando Árboles Binarios de Búsqueda Autobalanceados (AVL) en PHP

Los Árboles Binarios de Búsqueda (BST) son estructuras de datos poderosas para la búsqueda, inserción y eliminación eficiente de elementos. Sin embargo, en el peor de los casos (cuando los datos están ordenados), un BST puede degenerar en una lista enlazada, perdiendo su eficiencia. Los árboles AVL son una optimización de los BST que se autobalancean para garantizar una altura logarítmica, manteniendo un rendimiento óptimo incluso en casos de inserciones y eliminaciones desfavorables. En este artículo, exploraremos cómo implementar un árbol AVL en PHP.

<?php

class AVLNode {
    public $key;
    public $value;
    public $height;
    public $left;
    public $right;

    public function __construct($key, $value) {
        $this->key = $key;
        $this->value = $value;
        $this->height = 1; // Altura inicial de un nodo hoja
        $this->left = null;
        $this->right = null;
    }
}

class AVLTree {
    private $root;

    public function __construct() {
        $this->root = null;
    }

    private function height(?AVLNode $node): int {
        return $node ? $node->height : 0;
    }

    private function updateHeight(?AVLNode $node): void {
        $node->height = 1 + max($this->height($node->left), $this->height($node->right));
    }

    private function getBalance(?AVLNode $node): int {
        return $node ? $this->height($node->left) - $this->height($node->right) : 0;
    }

    private function rotateRight(?AVLNode $y): ?AVLNode {
        $x = $y->left;
        $T2 = $x->right;

        // Rotación
        $x->right = $y;
        $y->left = $T2;

        // Actualizar alturas
        $this->updateHeight($y);
        $this->updateHeight($x);

        return $x;
    }

    private function rotateLeft(?AVLNode $x): ?AVLNode {
        $y = $x->right;
        $T2 = $y->left;

        // Rotación
        $y->left = $x;
        $x->right = $T2;

        // Actualizar alturas
        $this->updateHeight($x);
        $this->updateHeight($y);

        return $y;
    }

    public function insert(?AVLNode $node, $key, $value): ?AVLNode {
        // Inserción estándar de BST
        if ($node === null) {
            return new AVLNode($key, $value);
        }

        if ($key < $node->key) {
            $node->left = $this->insert($node->left, $key, $value);
        } elseif ($key > $node->key) {
            $node->right = $this->insert($node->right, $key, $value);
        } else {
            // Clave duplicada no permitida
            return $node;
        }

        // Actualizar altura del nodo actual
        $this->updateHeight($node);

        // Obtener el factor de balance del nodo
        $balance = $this->getBalance($node);

        // Si el nodo no está balanceado, hay 4 casos
        // Caso Izquierda Izquierda
        if ($balance > 1 && $key < $node->left->key) {
            return $this->rotateRight($node);
        }

        // Caso Derecha Derecha
        if ($balance < -1 && $key > $node->right->key) {
            return $this->rotateLeft($node);
        }

        // Caso Izquierda Derecha
        if ($balance > 1 && $key > $node->left->key) {
            $node->left = $this->rotateLeft($node->left);
            return $this->rotateRight($node);
        }

        // Caso Derecha Izquierda
        if ($balance < -1 && $key < $node->right->key) {
            $node->right = $this->rotateRight($node->right);
            return $this->rotateLeft($node);
        }

        return $node;
    }

    public function insertKey($key, $value): void {
        $this->root = $this->insert($this->root, $key, $value);
    }

    // (El resto de métodos: eliminar, buscar, etc., seguirían la misma lógica AVL)
}

// Ejemplo de uso
$tree = new AVLTree();
$tree->insertKey(10, "Valor 10");
$tree->insertKey(20, "Valor 20");
$tree->insertKey(30, "Valor 30");
$tree->insertKey(40, "Valor 40");
$tree->insertKey(50, "Valor 50");
$tree->insertKey(25, "Valor 25");

// La raíz ahora apuntará al árbol AVL balanceado.
?>
    

Este código proporciona una implementación básica de la inserción en un árbol AVL. Los métodos `rotateRight` y `rotateLeft` realizan las rotaciones necesarias para mantener el árbol balanceado. El método `getBalance` determina si un nodo está balanceado basándose en la diferencia de alturas entre sus subárboles izquierdo y derecho. Es importante recordar que la eliminación de nodos en un árbol AVL es más compleja que la inserción y requerirá implementar lógica adicional para mantener el balance.

El código presentado es un punto de partida. Una implementación completa de un árbol AVL requeriría la inclusión de métodos para eliminar nodos, buscar nodos, y quizás un método para imprimir el árbol para su visualización y depuración. Además, la optimización del rendimiento podría ser considerada, especialmente si el árbol se espera que maneje grandes cantidades de datos.