对三叉搜索树的理解

Post by zerob13

对于字符串的高效处理一般都是用字典树——Trie,或者ac自动机的。但是字典树对于大量数据的空间的开销相当大,特别我们的字典中不仅仅是26个字母组成的字符串时空间的损耗就会巨大无比。。。
三叉搜索树就是一种比较好的解决方法,我第一次看到的时候时在最近的《程序员》杂志上的一篇文章——《用三叉搜索树实现高效率的“自动完成”》,是一个.net大牛写的~于是我便对这个产生了兴趣,在折腾几天后,终于用java也写了一个很挫的三叉搜索树(见用三叉搜索树实现高效字符查找)。
其实所谓的三叉树就是舍去了Trie的多余的指针,而是把一个个树套在一起,每个节点压缩成三个方向。如果匹配的话就走中间方向的指针,如果不匹配,那么就走左或者右指针。选左选右则是这个数据结构优化的一个好地方,我用了字母顺序,文章作者说这个是最挫的方法。。。窘一个。。。好方法我还没有想到,因为不会写自平衡的树。。。杯具一个。。。
这里有一个例子,假如我们存入”AB”,”ABBA”.”ABCD”.”BCD”,这几个单词,那么三叉树就会出现如下的储存方式。。。

tt

红线表示匹配的箭头~黄色的表示单词结尾