字典树（Trie）与双数组字典树（Double-Array-Trie）
算法
字典树（Trie）与双数组字典树（Double-Array-Trie）
算法

字典树（Trie）与双数组字典树（Double-Array-Trie）

名称：“字典树”，又称“单词查找树”，是一种树形结构，是一种哈希树的变种。

作用：1. 单词查找；2. 字符串排序。

性质：1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符； 2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 3. 每个节点的所有子节点包含的字符都不相同。

红色节点表示字符串存在，白色节点表示字符串不存在

Q：按照字典序写出上面字典树中的所有单词【提示：深度优先遍历】

  1. a
  2. aae
  3. af
  4. c
  5. fz
  6. fzc
  7. fzd

字典树的基本代码实现（指针）：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;

#define BASE 26
// 定义节点
class node {
public:
    node() {
        flag = false;
        for (int i = 0; i < BASE; i++) next[i] = nullptr;
    }
    ~node() {}
    bool flag; // 标识：节点是否独立成词
    node *next[26]; // 定义节点的边
};

// 定义字典树
class Trie
{
private:
    node *root; //根节点
public:
    Trie() {
        root = new node();
    };
    
    // 插入
    bool insert(string word) {
        node *p = root;
        for (auto x : word) {
            int ind = x - 'a';
            if (p->next[ind] == nullptr) p->next[ind] = new node();
            p = p->next[ind];
        }
        if (p->flag) return false;
        p->flag = true;
        return true; // 代表 是否第一次插入
    }

    // 查找
    bool search(string word) {
        node *p = root;
        for (auto x : word) {
            int ind = x - 'a';
            p = p->next[ind];
            if (p == nullptr) return false;
        }
        return p->flag;
    }

    // 排序【dfs遍历】
    void output() {
        __output(root, "");
        return;
    }

    static void __output(node *root, string prefix) {
        if (root == nullptr) return;
        if (root->flag) cout << "find: " << prefix << endl;
        for (int i = 0; i < BASE; i++) {
            __output(root->next[i], prefix + char(i + 'a'));
        }
        return;
    }

    static void clearTrie(node *root) {
       if (root == nullptr) return;
       for (int i = 0; i < BASE; i++) clearTrie(root->next[i]);
       delete root;
       return;
    }

    ~Trie() {
        clearTrie(root);
    }
};

// 测试字典树的插入与查找
int main_test0() {
    Trie t;
    int op;
    string s;

    while (cin >> op >> s)
    {
        switch (op)
        {
        case 1:
            t.insert(s);
            break;
        case 2:
            cout << "search word = " << s << ", result :" << t.search(s) << endl;
        default:
            break;
        }
    }
    
    return 0;
}

// 测试字典树对字符串的排序
int main_test1() {
    int n; //定义容量
    cin >> n;
    string s;
    Trie t;

    for (int i = 0; i < n; i++) {
        cin >> s;
        t.insert(s);
    }

    t.output();
    return 0;
}

字典树的竞赛代码实现（数组）：

// 字典树的竞赛写法
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;

#define BASE 26

class node {
public:
    int flag; // 节点是否独立成词
    int next[BASE]; // 边的信息 每一个节点在数组中的下标
    void clear() {// 初始化当前节点
        flag = 0;
        for (int i = 0; i < BASE; i++) {
            next[i] = 0; // Trie的下标为0 代表没有挂载节点
        }
    }
} trie[10000]; // 用数组的物理结构书写trie的逻辑结构

// cnt 维护：当前能够使用的 下一个未使用节点的编号
// root 维护：根节点的编号
int cnt, root;

// 初始化Trie
void clearTrie() {
    cnt = 2, root = 1; 
    trie[root].clear();
    return;
}

// 创建节点
int getNewNode() {
    trie[cnt].clear();
    return cnt++;
}

// 插入
void insert(string s) {
    int p = root; // p：维护的是trie中节点的下标
    for (auto x : s) {
        int ind = x - 'a';
        if (trie[p].next[ind] == 0) trie[p].next[ind] = getNewNode();
        p = trie[p].next[ind];
    }
    trie[p].flag = 1;
    return;
}

// 查找
bool search(string s) {
    int p = root; // p：维护的是trie中节点的下标
    for (auto x : s) {
        int ind = x - 'a';
        p = trie[p].next[ind];
        if (p == 0) return 0;
    }
    return trie[p].flag;
}

// 测试
int main() {
    cout << "competition version" << endl;
    clearTrie();
    int op;
    string s;

    while (cin >> op >> s)
    {
        switch (op)
        {
        case 1:
            insert(s);
            break;
        case 2:
            cout << "search word = " << s << ", result :" << search(s) << endl;
        default:
            break;
        }
    }
    
    return 0;
}

双数组字典树（Double-Array-Trie）

双数组Trie（Double-ArrayTrie）是trie树的一个简单而有效的实现，由两个整数数组构成，一个是base[]，另一个是check[]。

base[] 的index，用于表示当前节点的下标。

