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

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

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

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

而 ART（Adaptive Radix Tree） 走的是另外一條路，不是在垂直方向（樹(shù)的縱深方向）下功夫，而是在水平方向（每個(gè)節(jié)點(diǎn)的扇出，fan-out）做文章。經(jīng)典 Trie 需要為字符集中的每個(gè)字符保留一個(gè)指針，不管其是否真的會(huì)存在。ART 正是抓住這一點(diǎn)，提出了一種自適應(yīng)的 Trie 結(jié)構(gòu)，首先來(lái)看看其核心數(shù)據(jù)結(jié)構(gòu)——Trie 樹(shù)節(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)。換個(gè)角度想，這就類似將經(jīng)典的 Trie 樹(shù)種指針從固定數(shù)組，換到了可變數(shù)組（）。當(dāng)然，每個(gè)節(jié)點(diǎn)的查找時(shí)間，也從 O(1) 換到了 O(lgn)，不過(guò)考慮到 n 一般比較小，也可近似認(rèn)為 O(1) == O(lgn)。此外，還可以控制可變的檔位，可以針對(duì)性的對(duì) cache 進(jìn)行優(yōu)化

延伸閱讀：

二、八叉樹(shù)（octree）是什么

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