论文部分内容阅读
在上篇Search（f，r，a）函数基础上对平衡树的插入算法Inseart（r，a）进行了深入的研究．首先用Search（y，r，a）函数判别a是否在Tr中，若a已在Tr中插入结束，否则Search（f，r，a）函数给出a应插入于Tr中的位置f，据f的不同情况实施插入．在Inseart（r，a）算法中，引入了Inseartasleaf（f，a）过程，对该过程中的Inseartasleaf 31（f，a）算法进行了详细论述，最后给出了Inseart（r，a）时间复杂度的证明．