关于Double Array Trie的理解
在只有根节点完美散列的前缀树中，其余节点都在用二分查找。当存在c个子节点时，每次状态转移的复杂度为 O(log c)。当c很大时，依然很慢。双数组字典树（Double Array Trie，DAT）就是一种状癌转移复杂度为常熟的数据结构，双数组字典树由日本人Jun-Ichi Aoe于1989年提出DAT 如其名，维护着两个数组——base 和 check。DAT中，每个节点都表示一种状...
