基数树

维基百科,自由的百科全书
跳转至: 导航搜索
基数树的一个例子

计算机科学中,基数树,或称Patricia trie/tree,或crit bit tree,压缩前缀树,是一种更节省空间的Trie(前缀树)。对于基数树的每个节点,如果该节点是唯一的儿子的话,就和父节点合并。

应用[编辑]

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

操作[编辑]

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

查找[编辑]

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