读书笔记摘抄新闻资讯三叉树
性质特点
对于一般的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;
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;
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<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 = new HashMap<Object, Object>();
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<Object, Object> data;// 扩展数据域，存放 检索次数，关键码频率等信息。
public Entry(char splitchar) {
this.splitchar = splitchar;
}
public Entry() {
}
}
}
三叉搜寻树的套用
三叉搜寻树由于其优良的搜寻性能，常被使用于搜寻引擎的自动填充完成（Auto-complete）功能，让用户可以通过“联想”的方式更容易查找到所需要的相关模糊信息
百度根据我们输入的“数据”关键字，提示了搜寻量较大的资料库学习，数据分析等搜寻信息，自动完成这种联想功能的核心思想即为三叉搜寻树思想。
对于Web应用程式来说，自动完成（Auto-complete）的繁重处理工作绝大部分要交给伺服器去完成。很多时候，自动完成（Auto-complete）的备选项数目巨大，不适宜一下子全都下载到客户端。相反，三叉树搜寻是保存在伺服器上的，客户端把用户已经输入的单词前缀送到伺服器上作查询，然后伺服器根据三叉搜寻树算法获取相应数据列表，最后把候选的数据列表返回给客户端。