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

Research on Set Operation Using Balance Tree(5)

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

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

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

摘　　要：研究了两棵平衡树之间的操作,通过两棵平衡树的同时操作,完成两个集合之间的各种运算,如测试集合包含关系(ISSUBSET)、求集合的并(UNION)、求集合的交(INTERSECT)、求集合的差(DEDUCT)、按关键字序列的连接(CONCATENATE)、拆分(SPLIT)、空间压缩(COMPACT)等算法.重要算法给出了时间复杂度证明.这些算法的实现和良好的时间复杂度,说明BT很好地解决了集合的存储和运算工作,解决了"2-3"树完成集合运算的空间利用率低和个别集合操作不相容问题.The paper is the later series of paper four; the operation between two BTs is presented. Through the operations between two BTs, the computations between two sets can be carried out, such as Test the issubset of the sets, compute the union, intersect, deduct of sets, concatenate by key words, split and space compact. For some important algorithms, time complexity is proved. Good time complexity and implementation of the algorithms prove the two facts that the BT can solve the problems about storage and computation of set very well and the BT can solve the problems of low space efficiency and non - compatible problems in .set operations by 2 - 3 tree.

关 键 词：集合 算法时间复杂度 平衡树 

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