基數樹

基數樹的一個例子

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

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

應用

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

操作

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

查找

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