从BST删除有序的数字序列

Question

我在考试期间遇到了这个问题,但我找不到快速的答案.

有一个数组A包含一些有序数字A = [1,3,6,9,11]和一个数字为键的BST.我必须提供一个有效的递归算法来从BST中删除A中的数字.

我遇到的问题不是删除节点,而是如何使用在删除节点时排序数组的事实.

有人可以帮我提一些提示吗？

Answer 1

这是一种可能的方法。

您可以同时遍历 BST（使用标准递归算法）和A（从左到右）。每次遍历都会按升序产生元素。您正在寻找匹配的元素以将其从树中删除。

简单的算法会有O(size(BST))时间复杂度。

在某些情况下，您可以完全避免查看左子树：树中“当前”节点的值为您提供左子树中值的上限，因此如果该值小于“当前”节点的值的元素A，跳过左子树。

您也可以在耗尽后立即停止算法A。