基数树 在计算机科学中基数树英語Radix Trie也叫基数特里树或压缩前缀树是一种数据结构是一种更节省空间的Trie前缀树其中作为唯一子节点的每个节点都与其父节点合并边既可以表示为元素序列又可以表示为单个元素 因此每个内部节点的子节点数最多为基数树的基数r 其中r为正整数是的x次方x这使得基数树更适用于对于较小的集合尤其是字符串很长的情况下和有很长相同前缀的字符串集合 基数树的查找方式也与常规树不同常规的树查找一开始就对整个键进行比较直到不相同为止基数树查找时节点时对于节点上的键都按块进行逐块比较其中该节点中块的长度是基数r 当r为时基数树为二进制的即该节点的键的长度为比特位能最大程度地减小树的深度来最小化稀疏性最大限度地合并键中没有分叉的节点 当r且为的整数次幂时基数树是r元基数树能以潜在的稀疏性为代价降低基数树的深度