á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
// )