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

Abstract: 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.

Key words: AA-tree, almost AA-tree, black-height, node, deletion, rotation