范围查询的数据结构 [英] Data structure for range query
问题描述
最近有人问我有关以下问题的编码问题。
对于这个问题，我有一些解决方案，但是我不确定它们是否最有效。
I was recently asked a coding question on the below problem. I have some solution to this problem but I am not very sure if those are most efficient.
问题：
编写一个程序来跟踪一组文本范围。起点和终点将是字符串。
Write a program to track set of text ranges. Start point and end point will be string.
Text range example : [AbA-Ef]
Aa would fall before this range
AB would fall inside this range
etc.
字符串比较将像'A'< ‘a’< ‘B’< ‘b’...’Z’< 'z'
String comparison would be like 'A' < 'a' < 'B' < 'b' ... 'Z' < 'z'
我们需要在此范围内支持以下操作
We need to support following operations on this range
- 添加范围-如果适用，应该合并范围
- 删除范围-这会从跟踪范围中删除范围并重新计算范围 >
- 查询范围-给定字符，函数应该返回它是否属于任何跟踪范围的一部分。
- Add range - this should merge the ranges if applicable
- Delete range - this deletes range from tracked ranges and recompute the ranges
- Query range - Given a character, function should return whether it is part of any of tracked ranges or not.
请注意，跟踪的范围可能是不连续的。
Note that tracked ranges can be dis-continuous.
我的解决方案：
我想出了两种方法。
- 存储范围为双向链表或
- 将范围存储为某种平衡树，叶节点具有实际数据，并且它们作为链接列表相互连接。
您是否认为此解决方案足够好，或者您可以想到任何更好的方法来使这三个API发挥最佳性能？
Do you think that this solution are good enough or you can think of any better way of doing this so that those three API gives your best performance ?
推荐答案
您可能正在寻找 interval树 。
You are probably looking for an interval tree.
使用数据结构和自定义比较器来指示范围在做什么，您将可以执行所需的操作
Use the data structure with your custom comparator to indicate "What's on range", and you will be able to do the required operations efficiently.
注意，间隔树实际上是实现第二个想法的有效方法（某种平衡树）
Note, an interval tree is actually an efficient way to implement your 2nd idea (Store ranges as a some sort of balanced tree)
这篇关于范围查询的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
