双数组Trie树中叶子结点check[t]=t的证明

曾经终败给现在 2021-09-17 13:50 129阅读 0赞

双数组Trie树，其实就是用两个一维数组来表示Trie树这种数据结构。

一个数组称为BASE，另一个数组为CHECK。转移条件如下：

对于状态s，接收字符c，转移到状态t

> BASE\[s\]+c=t  
> CHECK\[t\]=BASE\[s\]

1.  BASE数组保存结点的基地址
2.  CHECK数组标识结点的前驱信息

对于根结点，定义：

根结点的状态为0，\\(t\_根=0\\)

根结点的基地址为1，放在BASE数组下标为0处保存，故\\(BASE\[t\_根\]=BASE\[0\]=1\\)。

\\(CHECK\[t\_根\]=CHECK\[0\]=0\\)

对于Trie树中的一个结点nodeA，有如下信息：

*  字符'A'，这是给人看的
 *  字符'A'的状态，用\\(t\_A\\)来表示，\\(t\_A\\)是一个整数。从根结点，经过条件 'A' 转移到nodeA，即：\\(BASE\[0\]+code(A)=t\_A=1+65=66\\)，其中code(A)一般为该字符的ASCII码。
 *  字符'A'的基地址，使用BASE数组来保存
 *  由于字符'A'对应的结点nodeA的前驱是根结点，即\\(CHECK\[t\_A\]=BASE\[0\]=1\\)

对于叶子结点node\_leaf，定义该叶子结点的基地址为begin，code(node\_leaf)=0，对于状态为t\_leaf：

现在来证明：CHECK\[t\_leaf\]=t\_leaf

1.  BASE\[begin+code(node\_leaf)\]=t\_leaf 得到：**BASE\[begin\]**=t\_leaf
2.  CHECK\[t\_leaf\]=**BASE\[begin\]** 得到：CHECK\[t\_leaf\]=t\_leaf

其中，第1、2点就是由转移条件，证明完毕。

另外，在Hancks的[这篇文章中][Link 1]，有如下引用：

> 3、然后将这群兄弟节点的check设为check\[begin + a1…an\] = begin;很显然，**叶子节点i的check\[i\]的值一定等于i**，因为它是兄弟节点中的第一个，并且它的code为0。

就好理解了。  
另外，对于叶子结点而言，BASE\[t\_leaf\]=-index，[参考][Link 2]，其中 -index 表示：该叶子结点所代表的 关键词 在词典中顺序。（当构造双数组树时，词典先加载到TreeMap中，是有序的）

[Link 1]: http://www.hankcs.com/program/java/%E5%8F%8C%E6%95%B0%E7%BB%84trie%E6%A0%91doublearraytriejava%E5%AE%9E%E7%8E%B0.html
[Link 2]: http://www.cnblogs.com/ooon/p/4883159.html