第k小元素范围查询算法

• 作者: 任会斌 李征
• 来源期刊: 通信市场
• 学科: 工学
• 关键词: 范围查询 线段树 扩展红黑树
• 年，卷（期）: 2009,（7）
• 所属期刊栏目: 2009第四届中国电信行业网络信息安全论坛征文优秀论文
• 页码范围: 73-77
• 页数: 5页
• 分类号: TN91
• 字数: 4123字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-6675-B.2009.07.019

摘要

范围查询是进行数据分析的有效方法,预计算技术可以提高查询的速度,从而实现快速的用户响应.提出了一个新的范围查询问题:第k小元素范围查询,迄今未见有文献报导.在决策支持系统中,了解第k小元素比仅仅依靠最大值要关键得多.在线段树、扩展红黑树及预计算的基础上,给出了查询第k小元素的算法,其空间复杂度为0(nlogn),查询的时间复杂度为0(log3n).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	任会斌	同济大学电子信息与工程学院	2	0	0.0	0.0
2	李征	同济大学电子信息与工程学院	26	65	5.0	7.0