【一】 字典树

前言

一个超过1GB的文件，每一行都是一个单词，且每行长度不超过16，请找出出现次数排名前100的单词，内存使用不能超过2MB。这是我遇到过的一道题目，以此为引子。

定义

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

trie中的键通常是字符串，但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trie中的键是一串位元，可以用于表示整数或者内存地址。

基础性质

1.根节点不包含字符，任意子节点包含一个字符。
2.从根节点出发到任意一个叶子节点的路径上字符连接就是一个字符串。
3.每个节点的子节点包含的字符都是唯一的。

示图

image.png

trie.h

#ifndef TRIE_H
#define TRIE_H
#define MAX 26
typedef struct trie_s trie_t ;
struct trie_s{
    int is_terminal;
    int count;
    trie_t *node[MAX];
};
trie_t *trie_node_init();
int trie_insert(trie_t *root ,char *word);
int trie_delete(trie_t *root,char *word);
int trie_search(trie_t *root,char *word);
void trie_dump(trie_t *root,char *prefix);
void trie_destory(trie_t *root);
#endif /* TRIE_H */

trie.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
/**
 * 
 * @return 
 */
trie_t *trie_node_init(){
    trie_t *root;
    root = (trie_t *) malloc(sizeof(trie_t));
    root->count = 0;
    root->is_terminal = 0;
    int i;
    for(i=0;i<MAX;i++){
        root->node[i] = NULL;
    }
    return root;
}
/**
 * 
 * @param root
 * @param word
 * @return 
 */
int trie_insert(trie_t *root ,char *word){
    int i,val;
    int len = strlen(word);
    trie_t *node = root;
    for(i=0;i<len;i++){
        val = (int) (word[i] - 'a');
        //节点不存在
        if(node->node[val] == NULL){
            node->node[val] = trie_node_init();
        }
        node = node->node[val];
    }
    node->count = node->count + 1;
    node->is_terminal = 1;
    return 1;
}
/**
 * 
 * @param root
 * @param word
 * @return 
 */
int trie_delete(trie_t *root,char *word){
    int i,val;
    int len = strlen(word);
    trie_t *node = root;
    for(i=0;i<len;i++){
        val = (int) (word[i] - 'a');
        //节点不存在
        if(node->node[val] == NULL){
            return -1;
        }
        node = node->node[val];
    }
    node->count=0;
    node->is_terminal = 0;
    return 1;
}
/**
 * 
 * @param root
 * @param word
 * @return 
 */
int trie_search(trie_t *root,char *word){
    int i,val;
    int len = strlen(word);
    trie_t *node = root;
    int count = 0;
    for(i=0;i<len;i++){
        val = (int) (word[i] - 'a');
        //节点不存在
        if(node->node[val] == NULL){
            return count;
        }
        node = node->node[val];
    }
    count = node->count;
    return count;
}
/**
 * 
 * @param root
 * @param prefix
 */
void trie_dump(trie_t *root,char *prefix){
    if(!root){
        return;
    }
    int i,j,len;
    len = strlen(prefix);
    char new_prefix[len+1]; 
    char * new_prefix_pt;
    for(i=0;i<MAX;i++){
        if(root->node[i]){
            if(root->node[i]->is_terminal){
                printf("word:%s%c appear:%d times\n",prefix ,(char)('a' + i),root->node[i]->count);
            }
            new_prefix_pt = (char *) malloc(len + 1);
            sprintf(new_prefix_pt, "%s%c", prefix, ('a' + i));
            trie_dump(root->node[i] ,new_prefix_pt);
        }        
    }
}
/**
 * 
 * @param root
 */
void trie_destory(trie_t *root){
    if(!root){
        return ;
    }
    int i;
    for(i=0;i<MAX;i++){
        if(root->node[i]){
            trie_destory(root->node[i]);
        }
    }
    free(root);
}

trie_test.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.c"

/*
 * 
 */
void main(){
    trie_t *root = trie_node_init();
    FILE *fp = fopen("./words.txt","r");
    char one_line[1024];
    char *word;
    int len=0,i=0;
    word = (char *)malloc(17);
    while (!feof(fp)) 
    {    
        fgets(one_line,1024,fp);
        len = strlen(one_line);
        if(len<=2){
            continue;
        }
        for(i=0;i<len-2;i++){
            *(word+i) = one_line[i];
        }
        *(word+i) = '\0';
        trie_insert(root ,word);
    }
    fclose(fp);
    char *the_word ="ttcoakblwwh";
    int count = trie_search(root,the_word);
    printf("%s:%d\n",the_word ,count);
    trie_delete(root ,the_word);
    count = trie_search(root,the_word);
    printf("%s:%d\n",the_word ,count);
    trie_destory(root);
}