Trie树(字典树)的介绍及Java实现

蔚落 2022-03-27 14:10 219阅读 0赞

**简介**

Trie树，又称为前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。

**它的主要特点如下：**

根节点不包含字符，除根节点外的每一个节点都只包含一个字符。

从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

每个节点的所有子节点包含的字符都不相同。

**如下是一棵典型的Trie树:**

![201724100400516.png_20171410437][]

Trie的来源是Retrieval,它常用于前缀匹配和词频统计。可能有人要说了，词频统计简单啊，一个hash或者一个堆就可以搞定，但问题来了，如果内存有限呢？还能这么 玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。

**1、定义**

这里为了简化，只考虑了26个小写字母。

首先是节点的定义:

[?][Link 1]

然后是Trie树的定义:

[?][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>public</code> 
      <code>class</code> 
      <code>TrieTree { </code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>private</code> 
      <code>TrieNode root;</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>public</code> 
      <code>TrieTree(){ </code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>root=</code> 
      <code>new</code> 
      <code>TrieNode();</code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>...</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**2、插入**

由于是26叉树，故可通过charArray\[index\]-‘a';来得知字符应该放在哪个孩子中。

[?][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> 
    <div>
      16 
    </div> 
    <div>
      17 
    </div> 
    <div>
      18 
    </div> 
    <div>
      19 
    </div> 
    <div>
      20 
    </div> 
    <div>
      21 
    </div> 
    <div>
      22 
    </div> 
    <div>
      23 
    </div> 
    <div>
      24 
    </div> 
    <div>
      25 
    </div> 
    <div>
      26 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>public</code> 
      <code>void</code> 
      <code>insert(String word){ </code> 
     </div> 
     <div> 
      <code>if</code> 
      <code>(TextUtils.isEmpty(word)){ </code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>return</code> 
      <code>;</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div> 
      <code>insertNode(root,word.toCharArray(),</code> 
      <code>0</code> 
      <code>);</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>private</code> 
      <code>static</code> 
      <code>void</code> 
      <code>insertNode(TrieNode rootNode,</code> 
      <code>char</code> 
      <code>[]charArray,</code> 
      <code>int</code> 
      <code>index){ </code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>int</code> 
      <code>k=charArray[index]-</code> 
      <code>'a'</code> 
      <code>;</code> 
     </div> 
     <div> 
      <code>if</code> 
      <code>(k&lt;</code> 
      <code>0</code> 
      <code>||k&gt;</code> 
      <code>25</code> 
      <code>){ </code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>throw</code> 
      <code>new</code> 
      <code>RuntimeException(</code> 
      <code>"charArray[index] is not a alphabet!"</code> 
      <code>);</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div> 
      <code>if</code> 
      <code>(rootNode.children[k]==</code> 
      <code>null</code> 
      <code>){ </code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>rootNode.children[k]=</code> 
      <code>new</code> 
      <code>TrieNode();</code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>rootNode.children[k].data=charArray[index];</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>if</code> 
      <code>(index==charArray.length-</code> 
      <code>1</code> 
      <code>){ </code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>rootNode.children[k].freq++;</code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>return</code> 
      <code>;</code> 
     </div> 
     <div> 
      <code>}</code> 
      <code>else</code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>insertNode(rootNode.children[k],charArray,index+</code> 
      <code>1</code> 
      <code>);</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**3、移除节点**

移除操作中，需要对词频进行减一操作。

[?][Link 1]

**4、查找频率**

[?][Link 1]

**5、测试**

测试代码如下:

[?][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> 
    <div>
      16 
    </div> 
    <div>
      17 
    </div> 
    <div>
      18 
    </div> 
    <div>
      19 
    </div> 
    <div>
      20 
    </div> 
    <div>
      21 
    </div> 
    <div>
      22 
    </div> 
    <div>
      23 
    </div> 
    <div>
      24 
    </div> 
    <div>
      25 
    </div> 
    <div>
      26 
    </div> 
    <div>
      27 
    </div> 
    <div>
      28 
    </div> 
    <div>
      29 
    </div> 
    <div>
      30 
    </div> 
    <div>
      31 
    </div> 
    <div>
      32 
    </div> 
    <div>
      33 
    </div> 
    <div>
      34 
    </div> 
    <div>
      35 
    </div> 
    <div>
      36 
    </div> 
    <div>
      37 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>public</code> 
      <code>static</code> 
      <code>void</code> 
      <code>test(){ </code> 
     </div> 
     <div> 
      <code>TrieTree trieTree=</code> 
      <code>new</code> 
      <code>TrieTree();</code> 
     </div> 
     <div> 
      <code>String sourceStr=</code> 
      <code>"Democratic presumptive nominee Hillary Clintons campaign posed pounced on Trumps assertion that British term monetary turmoil might benefit his business venture in Scotland"</code> 
      <code>;</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>//String sourceStr="the that";</code> 
     </div> 
     <div> 
      <code>sourceStr=sourceStr.toLowerCase();</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>String[]strArray=sourceStr.split(</code> 
      <code>" "</code> 
      <code>);</code> 
     </div> 
     <div> 
      <code>for</code> 
      <code>(String str:strArray){ </code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>trieTree.insert(str);</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>String sourceStr2=</code> 
      <code>"Every president is tested by world events But Donald Trump thinks about how is his golf resort can profit from that"</code> 
      <code>;</code> 
     </div> 
     <div> 
      <code>sourceStr2=sourceStr2.toLowerCase();</code> 
     </div> 
     <div> 
      <code>String[]strArray2=sourceStr2.split(</code> 
      <code>" "</code> 
      <code>);</code> 
     </div> 
     <div> 
      <code>for</code> 
      <code>(String str:strArray2){ </code> 
     </div> 
     <div> 
      <code>&nbsp;</code> 
      <code>trieTree.insert(str);</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>BinaryTree.print(</code> 
      <code>"frequence of 'that':"</code> 
      <code>+trieTree.getFreq(</code> 
      <code>"that"</code> 
      <code>));</code> 
     </div> 
     <div> 
      <code>BinaryTree.print(</code> 
      <code>"\nfrequence of 'donald':"</code> 
      <code>+trieTree.getFreq(</code> 
      <code>"donald"</code> 
      <code>));</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>trieTree.remove(</code> 
      <code>"that"</code> 
      <code>);</code> 
     </div> 
     <div> 
      <code>BinaryTree.print(</code> 
      <code>"\nafter remove 'that' once,freq of 'that':"</code> 
      <code>+trieTree.getFreq(</code> 
      <code>"that"</code> 
      <code>));</code> 
     </div> 
     <div> 
      <code>trieTree.remove(</code> 
      <code>"that"</code> 
      <code>);</code> 
     </div> 
     <div> 
      <code>BinaryTree.print(</code> 
      <code>"\nafter remove 'that' twice,freq of 'that':"</code> 
      <code>+trieTree.getFreq(</code> 
      <code>"that"</code> 
      <code>));</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>trieTree.remove(</code> 
      <code>"donald"</code> 
      <code>);</code> 
     </div> 
     <div> 
      <code>BinaryTree.print(</code> 
      <code>"\nafter remove 'donald' once,freq of 'donald':"</code> 
      <code>+trieTree.getFreq(</code> 
      <code>"donald"</code> 
      <code>));</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>BinaryTree.reallyStartPrint();</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

测试结果如下:

[![201724100604095.png_20171410612][]][201724100604095.png_20171410612]

**总结**

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流。

[201724100400516.png_20171410437]: http://files.jb51.net/file_images/article/201702/201724100400516.png?20171410437
[Link 1]: http://www.jb51.net/article/104543.htm#
[201724100604095.png_20171410612]: http://files.jb51.net/file_images/article/201702/201724100604095.png?20171410612