base[] 记录的是基础值，生成基础值的过程中，需要保证基础值不发生冲突：t = base[i] + ‘s’，即base[t]是空的。

备注：s代表节点的每条边（有子节点的边），转换为的int值。

由父节点的下标i，可以推算出，其子节点的下标t。

check[] 的index，用于表示‘当前节点的子节点’的下标。

check[] 记录的是子节点对应的父节点index，可用于判断父节点在这条边上是否有子节点。

将check[t] 赋值为i (其父节点的base值)：check[t] = i 。

可约定，如果check[t]记录的是负值，表示成词。

代码实现：

// 双数组字典树
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;

#define BASE 26
#define MAX_CNT 1000
class node {
public:
    int flag; // 节点是否独立成词
    int next[BASE]; // 边的信息 每一个节点在数组中的下标
    void clear() {// 初始化当前节点
        flag = 0;
        for (int i = 0; i < BASE; i++) {
            next[i] = 0; // Trie的下标为0 代表没有挂载节点
        }
    }
} trie[MAX_CNT]; // 用数组的物理结构书写trie的逻辑结构

// cnt 维护：当前能够使用的 下一个未使用节点的编号
// root 维护：根节点的编号
int cnt, root;

// 初始化Trie
void clearTrie() {
    cnt = 2, root = 1; 
    trie[root].clear();
    return;
}

// 创建节点
int getNewNode() {
    trie[cnt].clear();
    return cnt++;
}

// 插入
void insert(string s) {
    int p = root; // p：维护的是trie中节点的下标
    for (auto x : s) {
        int ind = x - 'a';
        if (trie[p].next[ind] == 0) trie[p].next[ind] = getNewNode();
        p = trie[p].next[ind];
    }
    trie[p].flag = 1;
    return;
}

// 查找
bool search(string s) {
    int p = root; // p：维护的是trie中节点的下标
    for (auto x : s) {
        int ind = x - 'a';
        p = trie[p].next[ind];
        if (p == 0) return 0;
    }
    return trie[p].flag;
}

// base[]: 下标为节点下标，值为节点base值
// check[]: 下标为子节点的下标，值为父节点的index
// da_root: DoubleArrayTrie的root节点下标 下标0代表base[]/check[]的初始值
int *base, *check, da_root = 1;

// 为节点生成base
int getBaseValue(int root, int *base, int *check) {
    int b = 1; // 初始化base
    bool flag = false; // 标识 是否找到了可用的base: check[b + i] == 0
    while (!flag) {
        b += 1; // base循环累加 尝试
        flag = true;
        for (int i = 0; i < BASE; i++) {
            if (trie[root].next[i] == 0) continue; // 没有节点则跳过
            // 有节点
            if (check[b + i] == 0) continue; // 子节点对应的check[] index未被占用
            flag = false;
            break;
        }
    }
    return b;
}

/**
 * @param root: Trie根节点index
 * @param da_root: DoubleArrayTrie根节点index
 * @param base: base[]
 * @param check: check[]
 * @return max_ind：维护DoubleArrayTrie节点的最大索引
 */
int ConvertToDoubleArrayTrie(int root, int da_root, int *base, int *check) {
    int max_ind = da_root;
    base[da_root] = getBaseValue(root, base, check);
    for (int i = 0; i < BASE; i++) {
        if (trie[root].next[i] == 0) continue;
        check[base[da_root] + i] = da_root; // 给root子节点进行check赋值
        if (trie[trie[root].next[i]].flag) {
            check[base[da_root] + i] = -da_root; // 标记 成词
        }
    }
    for (int i = 0; i < BASE; i++) {
        if (trie[root].next[i] == 0) continue;
        max_ind = max(
            max_ind,
            ConvertToDoubleArrayTrie(trie[root].next[i], base[da_root] + i, base, check)
        );
    }
    return max_ind;
}

bool searchDATrie(string s) {
    int p = da_root;
    for (auto x : s) {
        int ind = x - 'a';
        if (abs(check[base[p] + ind]) != p) return false;
        p = base[p] + ind;
    }
    return check[p] < 0;
}

// 测试
int main() {
    cout << "DoubleArrayTrie:" << endl;
    clearTrie();

    // 定义输入字符串数量
    int n;
    cin >> n;

    // 写入普通Trie
    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        insert(s);
    }

    base = new int[MAX_CNT];
    check = new int[MAX_CNT];
    memset(base, 0, sizeof(int) * MAX_CNT);
    memset(check, 0, sizeof(int) * MAX_CNT);

    int max_ind = ConvertToDoubleArrayTrie(root, da_root, base, check);

    printf("trie usage : %lu byte\n", cnt * sizeof(node));
    printf("double array trie usage : %lu bype\n", (max_ind + 1) * sizeof(int) * 2); // *2: base[] + check[]

    while (cin >> s) {
        cout << "find " << s << ", from trie : " << search(s) << endl;
        cout << "find " << s << ", from da trie : " << searchDATrie(s) << endl;
    }
    
    return 0;
}

发表评论

邮箱地址不会被公开。