双数组压缩树

两个数组 base check

• begin 偏移量

• 公式

  check[begin+code]=begin

  base[begin+code]=begin(子节点的)

  ps：每个词语的结尾 默认是有一个字符的 这个字符code=0带入公式如下

  check[begin]=begin

  base[begin]=index(这个词语的id)

偏移量是不能重复的

流程演示

输入词

12

123

345

398

1. 构建字典树

1. 跟节点开始 begin=base[0]=1 因为数组中还没有元素偏移量为1,check[0]默认值是0
2. check[1+code_1]=1 check[1+code_3]=1 ,然后找1，3的偏移量，这里假设为2
3. 为base数组赋值base[2+code_1]=2 base[2+code_3]=2
4. check[2+code_2]=2
5. 找2的偏移量假设3 base[3+code_2]=3

6. 这里需要注意 2下面有3，同时是2的结尾，结尾的code为0赋值如下

   base[0+3]=index(这个index一般用负数表示) check[3+code_3]=3

7. 依次类推，即可构建

查询过程如下

比如要找12

• root节点开始 base[0]==1得到偏移量是1
• 检查1是否是root的子节点，如果 check[1+code_1]==1说明1是root的子节点
• 然后检查1是否是一个词check[1]==1&&base[1]<0 说明1就是一个词，、
• 依次类推

ps：偏移量是不能重复的，所以构建的时候需要一个数组来维护，使用过的偏移量