New method in information processing for maintaining an efficient dynamic ordered set  

作　　者：XIN ShiQing WANG GuoJin 

机构地区：[1]Institute of Computer Graphics and Image Processing, Zhejiang University, Hangzhou 310027, China [2]State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou 310027, China

出　　处：《Science in China(Series F)》2009年第8期1292-1301,共10页中国科学（F辑英文版）

基　　金：Supported by the National Natural Science Foundation of China (Grant No. 60873111);the National Basic Research Program of China(Grant No. 2004CB719400)

摘　　要：This paper investigates how to maintain an efficient dynamic ordered set of bit strings, which is an important problem in the field of information search and information processing. Generally, a dynamic ordered set is required to support 5 essential operations including search, insertion, deletion, max-value retrieval and next-larger-value retrieval. Based on previous research fruits, we present an advanced data structure named rich binary tree （RBT）, which follows both the binary-search-tree property and the digital-search-tree property. Also, every key K keeps the most significant difference bit （MSDB） between itself and the next larger value among K＇s ancestors, as well as that between itself and the next smaller one among its ancestors. With the new data structure, we can maintain a dynamic ordered set in O（L） time. Since computers represent objects in binary mode, our method has a big potential in application. In fact, RBT can be viewed as a general-purpose data structure for problems concerning order, such as search, sorting and maintaining a priority queue. For example, when RBT is applied in sorting, we get a linear-time algorithm with regard to the key number and its performance is far better than quick-sort. What is more powerful than quick-sort is that RBT supports constant-time dynamic insertion/deletion.This paper investigates how to maintain an efficient dynamic ordered set of bit strings, which is an important problem in the field of information search and information processing. Generally, a dynamic ordered set is required to support 5 essential operations including search, insertion, deletion, max-value retrieval and next-larger-value retrieval. Based on previous research fruits, we present an advanced data structure named rich binary tree （RBT）, which follows both the binary-search-tree property and the digital-search-tree property. Also, every key K keeps the most significant difference bit （MSDB） between itself and the next larger value among K＇s ancestors, as well as that between itself and the next smaller one among its ancestors. With the new data structure, we can maintain a dynamic ordered set in O（L） time. Since computers represent objects in binary mode, our method has a big potential in application. In fact, RBT can be viewed as a general-purpose data structure for problems concerning order, such as search, sorting and maintaining a priority queue. For example, when RBT is applied in sorting, we get a linear-time algorithm with regard to the key number and its performance is far better than quick-sort. What is more powerful than quick-sort is that RBT supports constant-time dynamic insertion/deletion.

关 键 词：information processing dynamic ordered set algorithms and data structures rich binary tree 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP311.13[自动化与计算机技术—计算机科学与技术]