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

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