Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
images
README_en.md
ReadMe.md
Trie.swift

ReadMe.md

字典树(Trie)

这个话题已经有个辅导文章

什么是字典树

Trie(在一些其他实现中也称为前缀树或基数树)是用于存储关联数据结构的特殊类型的树。 Trie作为一个字典可能如下所示:

A Trie

存储英语是Trie的主要用处。 Trie中的每个节点都代表一个单词的单个字符。 然后,一系列节点组成一个单词。

为什么需要字典树?

字典树对某些情况非常有用。 以下是一些优点:

  • 查找值通常具有更好的最坏情况时间复杂度。
  • 与哈希映射不同,Trie不需要担心键冲突。
  • 不使用散列来保证元素的唯一路径。
  • Trie结构默认按字母顺序排列。

常用算法

包含(或任何常规查找方法)

Trie结构非常适合查找操作。 对于模拟英语语言的Trie结构,找到一个特定的单词就是几个指针遍历的问题:

func contains(word: String) -> Bool {
	guard !word.isEmpty else { return false }

	// 1
	var currentNode = root
  
	// 2
	var characters = Array(word.lowercased().characters)
	var currentIndex = 0
 
	// 3
	while currentIndex < characters.count, 
	  let child = currentNode.children[characters[currentIndex]] {

	  currentNode = child
	  currentIndex += 1
	}

	// 4
	if currentIndex == characters.count && currentNode.isTerminating {
	  return true
	} else {
	  return false
	}
}

contains方法相当简单:

  1. 创建对root的引用。 此引用将允许您沿着节点链向下走。
  2. 跟踪你想要匹配的单词的字符。
  3. 将指针向下移动节点。
  4. isTerminating是一个布尔标志,表示该节点是否是单词的结尾。 如果满足此if条件,则意味着您可以在trie中找到该单词。

插入

插入Trie需要您遍历节点,直到您停止必须标记为terminating的节点,或者到达需要添加额外节点的点。

func insert(word: String) {
  guard !word.isEmpty else {
    return
  }

  // 1
  var currentNode = root

  // 2
  for character in word.lowercased().characters {
    // 3
    if let childNode = currentNode.children[character] {
      currentNode = childNode
    } else {
      currentNode.add(value: character)
      currentNode = currentNode.children[character]!
    }
  }
  // Word already present?
  guard !currentNode.isTerminating else {
    return
  }

  // 4
  wordCount += 1
  currentNode.isTerminating = true
}
  1. 再次,您创建对根节点的引用。 您将此引用沿着节点链移动。
  2. 逐字逐句地逐字逐句
  3. 有时,要插入的节点已存在。 这是Trie里面两个共享字母的词(即“Apple”,“App”)。如果一个字母已经存在,你将重复使用它,并简单地遍历链条。 否则,您将创建一个表示该字母的新节点。
  4. 一旦结束,将isTerminating标记为true,将该特定节点标记为单词的结尾。

删除

从字典树中删除键有点棘手,因为还有一些情况需要考虑。 Trie中的节点可以在不同的单词之间共享。 考虑两个词“Apple”和“App”。 在Trie中,代表“App”的节点链与“Apple”共享。

如果你想删除“Apple”,你需要注意保持“App”链。

func remove(word: String) {
  guard !word.isEmpty else {
    return
  }

  // 1
  guard let terminalNode = findTerminalNodeOf(word: word) else {
    return
  }

  // 2
  if terminalNode.isLeaf {
    deleteNodesForWordEndingWith(terminalNode: terminalNode)
  } else {
    terminalNode.isTerminating = false
  }
  wordCount -= 1
}
  1. findTerminalNodeOf遍历字典树,找到代表word的最后一个节点。 如果它无法遍历字符串,则返回nil
  2. deleteNodesForWordEndingWith遍历后缀,删除word表示的节点。

时间复杂度

设n是Trie中某个值的长度。

  • contains - 最差情况O(n)
  • insert - O(n)
  • remove - O(n)

其他值得注意的操作

  • count:返回Trie中的键数 —— O(1)
  • words:返回包含Trie中所有键的列表 —— O(1)
  • isEmpty:如果Trie为空则返回true,否则返回false —— O(1)

扩展阅读字典树的维基百科

作者:Christian Encarnacion, Kelvin Lau
翻译:Andy Ron 校对:Andy Ron

You can’t perform that action at this time.