php 字典树实现

字典树（Trie）基础概念

字典树是一种树形数据结构，用于高效存储和检索字符串集合。核心特点是通过公共前缀共享节点，减少存储空间并提高查询效率。

PHP实现字典树

以下是一个完整的PHP字典树实现，包含插入、搜索和前缀匹配功能：

class TrieNode {
    public $children = [];
    public $isEndOfWord = false;
}

class Trie {
    private $root;

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

    public function insert($word) {
        $node = $this->root;
        $length = strlen($word);

        for ($i = 0; $i < $length; $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
        }
        $node->isEndOfWord = true;
    }

    public function search($word) {
        $node = $this->root;
        $length = strlen($word);

        for ($i = 0; $i < $length; $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                return false;
            }
            $node = $node->children[$char];
        }
        return $node->isEndOfWord;
    }

    public function startsWith($prefix) {
        $node = $this->root;
        $length = strlen($prefix);

        for ($i = 0; $i < $length; $i++) {
            $char = $prefix[$i];
            if (!isset($node->children[$char])) {
                return false;
            }
            $node = $node->children[$char];
        }
        return true;
    }
}

使用示例

$trie = new Trie();
$trie->insert("apple");
$trie->insert("app");

var_dump($trie->search("apple"));  // true
var_dump($trie->search("app"));    // true
var_dump($trie->search("ap"));     // false
var_dump($trie->startsWith("ap")); // true

性能优化建议

对于大规模数据应用，可考虑以下优化措施：

• 使用更紧凑的数据结构存储子节点
• 实现删除操作时需要处理节点清理
• 添加批量插入方法提高初始化效率
• 考虑内存回收机制

应用场景

字典树特别适合以下场景：

• 自动补全系统
• 拼写检查
• IP路由表查找
• 文本词频统计

该实现提供了字典树的核心功能，可根据具体需求进行扩展和完善。