K 代表形成Trie的字符串集合。Trie由结点和连接结点的边（arc）组成。结点由Double-Array的下标来标记，边则是由字符来标记，如果一条边从结点n到结点m被标记成a，那么我们可以定义如下的函数g(n,a)=m 。
对于集合K中的一个字符串S在Trie中形成的一条路径P，如果路径P中有结点m满足g(n,a)=m ,使得在Trie中检索S时，检索到字符a就已经能够将字符串S与Trie中的其它字符串区别开来，那么结点m称为separate node 。
Double-Array和reducedtrie 的关系如下：（到这里就很容易理解了，reduced trie表示的是一种结构，而Double-Array则表示reduced-trie这种结构的存储方式）
一、结点1永远是Trie的根结点，所以Trie的插入和查找操作都是从BASE[1]开始。
二、CHECK[m]=n 所表达的意思是：结点m的父结点是n . 所以如果表述为father[m]=n可能更清楚一些。
三、在Double-Array中，除CHECK[1]之外，如果CHECK[m]=0,则表示结点m是孤岛，是可用的。Double-Array实际就就是通过g(n,a)=m把这些孤岛连接成reduced trie这种树形结构。这一点在理解trie的insertion操作时会有帮助。
Case 4: 插入字符时出现需要修改现有BASE值的冲突。(位置占用冲突)
冲突的出现意味着在double-array中两个不同的字符通过g(n,a)得到了同样的m值，换话话说，两个不同的父结点拥有了同一个孩子（表现在double-array中就是两个字符争夺数组中的同一个空间位置）。
这样1就作为了BASE[4]新的候选值，CHECK[3]=0也表明结点3是可以作为结点4的子结点。这样结点4和结点3就可以通过g(4,a)=g(4,2)=3关系式，把字符a存储到double-array中了。
Case 4：抢占位置引发的冲突
（现在进入到整篇文章最核心的地方了，也就是DATrie最难的地方）
就像Case 3 一样，BASE数组中的值必须进行修改才能解决冲突。插入”baby#”的步骤演示如下：
步骤1：根结点在BASE数组的下标1位置，所以从BASE[1]开始。
对于baby#中前三个字符而言，BASE和CHECK中的值如下；
BASE[4]+’a’=1+2=3, CHECK[3]=4
BASE[3]+’b’=1+3=4, CHECK[4]=1≠3
CHECK[4]的计算结果出现前后不一致的现象表明有一个状态没有被考虑到。这也意味着结点1或者结点3的BASE值需要进行修改。（这里可以这样理解：结点4作为子结点被父结点1和父结点3争夺,我们有两种方法解决冲突：结点1放弃孩子或者结点3放弃孩子。如果是结点1让步，那么就需要修改BASE[1]，如果结点3让步，那么就需要修改BASE[3]）
原文：http://www.cnblogs.com/agileblog/p/3638190.html