double array trie 插入结点总结

双数组Trie树索引的可操作性研究.pdf

提示:任一状态点的移动,会影响其Trie树中父节
点的base值的选择以及兄弟结点位置的变动,而兄
弟结点的移动又须变更相应的子节点的check值。

设待插入的词或其子串为‘c1c2c3...’。由双数
组的结构可以看出,当索引中已经存在以单个字符G
为状态的状态点时,所需的操作与建立双数组时的相
同,不影响双数组的整体结构,我们把符合这种情况
的词或其子串统称为“稳定词”。

(1)字符c1不在序列码表中,把c1加入序列码表中,设定其码值为数组大小。

(2) 索引中存在以字符c1,以及(c1,....ci-2)ci-1
为状态的状态点,但字符Ci不在序列码表中。这时要把ci加入序列码表。

比如:青年,青菜,已经在索引中,但青壮年中的‘壮‘不在序列码中,这时需要调整’壮‘的兄弟结点‘年’‘菜’,的插入位置,并修改兄弟结点孩子的check值。青年,青菜,没有孩子结点。

(3) 索引中存在以字符c1以及c1...ci-2ci-1’
为状态的状态点,字符Ci也在序列码表中,但状态点
c1...ci-2ci-1ci不存在索引中。

如: 白菜,白金在索引中,白伯不在索引中,需要修改白的base值,及白菜,白金的插入位置。并修改白菜心(白菜的孩子结点)的check值。

原先索引中已经存在:阿伯,现在新插入结点白伯,类似于: 青菜,白菜。

(4) ci 在序列码中,但ci不是首字状态点。把ci对应位置空出来,存放ci。ci位置原先结点及其兄弟结点插入其他位置,并修改其父节点的base值,孩子结点的check值,类似于relocate。

原文地址:https://www.cnblogs.com/agileblog/p/3640457.html