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