PHP字典树(Trie树)定义与实现方法示例

定义

Trie树，也叫字典树或者单词查找树，是一种树形数据结构，常用于统计或者排序字符串数据集。它能够高效地支持字符串数据的插入、查找和前缀搜索等操作，时间复杂度与字符串长度有关，对于一定量的字符串集合，它的查找效率比哈希表更高。

Trie树与二叉查找树最大的不同在于，Trie树每个节点不仅仅存储一个关键码，而是存储一个关键码序列。Trie树的核心思想是利用字符串之间的公共前缀，将重复的前缀合并在一起，从而减少了存储空间，提高了查找效率。

实现

定义类

我们定义一个Trie树类TrieTree，它有以下三个属性：

• $root：根节点，初始时为空；
• $count：Trie树中单词的数量，初始为0；
• $size：Trie树中节点的数量，初始为1（根节点）。

class TrieTree {
    private $root;
    private $count;
    private $size;

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

定义节点类

我们定义Trie树中的节点类TrieNode，它有以下三个属性：

• $char：该节点存储的字符；
• $isEnd：是否为单词结尾，初始为false；
• $children：该节点的子节点，初始为空数组。

class TrieNode {
    public $char;
    public $isEnd;
    public $children;

    public function __construct($char = null) {
        $this->char = $char;
        $this->isEnd = false;
        $this->children = [];
    }
}

插入单词操作

Trie树的插入操作需要遍历整个单词，然后将单词的每个字符依次插入到Trie树中。

public function insert($word) {
    $node = $this->root;
    for ($i = 0; $i < strlen($word); $i++) {
        $char = $word[$i];
        if (!isset($node->children[$char])) {
            $node->children[$char] = new TrieNode($char);
            $this->size++;
        }
        $node = $node->children[$char];
    }
    if (!$node->isEnd) {
        $node->isEnd = true;
        $this->count++;
    }
}

查找单词操作

Trie树的查找操作需要遍历整个单词，然后判断每个字符是否存在于Trie树中。

public function search($word) {
    $node = $this->root;
    for ($i = 0; $i < strlen($word); $i++) {
        $char = $word[$i];
        if (!isset($node->children[$char])) {
            return false;
        }
        $node = $node->children[$char];
    }
    return $node->isEnd;
}

查找前缀操作

Trie树的查找前缀操作需要遍历前缀，然后判断每个字符是否存在于Trie树中。

public function startsWith($prefix) {
    $node = $this->root;
    for ($i = 0; $i < strlen($prefix); $i++) {
        $char = $prefix[$i];
        if (!isset($node->children[$char])) {
            return false;
        }
        $node = $node->children[$char];
    }
    return true;
}

示例

示例1：插入单词和查找单词操作

我们创建一个Trie树对象，插入若干个单词，然后查找某些单词是否存在。

$trie = new TrieTree();
$trie->insert('apple');
$trie->insert('banana');
$trie->insert('orange');
$trie->insert('pear');

echo $trie->search('apple'); // true
echo $trie->search('pear'); // true
echo $trie->search('watermelon'); // false

示例2：查找前缀操作

我们创建一个Trie树对象，插入一些单词，然后查找以某个前缀开头的单词个数。

$trie = new TrieTree();
$trie->insert('apple');
$trie->insert('banana');
$trie->insert('orange');
$trie->insert('pear');

echo $trie->startsWith('a'); // true
echo $trie->startsWith('ab'); // false
echo $trie->startsWith('pe'); // true