一、如何克服字典樹(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)行插入。想想這么做有什么好處?
減少了分叉數(shù)(每個(gè)節(jié)點(diǎn)只有兩個(gè)分叉 0 和 1),從而減少了無(wú)用指針浪費(fèi)。增大了共同前綴的概率,被拉長(zhǎng)的路徑,正好可以用路徑壓縮來(lái)縮短。而 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。