计算机科学中,基数树(英語:Radix Trie,也叫基数特里树压缩前缀树)是一种数据结构,是一种更节省空间的Trie(前缀树),其中作为唯一子节点的每个节点都与其父节点合并,边既可以表示为元素序列又可以表示为单个元素。 因此每个内部节点的子节点数最多为基数树的基数r ,其中r为正整数,是2的x次方,x≥1,这使得基数树更适用于对于较小的集合(尤其是字符串很长的情况下)和有很长相同前缀的字符串集合。

基数树的一个例子

基数树的查找方式也与常规树不同(常规的树查找一开始就对整个键进行比较,直到不相同为止),基数树查找时节点时,对于节点上的键都按块进行逐块比较,其中该节点中块的长度是基数r; 当r为2时,基数树为二进制的(即该节点的键的长度为1比特位),能最大程度地减小树的深度来最小化稀疏性(最大限度地合并键中没有分叉的节点)。 当r≥4且为2的整数次幂时,基数树是r元基数树,能以潜在的稀疏性为代价降低基数树的深度。

应用

编辑

基数树可用来构建关联数组。 用于IP 路由信息检索中用于文本文档的倒排索引

操作

编辑

基数树支持插入、删除、查找操作。查找包括完全匹配、前缀匹配、前驱查找、后继查找。所有这些操作都是O(k)复杂度,其中k是所有字符串中最大的长度。

查找

编辑
 
示例:基数树中查找一个字符串