Abstract: The main idea of Foster’s algorithm for deleting a node from an HB(k) 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 HB(k) 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 for deleting a node from an HB(k) tree，the new algorithm does not relate to the use of an auxiliary stack．Let n be the number of nodes of an HB(k) tree．The time complexity of the new algorithm is O(log2n)，and it is the same as that of Foster’s algorithm for deleting a node from an HB(k) tree．Experimental results show that the average execution time of the new algorithm is shorter than that of Foster’s algorithm for deleting a node from an HB(k) tree．The space complexity of the new algorithm is O(1)，and it is lower than that of Foster’s algorithm for deleting a node from an HB(k) tree．

Key words: HB(k) tree, node, deletion, rotation

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

关键词: HB(k)树, 结点, 删除, 旋转