字典树(trie tree)
假设有b,abc,abd,bcd,abcd,efg,hii这6个单词,我们构建的树就是这样的。
对于每一个节点,从根遍历到他的过程就是一个单词,如果这个节点被标记为红色,就表示这个单词存在,否则不存在。
那么,对于一个单词,我只要顺着他从跟走到对应的节点,再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色,就相当于插入了这个单词。
这样一来我们询问和插入可以一起完成,所用时间仅仅为单词长度,在这一个样例,便是10。
我们可以看到,trie树每一层的节点数是26^i级别的。所以为了节省空间。
如果是数字的话。
比如456,百位是4,十位是45,个位是456
区间查询的话,423-642
分为5次查询:
百位:
5
十位:
43-49
50-59 因为百位5所以忽略直接命中
60-63
个位:
423-429
430-499因为十位43-49直接命中
500-599因为百位5
600-639因为十位60-63
640-642