前言
本章节内容有一定难度，初学者可以选择性学习
我们从晗佬的双数组结构来逆向理解这个流程，就会简单很多。
一、构造*
何晗大佬的书上本节写的特别多，也比较复杂，我讲概述一下，首先，我们要明白双数组字典树是一个深度优先遍历的问题，目的是为字典树的每个节点分偶一个双数组中的下标，并维护双数组的值。构造算法的过程是递归的。
二、由图和文字介绍来理解
1.图
2.分析图
看图：想要分配父节点，就必须先把所有的子节点分配完成。 举例：
0->3-2-1
5->6-8-7-11-10-9
构建完成的双数组结构如下：（不需要理解数值怎么来的）
下面这段话，一定要多看几遍，对应上图，反复一步一步走
让我们来验证一下双数组是否构建正确，以“自然”的查询为例。
1.初始状态下标b=0，“自”的 UTF-16BE 编码为33258，尝试状态转移p=base[0] +33258+1=33260。检查base[0] ==check [33260]是否成立，发现两者都是1。
2.转移成功，新的状态下标b=p=33260。
3.接着往下走,“然”的编码为28982，尝试状态转移p=base[33260]+28982+1=38380。检查base [33260]==check [38380]是否成立，发现两者都是9397。
4.再次转移成功，新的状态下标b=p=38380。这个状态是否对应一个单词?
5.我们尝试按\0进行转移，\0的编码为0且无需加一（原因见上文), p=base[38380]+0=38381，且满足base[38380] ==check [38381]
6.于是状态转移成功b=p=38381，这说明的确是一个词语的结尾。
7.根据约定，结尾状态的base [38381]=-2代表-index-1.于是求出index=1。也就是说“自然”的字典序是1，于是取出value数组中下标为1的元素natural作为“自然”的关联值。
三、逆向理解
我这里再给出晗佬的构造思路，大家再来看，就清晰的多了
(1)为根节点分配下标0，初始化base [0]=1; check [0]=0;。以根节点为最初的父节点开始深度优先遍历，兄弟节点按照字符的散列值（记作 code,Java中为UTF-16编码)升序排列。
(2)约定check [i]=0代表i空闲。检查父节点p的子节点列表[s1…sn]，寻找一个起始下标b，使得所有check[base[b]+si.code]==0。也就是说，找到n个空闲下标插入这群子节点。执行check[base[b]+ si.code]= base[b],也即将这n个空闲空间分配给这群子节点。这样n个子节点base[b]+ si.code就链接到了父节点p在base数组中的下标b，建立了子与父多对一的关系。
(3)检查每个子节点si，若它没有孩子，也就是图2-3的叶子节点(蓝色),则将它的 base设为负值，以存储它所对应单词的字典序index，即 base[base[b]+si.code]=-si.index-1 ;若它有孩子，则跳转步骤(2)，递归插人。记s,的子节点们的起始下标为h,执行base[base[b]+ si.code]=h。这样父节点base[b]+si.code就链接到了子节点插入的起始下标h(多个子节点共享)，建立了一对多的父子关系。
步骤(2)寻找空闲下标，维护check数组，建立子与父多对一的关系。
步骤(3)维护base数组，建立父与子一对多的关系。两种关系缺一不可。
因为根据定义，转移时先根据base提供的父子关系尝试转移，然后还需要根据check 数组校验子父关系。
四、测评
直接引用晗佬的了，跟之前的测评方法一样。
总结
本章节的内容很多文字，需要慢慢理解与消化，建议找个大段的时间来深入理解。反复揣摩晗佬的思维，化为己用。
