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

Research on Set Operation Using Balance Tree(3)

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

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

出　　处：《微电子学与计算机》2008年第3期182-185,189,共5页Microelectronics & Computer

摘　　要：在上篇Search(f,r,a)函数基础上对平衡树的插入算法Inseart(r,a)进行了深入的研究.首先用Search(f,r,a)函数判别a是否在Tr中,若a已在Tr中插入结束,否则Search(f,r,a)函数给出a应插入于Tr中的位置f,据f的不同情况实施插入.在Inseart(r,a)算法中,引入了Inseartasleaf(f,a)过程,对该过程中的Inseartasleaf31(f,a)算法进行了详细论述,最后给出了Inseart(r,a)时间复杂度的证明.The paper is the later series of paper two, a deeper research on the algorithm Inseart（ r, a ） for BT according to the function Search（f, r, a ） described in the paper two is done. Firstly, the function Search （f, r, a ） is used to decide whether a is in Tr. If true, the inserting is over. Or Search （f, r, a ） aires the location f of a in Tr, and then a is inserted based on f. In the algorithm Inseart（ r, a ）, the procedure Inseartasleaf （f, a ） and the details of the algorithm Inseartasleaf 31（f, a ） are presented. In the end, the demonstration of the time complexity of Inseart（ r, a ） is given.

关 键 词：子树 分裂 插入 平衡树 搜索 

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