用平衡树实现集合运算的研究之一
Research on Set Operation Using Balance Tree(1)作者机构:华北科技学院计算机系北京101601
出 版 物:《微电子学与计算机》 (Microelectronics & Computer)
年 卷 期:2008年第25卷第1期
页 面:137-140页
学科分类:08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术(可授工学、理学学位)]
摘 要:从二元查找树和2-3树实现集合的表示及其完成的集合操作进行分析,提出目前实现集合运算中存在的问题。通过对2-3树的改造,形成一种新的数据结构;即平衡树(BT)。BT解决了2-3树实现集合表示的存储空间利用率低问题。同时可以实现求集合的并、交、差、测集合包含关系操作。给出平衡树(BT)的结构定义,并对平衡树结点数据的存储结构进行了规定,对BT的性质进行了证明,然后对BT定义了遍历算法,最后给出了用BT实现集合14种操作的过程、函数的定义。