`

基于trie树做数值范围查询的原理

 
阅读更多
trie树,也称作前缀树,是有序的树状数据结构。它的特点是节点在树中的位置与节点的值有关联。一个节点的所有后代都以该节点作为前缀,通常根节点是空的,这就是前缀树的含义。

用trie树构造的数据结构如下
         4                  5             6
  42          44            55         64          66

421 423    442 445 446      552    641 642              665 667

如果要查找集合中所有大于423,小于667的记录,该如何做呢?
trie树不需要把第三层的记录都取出来比较,根据trie的特点,只需要查找否含有423、44、5、64、665、667这6个值的记录,这样做就优化了范围搜索的速度。
分享到:
评论

相关推荐

    面试指南-Lucene:ES篇.md

    - **VInt**:基于字节的编码方式,根据数值大小动态分配字节数。 **4. Trie字典树(Prefix Trees)原理** Trie树是一种特殊的树形结构,常用于字符串匹配问题。每个节点表示一个字符,路径代表一个字符串。在...

    PatriciaTrieTemplateClass_src_matlab_

    1. **数据结构设计**:理解 Patricia Trie 的工作原理,包括节点结构、链接关系以及如何通过位操作来减少内存占用和提高查找效率。 2. **MATLAB 类定义**:使用 MATLAB 的面向对象编程功能来定义和实现 Trie 类,...

    数据结构优质参考代码

    常见的树类型包括二叉树、二叉搜索树、平衡树(如AVL树和红黑树)、堆(最大堆和最小堆)以及 Trie 字典树等。每种树都有其特定的操作,例如插入、删除、查找等,这些操作的效率与树的特性紧密相关。 接着是“图”...

    信息学奥赛-省选及NOI课程表(2020.08.31).pdf

    9. **树套数**:一种特殊的数据结构,将数值存储于树形结构中,适用于处理特定类型的查询。 10. **数据结构维护与应用**:涉及如何有效地维护数据结构以及如何利用这些数据结构解决实际问题。 11. **常见省选数据...

    ACM算法整合

    - 树状数组也称为二叉索引树,用于高效地查询和更新区间上的数值。 - **二维树状数组** - 扩展树状数组的概念,支持二维空间中的查询和更新操作。 - **TRIE树(K叉)** - TRIE树是一种用于存储字符串的前缀树,可...

    1333个c程式范例的光碟 (algorithms)

    6. **字符串处理**:模式匹配、KMP算法、Trie树等,用于处理和分析文本数据。 7. **数值计算**:平方根计算、快速傅里叶变换(FFT)等,用于数学和科学计算。 这些C语言实现的算法范例对于提升编程能力、解决实际...

    吉大 各种基本ACM必备算法基础

    大数运算是指超出计算机内置整型数据类型范围的数值运算。通常使用数组或链表来存储大数,并实现加法、乘法等基本运算。 ##### 最长公共递增子序列O(N^2) 最长公共递增子序列问题是指找到两个序列中的最长递增子...

    ACM算法模板集史上最完整收藏版

    - 堆排序、优先队列等都基于此原理。 7. **逆序数**: - 通过归并排序可以高效地计算。 - 在排序算法分析中有着重要作用。 8. **树状DP**: - 将动态规划应用于树结构中。 - 在解决与树结构相关的问题时非常...

    ACM-ICPC代码库.吉林大学2007-2008

    4. **Trie树(K叉)**和**Trie树(左儿子右兄弟)**:Trie树用于存储字符串,提供高效的前缀搜索能力。 5. **后缀数组**:用于文本检索,O(N*logN)和O(N)的构建算法分别用于不同的场景。 6. **RMQ离线算法**:用于解决...

    Word内查重与词频统计202103-纯C#版本-vs2010编写.rar

    同时,为了提高查重速度,可以使用Trie树或者倒排索引等数据结构,快速查找重复的句子。 在开发过程中,测试是非常关键的一环。开发者可能创建了各种测试用例,包括不同长度、重复率和词频分布的文档,以确保程序在...

    上海交通大学acm模板(已修复的)

    5. **数字树**:即Trie树,用于高效存储和检索字符串等数据。 6. **线段树**:一种动态维护区间信息的数据结构。 7. **并查集**:用于处理不交集合并查询的问题。 8. **快速排序**:一种高效的排序算法。 9. **...

    ACM/ICPC常用算法的代码库(吉林大学版,强烈推荐)

    - **树状数组**:也称作二叉索引树,用于高效查询和更新数值。 - **二维树状数组**:在二维空间上使用树状数组,支持高效查询和更新操作。 - **TRIE树(K叉)**:用于存储字符串的前缀树,支持高效查找和插入操作。 - ...

    ACM 成长之路

    - 高精度加减乘除实现,能够处理超过标准整数类型所能表示的数值范围。 4. **二分查找** - 在有序数组中查找指定元素的位置,通常用于搜索操作。 5. **几何计算** - **叉乘**: 计算向量之间的叉积,用于判断...

    阿里巴巴校园招聘历年经典面试题汇总:C++研发 1

    3. **字典树构造及其优化**:字典树(Trie)是一种用于快速查找的树形数据结构,尤其适合于字符串的前缀查找。优化通常涉及减少空间占用和提高查询速度。 4. **持久化数据结构**:这种数据结构能在系统重启或关闭后...

    算法竞赛入门基础篇(个人整理)

    Trie(字典树)** - 一种用于存储字符串集合的树形数据结构,特别适合于字符串的查找和匹配。 **6. 并查集** - 用于处理不交集合并的问题,如图的连通性问题。 **7. 堆与哈希表** - 堆是一种特殊的完全二叉树...

    上海交大ACM模板,ACMer值得一看

    数字树也称为Trie树,是一种用于处理字符串的树形结构。在搜索和插入操作上具有很高的效率,广泛应用于词典、搜索引擎等领域。 #### 1.7 区间树 (Segment Tree) 区间树是一种支持区间查询和更新操作的数据结构。它...

Global site tag (gtag.js) - Google Analytics