一、如何克服字典樹(TrieTree)的缺點(diǎn)

對于字典樹(TrieTree)的缺點(diǎn)，為了減少空間浪費(fèi)，有人提出了一些壓縮算法。比如基數(shù) Trie（ radix tries），又稱緊湊前綴樹。基本思想是通過減少樹的節(jié)點(diǎn)，從而減少空指針。

解決方法是在樹的路徑上下功夫，如果某個樹的路徑（包含多個節(jié)點(diǎn)）沒有分叉，就將其壓縮為一個節(jié)點(diǎn)，即允許一個節(jié)點(diǎn)存儲多個字符。

這個壓縮方法的代價(jià)是，在插入或者刪除 key 時(shí)，需要處理節(jié)點(diǎn)的展開與合并。但，等等，你說我都懂，這和**基數(shù)（Radix）**有毛線關(guān)系？答案是，Radix Trie 會將所有的 Key 進(jìn)行二進(jìn)制展開，以二進(jìn)制的每個位作為單個字符作為 Trie 樹中的字符，進(jìn)行插入。想想這么做有什么好處？

而 ART（Adaptive Radix Tree） 走的是另外一條路，不是在垂直方向（樹的縱深方向）下功夫，而是在水平方向（每個節(jié)點(diǎn)的扇出，fan-out）做文章。經(jīng)典 Trie 需要為字符集中的每個字符保留一個指針，不管其是否真的會存在。ART 正是抓住這一點(diǎn)，提出了一種自適應(yīng)的 Trie 結(jié)構(gòu)，首先來看看其核心數(shù)據(jù)結(jié)構(gòu)——Trie 樹節(jié)點(diǎn)：

union Node {

??? Node4* n4;

??? Node16* n16;

??? Node48* n48;

??? Node256* n256;

}

看到該數(shù)據(jù)結(jié)構(gòu)，我們就大概猜出他要干什么了，即在分叉較少時(shí)，用小分叉節(jié)點(diǎn)；在分叉較大時(shí)，使用較大分叉節(jié)點(diǎn)。換個角度想，這就類似將經(jīng)典的 Trie 樹種指針從固定數(shù)組，換到了可變數(shù)組（）。當(dāng)然，每個節(jié)點(diǎn)的查找時(shí)間，也從 O(1) 換到了 O(lgn)，不過考慮到 n 一般比較小，也可近似認(rèn)為 O(1) == O(lgn)。此外，還可以控制可變的檔位，可以針對性的對 cache 進(jìn)行優(yōu)化

延伸閱讀：

二、八叉樹（octree）是什么

八叉樹（octree）是三維空間劃分的數(shù)據(jù)結(jié)構(gòu)之一，它用于加速空間查詢，例如在游戲中：
加速用于可見性判斷的視錐裁剪（view frustum culling）。
加速射線投射（ray casting） ，如用作視線判斷或槍擊判定。
鄰近查詢（proximity query），如查詢玩家角色某半徑范圍內(nèi)的敵方NPC。