ÁRBOL DE PATRICIA EN PHP: CÓMO IMPLEMENTARLO

class PatriciaNode {
    public ?string $label = null;     // fragmento de clave en esta arista
    public mixed $value = null;  // valor si es fin de palabra
    /** @var PatriciaNode[] */
    public array $children = [];      // hijos: primer carácter → nodo
}

class PatriciaTrie {
    private PatriciaNode $root;

    public function __construct() {
   $this->root = new PatriciaNode();
    }
    //Inserta una clave con su valor (por defecto true si solo quieres un set)
    public function insert(string $key, mixed $value = true): void {
   $node = $this->root;
   $i = 0;
   $len = strlen($key);

   while ($i < $len) {
  $char = $key[$i];

  if (isset($node->children[$char])) {
      $child = $node->children[$char];
      $common = $this->commonPrefixLength($child->label, substr($key, $i));

      if ($common === strlen($child->label)) {
     // todo el label coincide → seguimos al hijo
     $node = $child;
     $i += $common;
     continue;
      }

      // Divergencia en el medio del label → split
      $splitNode = new PatriciaNode();
      $splitNode->label = substr($child->label, 0, $common);

      $newChild = new PatriciaNode();
      $newChild->label = substr($child->label, $common);
      $newChild->value = $child->value;
      $newChild->children = $child->children;

      $splitNode->children[$newChild->label[0]] = $newChild;

      // Reemplazamos el hijo original por el nodo split
      $node->children[$char] = $splitNode;

      // Insertamos la nueva rama en el splitNode
      $node = $splitNode;
      $i += $common;
  } else {
      // No existe rama → creamos nueva
      $newNode = new PatriciaNode();
      $newNode->label = substr($key, $i);
      $newNode->value = $value;

      $node->children[$char] = $newNode;
      return;
  }
   }

   // Llegamos al final de la clave
   $node->value = $value;
    }

    // Busca una clave exacta y devuelve su valor (o null)
    public function search(string $key): mixed {
   $node = $this->findNode($key);
   return $node ? $node->value : null;
    }

    //¿Existe alguna clave que empiece con este prefijo?
    public function startsWith(string $prefix): bool {
   return $this->findNode($prefix) !== null;
    }

    // Devuelve todas las claves completas que empiezan con el prefijo
    //(útil para autocompletado)
    // @return string[]

    public function getAllWithPrefix(string $prefix): array {
   $result = [];
   $node = $this->findNode($prefix);

   if ($node === null) {
  return [];
   }

   $this->collectKeys($node, $prefix, $result);
   return $result;
    }

    private function findNode(string $key): ?PatriciaNode {
   $node = $this->root;
   $i = 0;
   $len = strlen($key);

   while ($i < $len) {
  $char = $key[$i];

  if (!isset($node->children[$char])) {
      return null;
  }

  $child = $node->children[$char];
  $labelLen = strlen($child->label);
  $remaining = substr($key, $i);

  if (strncmp($child->label, $remaining, $labelLen) !== 0) {
      return null;
  }

  $node = $child;
  $i += $labelLen;
   }

   return $node;
    }

    private function collectKeys(PatriciaNode $node, string $current, array &$result): void {
   if ($node->value !== null) {
  $result[] = $current;
   }

   foreach ($node->children as $child) {
  $this->collectKeys($child, $current . $child->label, $result);
   }
    }

    private function commonPrefixLength(string $a, string $b): int {
   $len = min(strlen($a), strlen($b));
   for ($i = 0; $i < $len; $i++) {
  if ($a[$i] !== $b[$i]) {
      return $i;
  }
   }
   return $len;
    }
}

$trie = new PatriciaTrie();

$trie->insert("romano", "Romania o romano antiguo");
$trie->insert("romero", "Hierba aromática");
$trie->insert("rosa", "Flor");
$trie->insert("rosario", "Objeto de oración");
$trie->insert("ruta", "Camino");

echo $trie->search("romero") ? "Encontrado: " . $trie->search("romero") : "No encontrado\n";
// Salida: Encontrado: Hierba aromática

var_dump($trie->startsWith("ros"));     // true
var_dump($trie->startsWith("rox"));     // false

print_r($trie->getAllWithPrefix("ro"));
// Posible salida:
// Array
// (
//     [0] => romano
//     [1] => romero
//     [2] => rosa
//     [3] => rosario
//     [4] => ruta
// )