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(); }
随机推荐
-
深入学习jQuery自定义插件
原文地址:jQuery自定义插件学习 1.定义插件的方法 对象级别的插件扩展,即为jQuery类的实例增加方法, 调用:$(选择器).函数名(参数); $(‘#id’).myPlugin(o ...
-
Js对map的操作
var map = {}; // 赋值 var key = "key1"; var value = "value1"; map[key] = value; // ...
-
Memcached存储命令 - set
Memcached set 命令用于将 value(数据值) 存储在指定的 key(键) 中. 如果set的key已经存在,该命令可以更新该key所对应的原来的数据,也就是实现更新的作用. set 命 ...
-
Android四大组件一----Activity
最新面试需要复习一下Android基础. {所谓Activity} 通俗点:app上看到的窗口基本都是Activity Android 程序一般是由多个Activity组成,用户看到的能够交互的窗口通 ...
-
关于photoshop钢笔工具中各点对应到“贝塞尔曲线”中的含义（cocos2d-x与iOS）
1.程序中贝塞尔曲线的简单介绍,只介绍曲线部分.程序中的贝塞尔曲线需要四个点:起始点(startPoint) ,控制点1(controlPoint1),控制点2(controlPoint2),结束点( ...
-
HW4.4
public class Solution { public static void main(String[] args) { final double KILOMETERS_PER_MILE = ...
-
Java I/O重定向
1.输入重定向 命令行:java [java类文件] < [输入文件路径名] 代码:InputStream inputStream = new FileInputStream( ...
-
Android 内部启动其他应用，以及打开指定qq聊天界面
在自己应用中打开第三方应用,有好多种方法,这里举例一种: //以打开微信为例,前提需要知道打开应用的包名,一般一个发布版本的应用,包名不会轻易改变的,但是,打开QQ就要注意了,毕竟QQ的发布版本有不下 ...
-
Scrapy基础(三) ------xpath基础
xpath简介 1,使用路径表达式在xml和html中解析 2,包含标准函数路(所有库支持的xpath语法一致) 3,W3C标准 节点: <body> 第一个节点: <h ...
-
如何为TreeView定义三层模板并实现数据绑定
一直以来都想对TreeView定义多层模板,并实现数据绑定做一个总结,今天在这里做一个概述,我们常用的两层的TreeView绑定的话,我们首先修改TreeView的模板,这里我们使用的是级联的数据模板 ...