基數樹
外觀
此條目沒有列出任何參考或來源。 (2010年2月10日) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/ae/Patricia_trie.svg/400px-Patricia_trie.svg.png)
在計算機科學中,基數樹(英語:Radix Trie,也叫基數特里樹或壓縮前綴樹)是一種數據結構,是一種更節省空間的Trie(前綴樹),其中作為唯一子節點的每個節點都與其父節點合併,邊既可以表示為元素序列又可以表示為單個元素。 因此每個內部節點的子節點數最多為基數樹的基數r ,其中r為正整數,是2的x次方,x≥1,這使得基數樹更適用於對於較小的集合(尤其是字符串很長的情況下)和有很長相同前綴的字符串集合。
基數樹的查找方式也與常規樹不同(常規的樹查找一開始就對整個鍵進行比較,直到不相同為止),基數樹查找時節點時,對於節點上的鍵都按塊進行逐塊比較,其中該節點中塊的長度是基數r; 當r為2時,基數樹為二進制的(即該節點的鍵的長度為1比特位),能最大程度地減小樹的深度來最小化稀疏性(最大限度地合併鍵中沒有分叉的節點)。 當r≥4且為2的整數次冪時,基數樹是r元基數樹,能以潛在的稀疏性為代價降低基數樹的深度。
應用
[編輯]基數樹可用來構建關聯數組。 用於IP 路由。 信息檢索中用於文本文檔的倒排索引。
操作
[編輯]基數樹支持插入、刪除、查找操作。查找包括完全匹配、前綴匹配、前驅查找、後繼查找。所有這些操作都是O(k)複雜度,其中k是所有字符串中最大的長度。
查找
[編輯]![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/63/An_example_of_how_to_find_a_string_in_a_Patricia_trie.png/220px-An_example_of_how_to_find_a_string_in_a_Patricia_trie.png)
|
![]() | 這是一篇與電腦相關的小作品。您可以透過編輯或修訂擴充其內容。 |