1.综述
又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。
它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
Trie树结构的优点在于:
1) 不限制子节点的数量;
2) 自定义的输入序列化,突破了具体语言、应用的限制,成为一个通用的框架;
3) 可以进行最大Tokens序列长度的限制;
4) 根据已定阈值输出重复的字符串;
5) 提供单个字符串频度查找功能;
6) 速度快,在两分钟内完成1998年1月份人民日报(19056行)的重复字符串抽取工作。
2.性质
它有3个基本性质:
1) 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
2) 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3) 每个节点的所有子节点包含的字符都不相同。
3.基本操作
其基本操作有:查找、插入和删除,当然删除操作比较少见.我在这里只是实现了对整个树的删除操作,至于单个word的删除操作也很简单.
4.实现方法
搜索字典项目的方法为:
(1) 从根结点开始一次搜索;
(2) 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;
(3) 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。
其他操作类似处理
5. Trie原理——Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
6.代码实现
复制代码 代码如下:
const int branchNum = 26; //声明常量
int i;
struct Trie_node
{
boolisStr; //记录此处是否构成一个串。
Trie_node*next[branchNum];//指向各个子树的指针,下标0-25代表26字符
Trie_node():isStr(false)
{
memset(next,NULL,sizeof(next));
}
};
class Trie
{
public:
Trie();
voidinsert(const char* word);
boolsearch(char* word);
voiddeleteTrie(Trie_node *root);
// voidprintTrie(Trie_node *root); //new add
private:
Trie_node* root;
};
Trie::Trie()
{
root =new Trie_node();
}
void Trie::insert(const char* word)
{
Trie_node*location = root;
while(*word)
{
if(location->next[*word-'a'] == NULL)//不存在则建立
{
Trie_node *tmp = new Trie_node();
location->next[*word-'a'] = tmp;
}
location = location->next[*word-'a']; //每插入一步,相当于有一个新串经过,指针要向下移动
word++;
}
location->isStr = true; //到达尾部,标记一个串
}
bool Trie::search(char *word)
{
Trie_node*location = root;
while(*word&& location)
{
location= location->next[*word-'a'];
word++;
}
return(location!=NULL && location->isStr);
}
void Trie::deleteTrie(Trie_node *root)
{
for(i =0; i < branchNum; i++)
{
if(root->next[i]!= NULL)
{
deleteTrie(root->next[i]);
}
}
deleteroot;
}
void main() //简单测试
{
Trie t;
t.insert("a");
t.insert("abandon");
char * c= "abandoned";
t.insert(c);
t.insert("abashed");
if(t.search("abashed"))
{
printf("true\n"); //已经插入了
}
}
有时,我们会碰到对字符串的排序,若采用一些经典的排序算法,则时间复杂度一般为O(n*lgn),但若采用Trie树,则时间复杂度仅为O(n)。
Trie树又名字典树,从字面意思即可理解,这种树的结构像英文字典一样,相邻的单词一般前缀相同,之所以时间复杂度低,是因为其采用了以空间换取时间的策略。
下图为一个针对字符串排序的Trie树(我们假设在这里字符串都是小写字母),每个结点有26个分支,每个分支代表一个字母,结点存放的是从root节点到达此结点的路经上的字符组成的字符串。
将每个字符串插入到trie树中,到达特定的结尾节点时,在这个节点上进行标记,如插入"afb",第一个字母为a,沿着a往下,然后第二个字母为f,沿着f往下,第三个为b,沿着b往下,由于字符串最后一个字符为'\0',因而结束,不再往下了,然后在这个节点上标记afb.count++,即其个数增加1.
之后,通过前序遍历此树,即可得到字符串从小到大的顺序。
实现代码如下(g++、VC++都编译通过):
复制代码 代码如下:
#include <iostream>
#include <string.h>
using namespace std;
#define NUM 26
class Node
{
public:
int count; //记录该处字符串个数
Node* char_arr[NUM]; //分支
char* current_str; //记录到达此处的路径上的所有字母组成的字符串
Node();
};
class Trie
{
public:
Node* root;
Trie();
void insert(char* str);
void output(Node* &node, char** str, int& count);
};
//程序未考虑delete动态内存
int main()
{
char** str = new char*[12];
str[0] = "zbdfasd";
str[1] = "zbcfd";
str[2] = "zbcdfdasfasf";
str[3] = "abcdaf";
str[4] = "defdasfa";
str[5] = "fedfasfd";
str[6] = "dfdfsa";
str[7] = "dadfd";
str[8] = "dfdfasf";
str[9] = "abcfdfa";
str[10] = "fbcdfd";
str[11] = "abcdaf";
//建立trie树
Trie* trie = new Trie();
for(int i = 0; i < 12; i++)
trie->insert(str[i]);
int count = 0;
trie->output(trie->root, str, count);
for(int i = 0; i < 12; i++)
cout<<str[i]<<endl;
return 0;
}
Node::Node()
{
count = 0;
for(int i = 0; i < NUM; i++)
char_arr[i] = NULL;
current_str = new char[100];
current_str[0] = '\0';
}
Trie::Trie()
{
root = new Node();
}
void Trie::insert(char* str)
{
int i = 0;
Node* parent = root;
//将str[i]插入到trie树中
while(str[i] != '\0')
{
//如果包含str[i]的分支存在,则新建此分支
if(parent->char_arr[str[i] - 'a'] == NULL)
{
parent->char_arr[str[i] - 'a'] = new Node();
//将父节点中的字符串添加到当前节点的字符串中
strcat(parent->char_arr[str[i] - 'a']->current_str, parent->current_str);
char str_tmp[2];
str_tmp[0] = str[i];
str_tmp[1] = '\0';
//将str[i]添加到当前节点的字符串中
strcat(parent->char_arr[str[i] - 'a']->current_str, str_tmp);
parent = parent->char_arr[str[i] - 'a'];
}
else
{
parent = parent->char_arr[str[i] - 'a'];
}
i++;
}
parent->count++;
}
//采用前序遍历
void Trie::output(Node* &node, char** str, int& count)
{
if(node != NULL)
{
if(node->count != 0)
{
for(int i = 0; i < node->count; i++)
str[count++] = node->current_str;
}
for(int i = 0; i < NUM; i++)
{
output(node->char_arr[i], str, count);
}
}
}
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
《魔兽世界》大逃杀!60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容,新游玩模式《强袭风暴》即将于3月21 日在亚服上线,届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕,并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时,他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中,玩家将会进入一个全新的海盗主题大逃杀式限时活动,其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场,作为一个独立于主游戏之外的活动,玩家可以用大逃杀的风格来体验《魔兽世界》,不分职业、不分装备(除了你在赛局中捡到的),光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式,玩家在加入海盗主题的预赛大厅区域前,可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹,《巨龙崛起》和《魔兽世界:巫妖王之怒 经典版》的玩家都可以获得奖励。
更新日志
- 人听人爱,入耳即溶《天碟落地3《HIFI瑰宝》示范颠峰之作》[WAV+CUE/分轨][839.9MB]
- 莫扎特安魂曲舍尔琴,维也纳国家歌剧院,1958【FLAC】
- 罗西尼五部歌剧序曲班贝格佩雷亚1958年【FLAC】
- 【HIRES】李云迪-莫扎特:钢琴奏鸣曲计划-萨尔兹堡-2024-24-96FLAC分轨
- 珍娜JheenaLodwick-GettingToKnowYou(XRCD)[WAV+CUE]
- 珍纳JheenaLodwick-AllMyLoving全我所爱(XRCD)[WAV+CUE]
- JheenaLodwick-Feeling挚爱(XRCD)[WAV+CUE]
- 人听人爱,入耳即溶《天碟落地2《测机王HQ》日本母带发烧音质》[WAV+CUE/分轨][709.9MB]
- 人听人爱,入耳即溶《天碟落地1《示范碟皇》殿堂级演绎名作》[WAV+CUE/分轨][786.9MB]
- MICO刘为《观·自在行》CD[FLAC/分轨][1.3GB]
- 珍纳JheenaLodwick-SingingInTheRain(XRCD)[WAV+CUE]
- 珍纳JheenaLodwick-Feelings非常感觉2-HDCD[WAV+CUE]
- 珍纳精选JheenaLodwick-JheenaLodwickGreatest[香港版]2015[WAV+CUE]
- 谁杀死了HI-FI音乐-《涂鸦精选VOL.2》[WAV+CUE]
- Mav-Mav《美芙的祈祷》(2000)[WAV+CUE]