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

Research on Set Operation Using Balance Tree(4)

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

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

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

摘　　要：研究如何在一棵平衡树中删除一个结点后仍保持平衡.若删除结点后无法保持平衡,对原平衡树中的有效结点逐个取出进行重建平衡树,同时完成对平衡树存贮空间的压缩.在给出删除算法(Delete)的同时,给出了后根删除(Postd)、建树(Maketree)、构造(Construct)、合成(Compost)、嵌入(Implant)等算法.这些算法的完成为求集合的并、交、差及测集合的包含关系奠定了基础.最后给出删除算法的时间复杂度证明.The paper is the later ,series of paper three, how to delete a node in a BT and keep its balance is the topic. If the BT can＇t keep balance after a node is deleted, get all the active nodes one by one and rebuild the BT. At the same time, the compression for storage space for BT is completed. Apart from the delete algorithms, other algorithms such as Postd, Maketree, Construct, Compost, Implant are present, too. All these algorithms are foundations of set operation to find the union, intersect, difference set and inclusion relations. In the end, the time complexity of above algorithms is presented.

关 键 词：删除 建树 合并 算法 平衡 栈 

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