一种新的删除AA-树结点的算法

摘要：

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

关键词：AA-树、准AA-树、黑高度、结点、删除、旋转

所属期刊栏目：44

分类号：TP311.12(计算技术、计算机技术)

资助基金：江苏省自然科学基金BK2005027

在线出版日期：2008-05-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：34-37