你们好，最近小艾特发现有诸多的小伙伴们对于tries hard翻译，tries这个问题都颇为感兴趣的，今天小活为大家梳理了下，一起往下看看吧。

1、用字符集{bear，bid , sun，sunday }构建的Tries树如图所示。

2、特点：

3、1、根节点不存储字符，除根节点外每个字符包含字符。

4、2、从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串

5、3、每个单词的公共前缀作为一个字符节点保存。

6、Tries实现方式。

7、Tries 可以通过二维数组，链表，二叉树等结构实现。

8、Tries节点的结构。

9、JAVA 实现方式

10、class TrieNode {

11、 // R links to node children

12、 private TrieNode[] links;

13、 private final int R = 26;

14、 private boolean isEnd;

15、 public TrieNode() {

16、 links = new TrieNode[R];

17、 }

18、 public boolean containsKey(char ch) {

19、 return links[ch -'a'] != null;

20、 }

21、 public TrieNode get(char ch) {

22、 return links[ch -'a'];

23、 }

24、 public void put(char ch, TrieNode node) {

25、 links[ch -'a'] = node;

26、 }

27、 public void setEnd() {

28、 isEnd = true;

29、 }

30、 public boolean isEnd() {

31、 return isEnd;

32、 }

33、}

34、插入操作Java实现：

35、class Trie {

36、 private TrieNode root;

37、 public Trie() {

38、 root = new TrieNode();

39、 }

40、 // Inserts a word into the trie.

41、 public void insert(String word) {

42、 TrieNode node = root;

43、 for (int i = 0; i < word.length(); i++) {

44、 char currentChar = word.charAt(i);

45、 if (!node.containsKey(currentChar)) {

46、 node.put(currentChar, new TrieNode());

47、 }

48、 node = node.get(currentChar);

49、 }

50、 node.setEnd();

51、 }

52、}

53、时间复杂度

54、最坏情况O(N）；N为节点的个数。

55、搜索与插入操作的时间复杂度：O(p)。p为单词的长度。

56、应用：

57、Trie树的应用有很多，比如说拼写矫正，单词自动补充完整，IP路由的最长前缀匹配等。

以上就是tries这篇文章的一些介绍，希望对大家有所帮助。