信息处理中有效维持动态有序集的新方法  

作　　者：辛士庆[1] 王国瑾[1,2] 

机构地区：[1]浙江大学数学系计算机图像图形研究所,杭州310027 [2]浙江大学计算机辅助设计与图形学国家重点实验室,杭州310027

出　　处：《中国科学（F辑:信息科学）》2009年第9期923-932,共10页

基　　金：国家重点基础研究发展计划(批准号:2004CB719400);国家自然科学基金(批准号:60873111)资助项目

摘　　要：文中研究了信息搜索及信息处理领域中的一个重要问题,就是如何有效地维持关键字为位串的动态有序集,以支持查找、加入、删除、求最值等操作.基于前人的研究成果,我们提出了一种性质更为完备的二叉树(RBT,rich binary tree).它同时具备二叉搜索树和数字查找树的性质;并且,所有结点都保存了它与祖先结点中次大者和次小者的最高差别位.于是,动态有序集的维持转化为对树结点的动态操作并且保证RBT的性质不变.该方法的最坏复杂度是O(L),其中L是关键字的字长.因为一般对象在计算机中都是以二进制形式存储的,所以该方法具有明显的应用潜力及可观的经济效益.文中的RBT可视为一种通用的数据结构,可以非常高效地解决与序有关的问题,比如查找、排序和维持优先队列等.例如,实验证明对于长关键字的排序,我们的算法基本上线性增长,优于快速排序,而且支持常数时间的动态插入和动态删除.

关 键 词：信息搜索 算法 数据结构 动态有序集 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]