【三叉树】英语怎么说_在线翻译

三叉树

对于一般的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; } } } Java package sunfa.tree; import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class TernarySearchTrie { public static void main(String args) { Map map = new HashMap(); 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 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 = new HashMap(); node.data.put("value", key); return node; } if (node.equals == null) node.equals = new Entry(key.charAt(i));// 这里要注意，要获取新的单词填充进去，因为i++了 node = node.equals; } else if (diff < 0) {// 没有找到对应的字符，并且下一个左或右节点为NULL，则会一直创建新的节点 if (node.left == null) node.left = new Entry(c); node = node.left; } else { if (node.right == null) node.right = new Entry(c); node = node.right; } } } public Entry search(String key) { if (key == null || key.trim().length() == 0) return null; Entry node = root; int count = 0, i = 0; while (true) { if (node == null) return null; int diff = key.charAt(i) - node.splitchar; count++; if (diff == 0) { i++; if (i == key.length()) { node.data.put("count", count); return node; } node = node.equals; } else if (diff < 0) { node = node.left; } else { node = node.right; } } } /** * 三叉Trie树存在3个节点，左右子节点和二叉树类似，以前key都是存放在二叉树的当前节点中，在三叉树中单词是存放在中间子树的。 */ static class Entry { Entry left; Entry right; Entry equals;// 比对成功就放到中间节点 char splitchar;// 单词 Map data;// 扩展数据域，存放检索次数，关键码频率等信息。 public Entry(char splitchar) { this.splitchar = splitchar; } public Entry() { } } } 三叉搜索树由于其优良的搜索性能，常被使用于搜索引擎的自动填充完成（Auto-complete）功能，让用户可以通过“联想”的方式更容易查找到所需要的相关模糊信息百度根据我们输入的“数据”关键字，提示了搜索量较大的数据库学习，数据分析等搜索信息，自动完成这种联想功能的核心思想即为三叉搜索树思想。对于Web应用程序来说，自动完成（Auto-complete）的繁重处理工作绝大部分要交给服务器去完成。很多时候，自动完成（Auto-complete）的备选项数目巨大，不适宜一下子全都下载到客户端。相反，三叉树搜索是保存在服务器上的，客户端把用户已经输入的单词前缀送到服务器上作查询，然后服务器根据三叉搜索树算法获取相应数据列表，最后把候选的数据列表返回给客户端。

目录

三叉树

网络释义 专业释义

相关文章

双语例句

百科

修改单词