用平衡树实现集合运算的研究之一  

Research on Set Operation Using Balance Tree(1)

作　　者：武颖[1] 耿子林[1] 

机构地区：[1]华北科技学院计算机系,北京101601

出　　处：《微电子学与计算机》2008年第1期137-140,共4页Microelectronics & Computer

摘　　要：从"二元查找树"和"2-3树"实现集合的表示及其完成的集合操作进行分析,提出目前实现集合运算中存在的问题。通过对"2-3树"的改造,形成一种新的数据结构;即平衡树(BT)。BT解决了"2-3树"实现集合表示的存储空间利用率低问题。同时可以实现求集合的并、交、差、测集合包含关系操作。给出平衡树(BT)的结构定义,并对平衡树结点数据的存储结构进行了规定,对BT的性质进行了证明,然后对BT定义了遍历算法,最后给出了用BT实现集合14种操作的过程、函数的定义。Some problems in set operation are obtained after analysis about representation and operation of set by binary search tree and 2- 3 tree. Through changing 2- 3 tree, a new data structure is formed-BT. The BT solves the problems of low storage space efficiency for set representation by 2- 3 tree. Also set operations to find the union, intersect, difference set and inclusion relations can be carried out. In the paper, a definition of BT is proposed and the storage structure of BT nodes is specified. The features of BT are demonstrated and then the traverse algorithm of BT is given. At last, 14 kinds of set operations, the procedures and functions with BT are presented.

关 键 词：集合 操作 算法 平衡树 复杂度 

分 类 号：TP311.312[自动化与计算机技术—计算机软件与理论]