前缀树
Trie
trie
是一种离散的数据结构，在典型的算法数据结构中并不十分知名或被广泛提及，但仍然是一个重要的结构。
trie
（也称为字典树），有时甚至是基数树或前缀树（因为它们可以通过前缀搜索），是一种有序的树结构，它利用了它存储的键，本文假设是字符串。
节点在树中的位置定义了与该节点关联的键，这与二叉搜索树相比有所不同，其中节点存储仅对应于该节点的键。
一个节点的所有后代都有一个与该节点关联的字符串的公共前缀，而根与一个空字符串相关联。
这里我们有一个
TrieNode
的预览，我们将在我们的
Trie
实现中使用它：
type TrieNode struct {
children map[string]*TrieNode
value string
end bool
func NewTrieNode(e string) *TrieNode {
ret := make(map[string]*TrieNode)
return &TrieNode{
children: ret,
value: e,
end: true,
可能存在trie是二叉搜索树的情况，但总的来说，这些情况是不同的。二叉搜索树和前缀树都是树，但是二叉搜索树中的每个节点总是有两个孩子，而前缀树的节点可以有更多。
在trie中，每个节点（根节点除外）都存储一个字符或一个数字。通过从根节点向下遍历trie到特定节点n，可以形成字符或数字的公共前缀，该前缀也由trie的其他分支共享。
通过从叶子节点到根节点遍历树，可以形成一个字符串或一个数字序列。
这是Trie结构体，它表示trie数据结构的实现：
type Trie struct {
sync.RWMutex
root *TrieNode
func NewTrie() *Trie {
return &Trie{
root: &TrieNode{
children: make(map[string]*TrieNode),
现在，让我们看看如何实现基本操作。
我们将描述的第一个操作是插入新节点。在我们开始实现之前，了解算法很重要：
将当前节点设置为根节点
将当前字母设置为单词的第一个字母
如果当前节点已经存在对当前字母的引用（通过children字段中的元素之一），则将当前节点设置为该引用节点。否则，创建一个新节点，设置字母等于当前字母，并将当前节点初始化为这个新节点
重复第3步，直到找到key
该算法的复杂度为O(n)，其中n表示key大小。
下面是这个算法的实现：
func (t *Trie) Insert(word string) {
t.Lock()
defer t.Unlock()
current := t.root
for i := 0; i < len(word); i++ {
if child, ok := current.children[string(word[i])]; ok {
current = child
} else {
current.children[string(word[i])] = NewTrieNode(string(word[i]))
current = current.children[string(word[i])]
current.end = true
现在让我们添加一个方法来搜索特定元素是否已经存在于trie中：
获取根的children
遍历字符串的每个字符
检查该字符是否已经是子树的一部分。如果它不存在于trie中的任何位置，则停止搜索并返回false
重复第二步和第三步，直到字符串中没有任何字符。如果到达string的末尾，则返回 true
该算法的复杂度为O(n)，其中n表示key的长度。
func (t *Trie) Search(word string) bool {
t.Lock()
defer t.Unlock()
current := t.root
for i := 0; i < len(word); i++ {
node := current.children[string(word[i])]
if node == nil {
return false
current = node
return current.end
除了插入和查找元素之外，很明显我们还需要能够删除元素。对于删除过程，我们需要按照以下步骤操作：
检查这个元素是否已经是trie的一部分
如果找到该元素，则将其从trie中删除
该算法的复杂度为O(n)，其中n表示key的长度。让我们快速看一下实现：
func (t *Trie) Delete(word string) {
t.Lock()
defer t.Unlock()
_ = deleteNode(t.root, word, 0)
func deleteNode(cur *TrieNode, word string, index int) bool {
if index == len(word) {
if !cur.end {
return false
cur.end = false
return len(cur.children) == 0
node := cur.children[string(word[index])]
if node == nil {
return false
shouldDeleteCurrentNode := deleteNode(node, word, index+1) && !node.end
if shouldDeleteCurrentNode {
delete(cur.children, string(word[index]))
return len(cur.children) == 0
return false
在leetcode.208.实现 Trie (前缀树)中，特别定义了StartsWith方法。如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。这只需要在搜索方法基础上改动些许即可，当遍历待匹配的字符串结束后，我们直接返回true。
func (t *Trie) StartsWith(prefix string) bool {
current := t.root
for i := 0; i < len(prefix); i++ {
node, ok := current.children[string(prefix[i])]
if !ok {
return false
current = node
return true
这里也给出该题的题解：
type Trie struct {
root *TrieNode
func NewTrieNode(e string) *TrieNode {
ret := make(map[string]*TrieNode)
return &TrieNode{
children: ret,
value: e,
end: false,
type TrieNode struct {
children map[string]*TrieNode
value string
end bool
func Constructor() Trie {
return Trie{
root: &TrieNode{
children: make(map[string]*TrieNode),
func (t *Trie) Insert(word string) {
current := t.root
for i := 0; i < len(word); i++ {
if current.children == nil {
current.children = make(map[string]*TrieNode)
if child, ok := current.children[string(word[i])]; ok {
current = child
} else {
current.children[string(word[i])] = NewTrieNode(string(word[i]))
current = current.children[string(word[i])]
current.end = true
func (t *Trie) Search(word string) bool {
current := t.root
for i := 0; i < len(word); i++ {
node := current.children[string(word[i])]
if node == nil {
return false
current = node
return current.end
func (t *Trie) StartsWith(word string) bool {
current := t.root
for i := 0; i < len(word); i++ {
node := current.children[string(word[i])]
if node == nil {
return false
current = node
return true
复制代码
