用C语言实现字典树
前言
前段时间，面试百度人工智能部门的测试开发岗的时候，面试官给了我一道算法题：有一堆数据，都是由英文字母构成的，设计一个算法去存储这些数据。我一想，那不就是考字典树嘛，简单啦，我参加ACM校赛的时候看过大神队友实现过。大概的思想都能理解，但是由于自己没有亲自实现过，所以当面试官问我具体要怎么实现的时候，我就特别着急，明明思路很清晰，但是细节却连接不起来，于是就打算面试后自己实现一遍！
简介
在谈实现之前，我想先谈谈字典树整体的思想和存在的价值。
字典树，顾名思义，就是用树的结构去存储单词。比如，我要存储单词ant和apple，就可以采取下图的多叉树结构去实现，其中可以看到，他们公用A节点，看是上去似乎节省了空间（实际上并没有，下面会解释），和形成了<strong>有序</strong>的分组。
字典树图解
假如不使用这种结构存储，那么采取朴素的方法，也就是用一个数组，把单词存进去，然后还需要满足数组内的单词不重复，我们可以比较一下这两种方法的时间复杂度。
<strong>假设每个单词平均有M个字母，共有N个单词</strong>
| 操作 | 朴素算法 | 字典树 |
|---|---|---|
| 插入 | O(N) | O(M) |
| 查找 | O(N) | O(M) |
| 删除 | O(N) | O(M) |
显然当需要存储的数据量越庞大或者数据的操作越频繁，字典树的优势越明显，它的时间复杂度只与单词的长度有关！这个算法可以应用在词频分析，信息检索，字符串匹配等方面。
实现
1. 定义结构体
typedef struct node {
struct node* children[SUB_NODE_COUNT];
int flag;
char character;
} Node;
定义树节点的数据包含三部分
- 所含字母
- 子节点指针
- 是否能终结
从这个定义的结构体可以看出，其实字典树并没有节省存储空间。<code>sizeof(Node)</code>的结果是216bytes，当然因为data packing对齐的关系，有一些多余padding，但是就算设置<code>#pragma pack (1)</code>， 消除padding，那<code>sizeof(Node)</code>也有213bytes，相比之下，一个char只需要1byte，所以并没有节省空间。
<code>int flag</code>这个变量是为了区分该节点与其祖先节点能否成为一个单词。比如ant和an分别都能成为独立的单词，所以n和t节点的<code>flag</code>都应该设置<code>TRUE</code>，但是orange和ora就不一样，因为ora不能成为一个单词，所以这里的a节点的<code>flag</code>应该设置<code>FALSE</code>
2. 插入函数
Node* create_node(char c, int flag) {
Node* n = malloc(sizeof(Node));
n->character = c;
n->flag = flag;
for (int i = 0; i < SUB_NODE_COUNT; i++) {
n->children[i] = NULL;
}
return n;
}
int append_node(Node* n, char c) {
Node* child_ptr = n->children[c-'a'];
if (child_ptr) {
return FALSE;
}
else {
n->children[c-'a'] = create_node(c, FALSE);
return TRUE;
}
}
int add_word(Node* root, char* str) {
char c = *str;
Node* ptr = root;
int flag = TRUE;
while(c != '\0') {
if (!append_node(ptr, c)) {
flag = FALSE;
}
ptr = ptr->children[c-'a'];
c = *(++str);
}
if (!ptr->flag) {
flag = FALSE;
ptr->flag = TRUE;
}
return !flag;
}
这个函数的功能，将单词插入树中，假如目标单词已经存在于树中，则返回<code>FALSE</code> , 否则就能成功插入，返回<code>TRUE</code>。插入的过程比较简单，只要单词字母对应的节点存在，则继续往下查询，否则就创建新节点，然后在最后的一个字母的节点把<code>flag</code>改为<code>FALSE</code>;
3. 查找函数
int check(Node* root, char* word) {
Node* ptr = root;
int len = strlen(word);
for (int i = 0; i < len; i++) {
if (!ptr) {
printf("\"%s\" isn't in the Dictionary!\n", word);
return FALSE;
}
ptr = ptr->children[word[i]-'a'];
}
if (ptr && ptr->flag) {
printf("\"%s\" is in the Dictionary!\n", word);
return TRUE;
} else {
printf("\"%s\" isn't in the Dictionary!\n", word);
return FALSE;
}
}
这个函数也比较简单，就不多解释了。
4. 遍历函数
void traversal(Node* root, char* str) {
if (!root) {
return;
}
int len_of_str = strlen(str);
char* new_str = malloc(len_of_str+1);
strcpy(new_str, str);
new_str[len_of_str] = root->character;
if (root->flag) {
//输出
char* str_for_print = malloc(len_of_str+2);
strcpy(str_for_print, new_str);
str_for_print[len_of_str+1] = '\0';
printf("%s\n", str_for_print);
free(str_for_print);
}
for (int i = 0; i < SUB_NODE_COUNT; i++) {
traversal(root->children[i], new_str);
}
free(new_str);
}
很显然，这里用深度优先遍历比较合适，因为这是根据单词字母的组成来垂直扩展多叉树的。对于深度优先算法，递归是最能偷懒的方法啦！深度遍历的过程中，只要遇到<code>flag</code>等于<code>TRUE</code>，跟祖先节点构成单词输出，那就OK啦。
5. 删除函数
int isLeave(Node* root) {
for (int i = 0; i < SUB_NODE_COUNT; i++) {
if (root->children[i]) {
return FALSE;
}
}
return TRUE;
}
int delete_word(Node* root, char* word) {
int len = strlen(word);
int first_index = word[0] - 'a';
if (!root->children[first_index]) {
return FALSE;
}
if (len == 1) {
if (root->children[first_index]->flag) {
if (isLeave(root->children[first_index])) {
free(root->children[first_index]);
root->children[first_index] = NULL;
} else {
root->children[first_index]->flag = FALSE;
}
return TRUE;
} else {
return FALSE;
}
}
int flag = delete_word(root->children[first_index], word+1);
if (isLeave(root->children[first_index]) && !root->children[first_index]->flag) {
free(root->children[first_index]);
root->children[first_index] = NULL;
}
return flag;
}
删除函数相对难一点。我看网上很多人实现字典树的时候都没有实现这个函数。
其实删除一个单词最直接的方法就是把最后一个字母的<code>flag</code>改为<code>FALSE</code>就可以了。但是只是这样做的话，随着越来越频繁的操作，会产生很多多余的节点，性能不能达到最佳，所以这个函数需要完成两件事。
- 判断删除的单词是否存在，假如不存在则返回<code>FALSE</code>。
- 删除多余的节点。
节点必须同时满足以下两点才能定义为多余的节点。
- 没有子节点（叶子节点）
- <code>flag</code>等于<code>FALSE</code>
6. 完整的实现
我只是简单地写了几个用例来测试，如若发现bug，欢迎来喷！
/*
============================================================================
Name : Dictionary.c
Author : Matthew1994
Version :
Copyright : Your copyright notice
Description : Dictionary Tree in C, Ansi-style
============================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define SUB_NODE_COUNT 26
typedef struct node {
struct node* children[SUB_NODE_COUNT];
int flag;
char character;
} Node;
Node* create_node(char c, int flag) {
Node* n = malloc(sizeof(Node));
n->character = c;
n->flag = flag;
for (int i = 0; i < SUB_NODE_COUNT; i++) {
n->children[i] = NULL;
}
return n;
}
int append_node(Node* n, char c) {
Node* child_ptr = n->children[c-'a'];
if (child_ptr) {
return FALSE;
}
else {
n->children[c-'a'] = create_node(c, FALSE);
return TRUE;
}
}
int add_word(Node* root, char* str) {
char c = *str;
Node* ptr = root;
int flag = TRUE;
while(c != '\0') {
if (!append_node(ptr, c)) {
flag = FALSE;
}
ptr = ptr->children[c-'a'];
c = *(++str);
}
if (!ptr->flag) {
flag = FALSE;
ptr->flag = TRUE;
}
return !flag;
}
void traversal(Node* root, char* str) {
if (!root) {
return;
}
int len_of_str = strlen(str);
char* new_str = malloc(len_of_str+1);
strcpy(new_str, str);
new_str[len_of_str] = root->character;
if (root->flag) {
//输出
char* str_for_print = malloc(len_of_str+2);
strcpy(str_for_print, new_str);
str_for_print[len_of_str+1] = '\0';
printf("%s\n", str_for_print);
free(str_for_print);
}
for (int i = 0; i < SUB_NODE_COUNT; i++) {
traversal(root->children[i], new_str);
}
free(new_str);
}
int check(Node* root, char* word) {
Node* ptr = root;
int len = strlen(word);
for (int i = 0; i < len; i++) {
if (!ptr) {
printf("\"%s\" isn't in the Dictionary!\n", word);
return FALSE;
}
ptr = ptr->children[word[i]-'a'];
}
if (ptr && ptr->flag) {
printf("\"%s\" is in the Dictionary!\n", word);
return TRUE;
} else {
printf("\"%s\" isn't in the Dictionary!\n", word);
return FALSE;
}
}
int isLeave(Node* root) {
for (int i = 0; i < SUB_NODE_COUNT; i++) {
if (root->children[i]) {
return FALSE;
}
}
return TRUE;
}
int delete_word(Node* root, char* word) {
int len = strlen(word);
int first_index = word[0] - 'a';
if (!root->children[first_index]) {
return FALSE;
}
if (len == 1) {
if (root->children[first_index]->flag) {
if (isLeave(root->children[first_index])) {
free(root->children[first_index]);
root->children[first_index] = NULL;
} else {
root->children[first_index]->flag = FALSE;
}
return TRUE;
} else {
return FALSE;
}
}
int flag = delete_word(root->children[first_index], word+1);
if (isLeave(root->children[first_index]) && !root->children[first_index]->flag) {
free(root->children[first_index]);
root->children[first_index] = NULL;
}
return flag;
}
int main(void) {
Node *root = create_node('$', FALSE);
//测试add_ word函数
add_word(root, "abc");
add_word(root, "abcd");
add_word(root, "world");
add_word(root, "nnaiodnf");
traversal(root, "");
//测试check函数
check(root, "abc");
check(root, "abcd");
//测试delete_word函数
delete_word(root, "abe");
check(root, "abe");
return EXIT_SUCCESS;
}
