árbol radix en php: cómo implementarlo

class RadixNode {
public array $children = [];// string prefix => RadixNode
public mixed $value = null;// valor si termina una palabra aquí
public bool $isEndOfWord = false;
}

class RadixTree {
private RadixNode $root;

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

public function insert(string $key, mixed $value = null): void {
$node = $this->root;
$i = 0;
$keyLength = strlen($key);

while ($i < $keyLength) {
  $matched = false;

  foreach ($node->children as $prefix => $child) {
  $common = $this->commonPrefixLength($key, $i, $prefix);

  if ($common > 0) {
 // Hay coincidencia parcial o total
 if ($common === strlen($prefix)) {
// El prefijo entero coincide → bajamos al hijo
$node = $child;
$i += $common;
 } else {
// Coincidencia parcial → partimos el nodo existente
$this->splitNode($node, $prefix, $common, $child);
// Ahora insertamos el resto en el nuevo nodo intermedio
$newNode = $node->children[substr($key, $i, $common)];
$newNode->children[substr($key, $i + $common)] = new RadixNode();
$node = $newNode->children[substr($key, $i + $common)];
$node->value = $value;
$node->isEndOfWord = true;
return;
 }
 $matched = true;
 break;
  }
  }

  if (!$matched) {
  // No hay coincidencia → nuevo hijo directo
  $remaining = substr($key, $i);
  $node->children[$remaining] = new RadixNode();
  $node = $node->children[$remaining];
  $node->value = $value;
  $node->isEndOfWord = true;
  return;
  }
}

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

private function commonPrefixLength(string $key, int $start, string $prefix): int {
$len = 0;
$max = min(strlen($key) - $start, strlen($prefix));
while ($len < $max && $key[$start + $len] === $prefix[$len]) {
  $len++;
}
return $len;
}

private function splitNode(RadixNode $parent, string $oldPrefix, int $splitAt, RadixNode $child): void {
$commonPart = substr($oldPrefix, 0, $splitAt);
$remainingOld = substr($oldPrefix, $splitAt);

// Creamos nodo intermedio
$midNode = new RadixNode();
$midNode->children[$remainingOld] = $child;

// Reemplazamos el viejo prefijo por el común
unset($parent->children[$oldPrefix]);
$parent->children[$commonPart] = $midNode;
}

public function search(string $key): mixed {
$node = $this->findNode($key);
return $node && $node->isEndOfWord ? $node->value : null;
}

public function startsWith(string $prefix): bool {
return $this->findNode($prefix) !== null;
}

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

$results = [];
$this->collectAll($node, $prefix, $results);
return $results;
}

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

while ($i < $len) {
  $matched = false;
  foreach ($node->children as $p => $child) {
  $common = $this->commonPrefixLength($key, $i, $p);
  if ($common > 0) {
 if ($common < strlen($p)) {
// No coincide todo el prefijo → no existe
return null;
 }
 $node = $child;
 $i += $common;
 $matched = true;
 break;
  }
  }
  if (!$matched) return null;
}
return $node;
}

private function collectAll(RadixNode $node, string $current, array &$results): void {
if ($node->isEndOfWord) {
  $results[$current] = $node->value;
}
foreach ($node->children as $prefix => $child) {
  $this->collectAll($child, $current . $prefix, $results);
}
}
}

// ---------------------- EJEMPLO DE USO ----------------------
$tree = new RadixTree();

$tree->insert("gato", "animal felino");
$tree->insert("gatito", "bebé gato");
$tree->insert("gata", "hembra del gato");
$tree->insert("perro", "mejor amigo del hombre");
$tree->insert("perrito", "cachorro");

echo "Búsqueda exacta:\n";
var_dump($tree->search("gato")); // "animal felino"
var_dump($tree->search("gat"));  // null

echo "\nPrefijos:\n";
var_dump($tree->startsWith("gat"));// true
var_dump($tree->startsWith("gatote")); // false

echo "\nTodas las palabras con prefijo 'gat':\n";
print_r($tree->getAllWithPrefix("gat"));
// Muestra: gato, gatito, gata