论文部分内容阅读
Foster的删除HB（k）树的结点的算法的主要思想是先删除结点再自下而上处理某些子树，涉及自下而上的后退。提出一种新的删除HB（k）树的结点的算法，其主要思想是先自上而下处理某些子树再删除结点，不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Foster的删除HB（k）树的结点的算法相比，新算法不涉及辅助栈的使用。设n是HB（k）树的结点的个数。新算法的时间复杂性是O（10g2n），与Foster的删除HB（k）树的结点的算法的相同。实验结果表明新算法的平均执行时间比Foster的