三叉树性质特点对于一般的Trie树的数据结构，它的实现简单但是空间效率极低 。例如，如果要支持26个英文字母，每个节点就要保存26个指针，当数据量继续增大，需要更多的支持记忆体用量，使得整个数据结构占用记忆体太多 。由于节点数组中保存挂起的空指针占用了过多记忆体，我们採用特殊的Trie树的数据结构——Ternary Search Trie，三叉搜寻树，它是结合字典树的高时间效率和二叉搜寻树的高空间效率的一种数据结构 。三叉搜寻树与二叉搜寻树不同，键不是直接保存在节点中，而是由节点在树中的位置决定 。一个节点的所有子孙都有相同的前缀（prefix），也就是这个节点对应的字元串，而根节点对应空字元串 。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值 。与此同时，三叉搜寻树使用了一种聪明的手段去解决字典树的记忆体问题（空的指针数组） 。为了避免多余的指针占用记忆体，每个节点不再用数组来表示，而是表示成“树中有树” 。节点里每个非空指针都会在三叉搜寻树里得到属于它自己的节点 。插入字元串的顺序会影响三叉搜寻树的结构，为了取得最佳性能，字元串应该以随机的顺序插入到三叉树搜寻树中，尤其不应该按字母顺序插入，否则对应于单个Trie节点的子树会退化成鍊表，极大地增加查找成本 。单词的读入顺序对于创建平衡的三叉搜寻树很重要，但对于二叉搜寻树就不太重要 。通过选择一个排序后数据单元集合的中间值，并把它作为开始节点 。
文章插图
三叉搜寻树的基本性质可以归纳为：（1）根节点不包含字元，除根节点外的每个节点只包含一个字元 。（2）从根节点到某一个节点，路径上经过的字元连线起来，为该节点对应的字元串 。（3）每个节点的所有子节点包含的字元串不相同 。（4）节点採用“树中有树”的建立方法，避免多余的记忆体占用 。三叉搜寻树的实现对于三叉搜寻树的实现代码採用C++和Java语言C++//向词典树中加入一个单词的过程privateTSTNodeaddWord(Stringkey){TSTNodecurrentNode=root;//从树的根节点开始查找intcharIndex=0;//从词的开头匹配while(true){//比较词的当前字元与节点的当前字元//向词典树中加入一个单词的过程privateTSTNodeaddWord(Stringkey){TSTNodecurrentNode=root;//从树的根节点开始查找intcharIndex=0;//从词的开头匹配while(true){//比较词的当前字元与节点的当前字元intcharComp=key.charAt(charIndex)-currentNode.splitchar;if(charComp==0){//相等charIndex++;if(charIndex==key.length()){returncurrentNode;}if(currentNode.eqNode==null){currentNode.eqNode=newTSTNode(key.charAt(charIndex));}currentNodecurrentNode=currentNode.eqNode;}elseif(charComp<0){//小于if(currentNode.loNode==null){currentNode.loNode=newTSTNode(key.charAt(charIndex));}currentNodecurrentNode=currentNode.loNode;}else{//大于if(currentNode.hiNode==null){currentNode.hiNode=newTSTNode(key.charAt(charIndex));}currentNodecurrentNode=currentNode.hiNode;}}}intcharComp=key.charAt(charIndex)-currentNode.splitchar;if(charComp==0){//相等charIndex++;if(charIndex==key.length()){returncurrentNode;}if(currentNode.eqNode==null){currentNode.eqNode=newTSTNode(key.charAt(charIndex));}currentNodecurrentNode=currentNode.eqNode;}elseif(charComp<0){//小于if(currentNode.loNode==null){currentNode.loNode=newTSTNode(key.charAt(charIndex));}currentNodecurrentNode=currentNode.loNode;}else{//大于if(currentNode.hiNode==null){currentNode.hiNode=newTSTNode(key.charAt(charIndex));}currentNodecurrentNode=currentNode.hiNode; }}}Javapackage sunfa.tree;import java.util.HashMap;import java.util.Iterator;import java.util.Map;public class TernarySearchTrie {public static void main(String[] args) {Map<String, String> map = new HashMap<String, String>();int size = 20;TernarySearchTrie tree = new TernarySearchTrie();for (int i = 0; i < size; i++) {map.put("tkey" + i, "value" + i);tree.addWord("tkey" + i);}System.out.println("search:");Iterator<String> it = map.keySet().iterator();while (it.hasNext()) {String key = it.next().toString();Entry node = tree.search(key);System.out.println(node.data.get("value") + ",查找次数："+ node.data.get("count"));}}private Entry root = new Entry();public Entry addWord(String key) {if (key == null || key.trim().length() == 0)return null;Entry node = root;int i = 0;while (true) {int diff = key.charAt(i) - node.splitchar;char c = key.charAt(i);if (diff == 0) {// 当前单词和上一次的相比较，如果相同i++;if (i == key.length()) {node.data = http://www.mancos-co.com/new HashMap