论文研究一种新的删除AA树结点的算法.pdf

Andersson的删除AA-树结点的算法的主要思想是先删除结点再自下而上处理某些子树，涉及自下而上的后退。提出一种新的删除AA-树结点的算法，其主要思想是先自上而下处理某些子树再删除结点，不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Andersson的算法相比，新算法不涉及辅助栈的使用。设n是AA-树的内部结点的个数，执行新算法时进行O（lbn）次旋转，新算法的时间复杂性是O（lbn），与Andersson的算法的时间复杂性相同。实验结果表明新算法的平均执行时间比Andersson的算法的平均执行时间短。新算法的空间复杂性是O（1），比Andersson的算法的空间