双数组Trie树 - milkandbread/summary-interview GitHub Wiki
双数组Trie树对比Trie树优缺点：
双数组 Trie 树是目前 Trie 树各种实现中性能和存储空间均达到很好效果的实现。但其完整的实现比较复杂，对于新手而言入手相对较难，因此本节将花费较多的篇幅对其解读。
双数组 Trie 树和经典 Trie 树一样，也是用数组实现 Trie 树。只不过它是将所有节点的状态都记录到一个数组之中（Base Array），以此避免数组的大量空置。
使用场景：
假设我们的词库里面有这么一些词，中国，北京，中华，华北这几个词语，需要构建一棵Trie树，构建好了以后，用户输入中字的时候，能把中国，中华都给提示出来。
Trie树构建
首先，拿到这些个词以后，第一步就要构建这棵Trie树了，构建之前，我们先对每一个字进行编号一下，这个只是为了方便描述，中:1,国:2,北:3,京:4,华:5。
初始化:
* 初始化空数组，初始化base和check两个空数组。
* base的元素为1表示是开始位偏移为1，为-1表示没有数据。
* check的元素中，-1表示没有数据，-2表示这是一个词结束了，-3表示是根节点，如下图所示
插入中国这个词中的’中‘字
* 从根节点开始，base[0]=1，插入位置为base[0]+中，中的编号为1，所以是base[0]+1=1+1=2，于是得到应该插入到base[2]的位置。
* 检查check[2]，看到check[2]为-1，表示base[2]没有数据，可以插入
* 更新check[2]为上一个节点的base数组的下标，上一个节点是base[0]，所以更新为0
* 更新base[2]为上一个节点的base数组的值，上一个节点base[0]的值是1，所以更新为1
* 按照上面的四个步骤更新完了以后，整个数组变成下面这个样子，对着图可以仔细想想整个过程，然后你想想伪代码是什么样子的，再想想如何编程。
插入国字:
由于这个词语还没结束，所以从base[2]开始继续往下走
从base[2]开始，插入位置为base[2]+国，国的编号是2，所以是base[2]+2=1+2=3，应该插入到base[3]中
检查check[3]，看到check[2]为-1，表示base[2]没有数据，可以插入
更新check[3]为上一个节点的base数组下标，上一个是base[2]，所以更新为2
更新base[3]为上一个节点的base数组的值，上一个节点base[2]的值是2，所以更新为2
插入'华北'这个词 到现在一切都很顺利，接下来插入华北这个词，这里就会遇到冲突了，遇到冲突以后，进行如下算法
插入'华'字:
插入'北'字:
* 由于这个词语还没结束，所以从base[6]开始继续往下走
* 从base[6]开始，插入位置为base[2]+北，国的编号是3，所以是base[6]+3=1+3=4，应该插入到base[4]中
* 检查check[4]，看到check[2]为0，表示base[4]有数据，_产生冲突！！_
* 从base[6]往后找空闲空闲，空闲空间的概念是两个数组都是-1
* 找到base[8]和check[8]为空闲空间
* 更新check[8]为上一节点的值，6
* 计算base[6]应该的值为8-北=8-3=5，更新base[6]为5，_解决冲突！_
cedar是C++实现的高效双数组trie