首页 > 其他 > 详细

模板 - 数据结构 - Trie

时间:2019-11-14 17:41:59      阅读:80      评论:0      收藏:0      [点我收藏+]

使用静态数组的nxt指针的设计,大概比使用map作为nxt指针的设计要快1倍,但空间花费大概也大1倍。在数据量小的情况下,时间和空间效率都不及map<vector,int>。map<vector,int>的最坏情况下效率为O(nlogn*len),而Trie的效率为O(n*len),但是实际上测出来还是map快一点,有可能在vector实际比较的时候很快就得出大小了。

时间复杂度:
初始化:O(sigma)
插入:O(len*sigma)
查询:O(len)

空间复杂度:
O(n*len*sigma)

struct TrieNode {
    int data;
    int nxt[26];

    void init() {
        data = 0;
        memset(nxt, 0, sizeof(nxt));
    }
};

struct Trie {
    TrieNode tn[200005];
    int root, top;

    int newnode() {
        tn[++top].init();
        return top;
    }

    void init() {
        top = 0;
        root = newnode();
    }

    void insert(int *a, int len, int data) {
        int cur = root;
        for(int i = 1; i <= len; ++i) {
            int &nxt = tn[cur].nxt[a[i] - 'a'];
            if(!nxt)
                nxt = newnode();
            cur = nxt;
        }
        tn[cur].data = data;
    }

    int query(int *a, int len) {
        int cur = root;
        for(int i = 1; i <= len; ++i) {
            int &nxt = tn[cur].nxt[a[i] - 'a'];
            if(!nxt)
                return -1;
            cur = nxt;
        }
        return tn[cur].data;
    }
} trie;

模板 - 数据结构 - Trie

原文:https://www.cnblogs.com/KisekiPurin2019/p/11858431.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!