返回信息流RT
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #90680同步于 2016/8/1
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
跪求大神分析双数组Trie树算法实现
Chyler
2016/8/1镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
https://linux.thai.net/~thep/datrie/datrie.html
楼主看看这篇吧，算是讲得比较详细的了。
另外官方也有源码可以下载，不过我觉得那个源码太晦涩了。
看了这个也没搞明白 觉得自己宛如制杖
【 在 liyi5133 的大作中提到: 】
: https://linux.thai.net/~thep/datrie/datrie.html
:
: 楼主看看这篇吧，算是讲得比较详细的了。
: 另外官方也有源码可以下载，不过我觉得那个源码太晦涩
: .........
发自「贵邮」
静下来慢慢看，反正就是base和check有两个判断，数组放不下的时候就重新分配调整，因为是数组的形式表示所以看起来不直观，再加上优化什么的很容易就懵逼了。
这篇论文是讲的比较好的了，别的中文资料大多参照这个翻译的，它偏原始的双数组，没有太多优化，官方源码那个库更复杂。
不过我觉得这东西构筑维护这么复杂，还老再分配 ，不是做研究的话真的一定要用这个吗？能省多少空间呢？
发自「贵邮」
需求主要是层数多 每层节点又少 用传统的trie数数据结构感觉浪费空间，换动态数组时间又上去了
我安心看看源码
多谢！
【 在 liyi5133 的大作中提到: 】
: 静下来慢慢看，反正就是base和check有两个判断，数组放不下的时候就重新分配调整，因为是数组的形式表示所以看起来不直观，再加上优化什么的很容易就懵逼了。
: 这篇论文是讲的比较好的了，别的中文资料大多参照这个翻译的，它偏原始的双数组，没有太多优化，官方源码那个库更复杂。
: 不过我觉得这东西构筑维护这么复杂，还老再分配 ，不是做研究的话真的一定要用这个吗？能省多少空间呢？
: ...................
有考虑过压缩trie吗？或者左孩子右兄弟的表示？
【 在 Chyler 的大作中提到: 】
: 需求主要是层数多 每层节点又少 用传统的trie数数据结构感觉浪费空间，换动态数组时间又上去了
: 我安心看看源码
: 多谢！
: 【 在 liyi5133 的大作中提到: 】
: : 静下来慢慢看，
: .........
发自「贵邮」