作者：唐自立avl树结点删除foster新算法时间复杂性空间复杂性自上而下执行过程时间比子树思想
摘要：所有传统的删除AVL树的结点的算法的主要思想都是先删除结点再自下而上处理某些子树,涉及自下而上的后退.提出一种新的删除AVL树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退.举例说明新算法的执行过程.证明新算法是正确的.与目前通常采用的Foster的算法相比,新算法不涉及辅助栈的使用.设n是AVL树的结点的个数.新算法的时间复杂性是O(log2n),与Foster的算法相同.实验结果表明新算法的平均执行时间比Foster的算法的短.新算法的空间复杂性是O(1),比Foster的算法的低.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
