跳至內容

基數樹

維基百科,自由的百科全書
基數樹的一個例子

計算機科學中,基數樹(英語:Radix Trie,也叫基數特里樹壓縮前綴樹)是一種數據結構,是一種更節省空間的Trie(前綴樹),其中作為唯一子節點的每個節點都與其父節點合併,邊既可以表示為元素序列又可以表示為單個元素。 因此每個內部節點的子節點數最多為基數樹的基數r ,其中r為正整數,是2的x次方,x≥1,這使得基數樹更適用於對於較小的集合(尤其是字符串很長的情況下)和有很長相同前綴的字符串集合。

基數樹的查找方式也與常規樹不同(常規的樹查找一開始就對整個鍵進行比較,直到不相同為止),基數樹查找時節點時,對於節點上的鍵都按塊進行逐塊比較,其中該節點中塊的長度是基數r; 當r為2時,基數樹為二進制的(即該節點的鍵的長度為1比特位),能最大程度地減小樹的深度來最小化稀疏性(最大限度地合併鍵中沒有分叉的節點)。 當r≥4且為2的整數次冪時,基數樹是r元基數樹,能以潛在的稀疏性為代價降低基數樹的深度。

應用

基數樹可用來構建關聯數組。 用於IP 路由信息檢索中用於文本文檔的倒排索引

操作

基數樹支持插入、刪除、查找操作。查找包括完全匹配、前綴匹配、前驅查找、後繼查找。所有這些操作都是O(k)複雜度,其中k是所有字符串中最大的長度。

查找

示例:基數樹中查找一個字符串