基数树






基数树的一个例子


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



应用


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



操作


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



查找




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









Popular posts from this blog

Mount Tamalpais

Indian Forest Service

Y