如何克服字典树(TrieTree)的缺点?

一、如何克服字典树(TrieTree)的缺点

对于字典树(TrieTree)的缺点，为了减少空间浪费，有人提出了一些压缩算法。比如基数 Trie（ radix tries），又称紧凑前缀树。基本思想是通过减少树的节点，从而减少空指针。

解决方法是在树的路径上下功夫，如果某个树的路径（包含多个节点）没有分叉，就将其压缩为一个节点，即允许一个节点存储多个字符。

这个压缩方法的代价是，在插入或者删除 key 时，需要处理节点的展开与合并。但，等等，你说我都懂，这和**基数（Radix）**有毛线关系？答案是，Radix Trie 会将所有的 Key 进行二进制展开，以二进制的每个位作为单个字符作为 Trie 树中的字符，进行插入。想想这么做有什么好处？

减少了分叉数（每个节点只有两个分叉 0 和 1），从而减少了无用指针浪费。增大了共同前缀的概率，被拉长的路径，正好可以用路径压缩来缩短。

而 ART（Adaptive Radix Tree） 走的是另外一条路，不是在垂直方向（树的纵深方向）下功夫，而是在水平方向（每个节点的扇出，fan-out）做文章。经典 Trie 需要为字符集中的每个字符保留一个指针，不管其是否真的会存在。ART 正是抓住这一点，提出了一种自适应的 Trie 结构，首先来看看其核心数据结构——Trie 树节点：

union Node {

Node4* n4;

Node16* n16;

Node48* n48;

Node256* n256;

}

看到该数据结构，我们就大概猜出他要干什么了，即在分叉较少时，用小分叉节点；在分叉较大时，使用较大分叉节点。换个角度想，这就类似将经典的 Trie 树种指针从固定数组，换到了可变数组（）。当然，每个节点的查找时间，也从 O(1) 换到了 O(lgn)，不过考虑到 n 一般比较小，也可近似认为 O(1) == O(lgn)。此外，还可以控制可变的档位，可以针对性的对 cache 进行优化

延伸阅读：

二、八叉树（octree）是什么

八叉树（octree）是三维空间划分的数据结构之一，它用于加速空间查询，例如在游戏中：
加速用于可见性判断的视锥裁剪（view frustum culling）。
加速射线投射（ray casting），如用作视线判断或枪击判定。
邻近查询（proximity query），如查询玩家角色某半径范围内的敌方NPC。