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

摘要

在上篇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)时间复杂度的证明.