基数树是什么

小嘿QA2020-04-21 16:17:30阅读(...)

在计算机科学中,基数树,或称压缩前缀树,是一种更节省空间的Trie(前缀树)。对于基数树的每个节点,如果该节点是确定的子树的话,就和父节点合并。基数树可用来构建关联数组。 用于IP 路由。 信息检索中用于文本文档的倒排索引。

在计算机科学中,基数树,或称压缩前缀树,是一种更节省空间的 Trie(前缀树)。对于基数树的每个节点,如果该节点是确定的子树的话,就和父节点合并。基数树可用来构建关联数组。 用于 IP 路由。 信息检索中用于文本文档的倒排索引。

基数树是什么

简介

基数树可看做是以二进制位串为关键字的 trie 树,是一种多叉树形结构,同时又类似多层索引表,每个中间节点包含指向多个子节点的指针数组,叶子节点包含指向实际的对象的指针(由于对象不具备树节点结构,因此将其父节点看做叶节点)。基数树也被设计成多道树,以提高磁盘交互性能。同时,基数树也是按照字典序来组织叶节点的,这种特点使之适合持久化改造,加上它的多道特点,灵活性较强,适合作为区块链的基础数据结构,构建持久性区块时较好地映射各类数据集合上。基数树支持插入、删除、查找操作。查找包括完全匹配、前缀匹配、前驱查找、后继查找。所有这些操作都是 O(k)复杂度,其中 k 是所有字符串中最大的长度。

前缀树

在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie 这个术语来自于 retrieval。根据词源学,trie 的发明者 Edward Fredkin 把它读作/ˈtriː/ “tree”。但是,其他作者把它读作/ˈtraɪ/ “try”。trie 中的键通常是字符串,但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie 中的键是一串位元,可以用于表示整数或者内存地址。trie 树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

收藏0个人收藏
走进科技生活方式

评论交流

泪雪默认头像请「登录」后参与评论
  1. 加载中..