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

New algorithm for deleting node from AA-tree

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

The main idea of Andersson’s algorithm for deleting a node from an AA-tree is to delete the node first and then to process certain subtrees from below to above,relating to the backtracking from below to above.A new algorithm for deleting a node from an AA-tree is presented,whose main idea is to process certain subtrees from above to below first and then to delete the node,instead of relating to the backtracking from below to above.The execution of the new algorithm is illustrated by an example.The new algorithm is proved correct.Compared with Andersson’s algorithm,the new algorithm does not relate to the use of an auxiliary stack.Let n be the number of internal nodes of an AA-tree.O（lbn） rotations are performed during the execution of the new algorithm.The time complexity of the new algorithm is O（lbn）,and it is the same as that of Andersson’s algorithm.Experimental results show that the average execution time of the new algorithm is shorter than that of Andersson’s algorithm.The space complexity of the new algorithm is O（1）,and it is lower than that of Andersson’s algorithm.