一种新的删除AVL树的结点的算法

所有传统的删除AVL树的结点的算法的主要思想都是先删除结点再自下而上处理某些子树，涉及自下而上的后退。提出一种新的删除AVL树的结点的算法，其主要思想是先自上而下处理某些子树再删除结点，不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与目前通常采用的Foster的算法相比，新算法不涉及辅助栈的使用。设n是AVL树的结点的个数。新算法的时间复杂性是O(log2n)，与Foster的算法相同。实验结果表明新算法的平均执行时间比Foster的算法的短。新算法的空间复杂性是O(1)，比Foster的算法的低。

A NEW ALGORITHM FOR DELETING A NODE FROM AN AVL TREE

The main idea of every traditional algorithm for deleting a node from an AVL 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 AVL 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 Foster's algorithm,which is commonly adopted at present,the new algorithm does not relate to the use of an auxiliary stack.Let n be the number of nodes of an AVL tree.The time complexity of the new algorithm is O(log_2n),and it is the same as that of Foster's algorithm.Experimental results show that the average execution time of the new algorithm is shorter than that of Foster's algorithm.The space complexity of the new algorithm is O(1),and it is lower than that of Foster's algorithm.