基数树
外观
此条目没有列出任何参考或来源。 (2010年2月10日) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/ae/Patricia_trie.svg/400px-Patricia_trie.svg.png)
在计算机科学中,基数树(英语:Radix Trie,也叫基数特里树或压缩前缀树)是一种数据结构,是一种更节省空间的Trie(前缀树),其中作为唯一子节点的每个节点都与其父节点合并,边既可以表示为元素序列又可以表示为单个元素。 因此每个内部节点的子节点数最多为基数树的基数r ,其中r为正整数,是2的x次方,x≥1,这使得基数树更适用于对于较小的集合(尤其是字符串很长的情况下)和有很长相同前缀的字符串集合。
基数树的查找方式也与常规树不同(常规的树查找一开始就对整个键进行比较,直到不相同为止),基数树查找时节点时,对于节点上的键都按块进行逐块比较,其中该节点中块的长度是基数r; 当r为2时,基数树为二进制的(即该节点的键的长度为1比特位),能最大程度地减小树的深度来最小化稀疏性(最大限度地合并键中没有分叉的节点)。 当r≥4且为2的整数次幂时,基数树是r元基数树,能以潜在的稀疏性为代价降低基数树的深度。
应用
[编辑]基数树可用来构建关联数组。 用于IP 路由。 信息检索中用于文本文档的倒排索引。
操作
[编辑]基数树支持插入、删除、查找操作。查找包括完全匹配、前缀匹配、前驱查找、后继查找。所有这些操作都是O(k)复杂度,其中k是所有字符串中最大的长度。
查找
[编辑]![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/63/An_example_of_how_to_find_a_string_in_a_Patricia_trie.png/220px-An_example_of_how_to_find_a_string_in_a_Patricia_trie.png)
|
![]() | 这是一篇与计算机相关的小作品。您可以通过编辑或修订扩充其内容。 |