为什么trie又叫“前缀树”？

Question

我在维基百科上读到了这的文章，无意中发现了这句话："trie也叫前缀树“。

我知道trie的用法，但为什么它被称为“前缀树”呢？

Answer 1

因为它们可以被前缀搜索。您还可以反转trie并找到通配符：http://phpir.com/tries-and-wildcards。

例如，学术术语是c-i-m-e-d-a-c-a。使用与以前相同的技术，我们现在可以搜索以某个短语结尾的所有单词，允许我们在查询术语的开头处理通配符，例如*按韵律。

<?php
function buildTries($words) {
        $trie = new Trie();
        $rtrie = new Trie();
        foreach($words as $word) {
                $trie->add($word);
                $rtrie->add(strrev($word));
        }
        return array('trie' => $trie, 'rtrie' => $rtrie);
}

function searchTries($search, $tries) {
        $terms = explode('*', $search);
        if(count($terms) > 2) {
                return false;
        }

        if(strlen($terms[0]) && strlen($terms[0])) {
                // middle wildcard
                $straight = $tries['trie']->prefixSearch($terms[0]);
                $rev = $tries['rtrie']->prefixSearch(strrev($terms[1]));
                return array_intersect($straight, reverseArray($rev));
        } else if(strlen($terms[1]) ) {
                // leading wildcard
                return reverseArray($tries['rtrie']->prefixSearch(strrev($terms[1])));
        } else {
                // trailing wildcard
                return $tries['trie']->prefixSearch($terms[0]);
        }
}

function reverseArray($keys) {
        $return = array();
        foreach($keys as $key => $value) {
                $return[strrev($key)] = $value;
        }
        return $return;
}

/* Do some searches */

$words = array( 
        'adder',
        'addled',
        'abject',
        'agreement',
        'astronaut',
        'handily', 
        'happily',
        'helpfully'
);
$tries = buildTries($words);

$return = searchTries('h*ly', $tries);
var_dump($return);

$return = searchTries('ha*ly', $tries);
var_dump($return);
?>

两个var转储的结果如下所示：

array(3) {
  ["handily"]=>
  NULL
  ["happily"]=>
  NULL
  ["helpfully"]=>
  NULL
}

array(2) {
  ["handily"]=>
  NULL
  ["happily"]=>
  NULL
}