Trie字典树

发表于 | 分类于 | 评论数： | 热度： ℃
本文字数： 5.5k | 阅读时长 ≈ 5 分钟

  Trie树，俗称字典树，最早是应用于通讯录中人名的查找而设计的查找树。字典树的查找效率高，通过利用公共前缀来减少查询时间。Trie树的结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int num_chars = 28;//represent 

struct node{
	Record* data;//数据域
	node* branch[num_chars];//一个节点下还有不同字母的分支
	node();//构造方法
};

class Trie{
private:
	node* root;
public:
	...
}

注：Trie树中只有当到达字符串末尾时（Trie树中存在这个字符串），data数据域才会有值。表示当前字符串存入当前Trie树，否则其他节点data指针为空。

Trie树的查找

按照目标字符串，一个字符一个字符的向下查找，直到节点为null或字符串全部遍历完

1
2
3
4
5
6
7
8
9
10
11
12
13
bool search(const key& t){
	int position=0;
	char next_char;
	node *loc = root;
	while(loc!=null&&(next_char=t.key_letter(position))!=''){
		location = location->branch[alphabtic_order(next_char)];//根据字母获取分支
		position++;
	}
	if(position!=null&&position->data!=null)
		return 1;
	else
		return 0;
}

Trie树的插入

向下查询到某个合适的位置，将data指针设置成新键的记录信息。若中途遇空，则必须将节点都插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool insert(const Record& new_data){
	if(root==null)
		root = new node;
	int p=0,next_position;
	char next_char;
	node *loca = root;
	while(loca!=null&&(next_char=new_data.key_letter(p))!=''){
		next_position = alphabetic_order(next_char);
		if(loca->branch[next_position]==null)
			loca->branch[next_position]=new node();
		loca=loca->branch[next_position];
		p++;
	}//至此，已遍历完待插入字符串的所有字符。此时location的位置在最后一个字母的节点
	if(loca->data!=null)
		return;//已经存在
	else
		loca->data=new Record(new_data);
	return 1;
}

Trie树的删除

  沿着路径找到相应data成员设置为null。若这个节点所有成员为null（分支和data）则删除这个节点。思路：利用递归或栈。

----\(˙<>˙)/----赞赏一下吧～