在 O(max(h1, h2)) 时间内将两个 BST 合并在一起
Merging two BSTs together in O(max(h1, h2)) time
有办法吗？换句话说，有没有办法在不知道高度的情况下知道哪棵树具有 smaller/larger 高度？这样我们就知道我们需要从哪棵树中挑选房间。请注意，第一棵树中的所有元素都小于第二棵树中的所有元素。
h1和h2是树的高度
合并后的新树的高度需要为 max(h1 , h2) + 1
我认为你必须明确地找到树的高度。没有更具体的信息，您将无能为力。您可以在 O(n) 时间内递归地找到树的高度，其中 n 是树中的节点数。
从T2中取出最小的元素，使其成为一棵以T1为左子树，其余为T2的右子树的树的根。 max(h1, h2) 只是 T2 左脊柱长度的方便界限。我们实际上可以得到一个运行时间为 O(min(h1, h2)) 的算法，通过以吻合的方式遍历 T1 的右脊柱和 T2 的左脊柱，然后在 [=12= 中的最大值时执行该算法的适当镜像] 的 T2 被发现。
有办法吗？换句话说，有没有办法在不知道高度的情况下知道哪棵树具有 smaller/larger 高度？这样我们就知道我们需要从哪棵树中挑选房间。请注意，第一棵树中的所有元素都小于第二棵树中的所有元素。
h1和h2是树的高度 合并后的新树的高度需要为 max(h1 , h2) + 1
我认为你必须明确地找到树的高度。没有更具体的信息，您将无能为力。您可以在 O(n) 时间内递归地找到树的高度，其中 n 是树中的节点数。
从T2中取出最小的元素，使其成为一棵以T1为左子树，其余为T2的右子树的树的根。 max(h1, h2) 只是 T2 左脊柱长度的方便界限。我们实际上可以得到一个运行时间为 O(min(h1, h2)) 的算法，通过以吻合的方式遍历 T1 的右脊柱和 T2 的左脊柱，然后在 [=12= 中的最大值时执行该算法的适当镜像] 的 T2 被发现。