爆炸式字典树

上一篇文章《

字典树

》，介绍了字典树的四种实现形式。本文讨论两种改进的字典树。

补充上篇文章中提到的array trie，hash trie 以及 list trie的node结构如下：

Burst Tries

爆炸式字典树，开始的时候采用一个容器存储key。一旦容器full之后，“爆炸”产生多个分支，指向各个子容器，每一次爆炸，子树的高度加1.

一颗爆炸树结构，大致如下图所示，图中采用的是BST树作为容器结构。

具体开源代码，可以参考：https://github.com/gabrieldumitrescu/BurstTrie

参考论文：Heinz S, Zobel J, Williams H E. Burst tries: a fast, efficient data structure for string keys[J]. ACM Transactions on Information Systems (TOIS), 2002, 20(2): 192-223.

论文ppt：http://www.cs.uvm.edu/~xwu/wie/CourseSlides/Schips-BurstTries.pdf

HAT-trie

爆炸式字典树，一句话总结就是，用容器替代叶子节点的字典树。HAT-trie的原理相对简单，采用了一个cache优化的hash容器实现的爆炸式字典树而已。链式hash由于指针过多，性能不好。下面三张图一看就懂了。

参考资料：

https://en.wikipedia.org/wiki/HAT-trie

https://tessil.github.io/2017/06/22/hat-trie.html

https://github.com/Tessil/hat-trie

https://github.com/dcjones/hat-trie

Askitis N, Sinha R. HAT-trie: a cache-conscious trie-based data structure for strings[C]//Proceedings of the thirtieth Australasian conference on Computer science-Volume 62. Australian Computer Society, Inc., 2007: 97-105.

文章中，屏蔽了很多，插入，删除，爆炸操作等一系列细节，感兴趣的可以去review代码