trie，又称前缀树或字典樹，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
一个保存了 8 个键的 trie 结构，"A", "to", "tea", "ted", "ten", "i", "in", and "inn".
In the example shown, keys are listed in the nodes and values below them. Each complete English word has an arbitrary integer value associated with it. A trie can be seen as adeterministic finite automaton, although the symbol on each edge is often implicit in the order of the branches.
It is not necessary for keys to be explicitly stored in nodes. (In the figure, words are shown only to illustrate how the trie works.)
Though tries are most commonly keyed by character strings, they don't need to be. The same algorithms can easily be adapted to serve similar functions of ordered lists of any construct, e.g., permutations on a list of digits or shapes. In particular, a bitwise trie is keyed on the individual bits making up a short, fixed size of bits such as an integer number or memory address.
A trie can also be used to replace a hash table, over which it has the following advantages:
- Looking up data in a trie is faster in the worst case, O(m) time (where m is the length of a search string), compared to an imperfect hash table. An imperfect hash table can have key collisions. A key collision is the hash function mapping of different keys to the same position in a hash table. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.
- There are no collisions of different keys in a trie.
- Buckets in a trie, which are analogous to hash table buckets that store key collisions, are necessary only if a single key is associated with more than one value.
- There is no need to provide a hash function or to change hash functions as more keys are added to a trie.
- A trie can provide an alphabetical ordering of the entries by key.
Tries do have some drawbacks as well:
- Tries can be slower in some cases than hash tables for looking up data, especially if the data is directly accessed on a hard disk drive or some other secondary storage device where the random-access time is high compared to main memory.[5]
- Some keys, such as floating point numbers, can lead to long chains and prefixes that are not particularly meaningful. Nevertheless a bitwise trie can handle standard IEEE single and double format floating point numbers.
- Some tries can require more space than a hash table, as memory may be allocated for each character in the search string, rather than a single chunk of memory for the whole entry, as in most hash tables.
Implementation：
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h> typedef struct trie trie;
struct trie
{
char key;
trie *next,*children;
}; trie *newnode(char s)
{
trie *t=(trie *)malloc(sizeof(trie));
t->key=s;
t->next=t->children=NULL;
} void insert(trie **t,char *s,int start)
{if(s[start]=='\0')
{
*t=newnode('#');
return;
}
if(*t==NULL)
{
*t=newnode(s[start]);
insert(&(*t)->children,s,start+);
}
if((*t)->key==s[start])
insert(&(*t)->children,s,start+);
else
insert(&(*t)->next,s,start);
} bool search(trie *t ,char *s,int start)
{ if(t==NULL)
return false; if(t->key=='#' && s[start]=='\0')
return true; if(t->key!='#' && s[start]=='\0' || t->key=='#' && s[start]!='\0')
return false; if(t->key==s[start])
return search(t->children,s,start+); else
return search(t->next,s,start); return false;
} /*void push(trie **t ,char *str)
{ int i=0;
for(i=0;i<strlen(str);i++)
insert(t,str[i]);
}*/ main()
{ int i=; trie *t=NULL;
char ch='y';
while(ch=='y')
{
{char str[];
fflush(stdin);
printf("Enter the word ");
gets(str); insert(&t,str,);
}
// push(&t,str);
fflush(stdin);
printf("more y/n ::");
ch=getchar();
} ch='y';
while(ch=='y')
{char str[];
fflush(stdin);
printf("Enter the string you want to search::");
gets(str); fflush(stdin);
if(search(t,str,))
printf("Found");
else
printf("Not Found"); printf("\n more y/n ::");
scanf("%c",&ch); } getch(); }
随机推荐
-
DOM中文本节点索引方法
问题 对于 jquery 接口text()只能取到有标签的 dom对象中 文本内容. 如果索引对象本身就是文本节点,则不好索引到, 没有相关的索引选择器. 例如: 对于<input>aaa ...
-
hibernate基础
另存为查看吧
-
《算法导论》习题解答 Chapter 22.1-2（邻接矩阵与链表）
链表如图: 矩阵: 1 2 3 4 5 6 7 1 0 1 1 0 0 0 0 2 1 0 0 1 1 0 0 3 1 0 0 0 0 1 1 4 0 1 0 0 0 0 0 5 0 1 0 0 0 ...
-
powerdesign设置实体显示格式
工具-显示参数选择中,如下图:
-
Bzoj 2588: Spoj 10628. Count on a tree 主席树,离散化,可持久,倍增LCA
题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2588 2588: Spoj 10628. Count on a tree Time Limit ...
-
201521145048《Java程序设计》第13周学习总结
1. 本周学习总结 以你喜欢的方式(思维导图.OneNote或其他)归纳总结多网络相关内容. 2. 书面作业 Q1. 网络基础 1.1 比较ping www.baidu.com与ping cec.jm ...
-
MySQL 水平拆分与垂直拆分详解
前言:说到优化mysql,总会有这么个回答:水平拆分,垂直拆分,那么我们就来说说什么是水平拆分,垂直拆分. 一.垂直拆分 说明:一个数据库由很多表的构成,每个表对应着不同的业务,垂直切分是指按照业务将 ...
-
Java易错题（1）
检查程序,是否存在问题,如果存在指出问题所在,如果不存在,说明输出结果. public class HelloB extends HelloA { public HelloB() { } { Syst ...
-
D - Pagodas
n pagodas were standing erect in Hong Jue Si between the Niushou Mountain and the Yuntai Mountain, l ...
-
python变量名感悟
我感悟的是python的变量名其实就可以理解为C/C++中的指针! 1.python的变量在使用之前必须赋值,就像指针在使用之前不能为空. 2.python的内存可以用del释放,C++可以用dele ...