2-3棵树(B树)的面试问题

Question

这是面试问题的一部分，在第二部分变得更加困难。

给出了2~3棵树T1和T2，使得已知树的h (h表示高度)和m，每棵树的M也是已知的(m表示最小，M表示最大)，再加上T1中的每个节点都< T2中的每个节点。我被要求在O(|h1-h2|+1)中找到一种算法将两者连接到一棵树中。

这个很简单，我必须指出，这个算法可能会导致一棵比前两棵树更大的树。

现在，I给了k 2-3棵树(T1，T2，T3...Tk)，它们具有相同的精确条件，并且知道h_1<=h_2<=...<=h_k和没有三棵树有相同的高度来加入O(h_k-h_1+k)。

一开始，我想用previou算法把前两棵树连在一起，然后再把第三棵树连接到一起，等等，但我觉得这里出了点问题，因为我没有利用“没有三棵树有相同的高度”这一事实。

我在这里错过了什么？

Answer 1

您的解决方案是正确的，但如果您有超过2棵树的高度相同。例如，如果您有相同高度的k树，那么前两棵树确实将合并到O(h_1 - h_1) = O(1) time中，但是得到的高度可以变成h_1 + 1。虽然它可能只会变成，或者可能不会，但让我表明，一切都有可能出问题。

在高度为n的树中，我们可以拥有的最大键数是3^(n+1)-1。这是因为每个顶点最多有三个子树，因此第一层有3^i顶点，添加n层将导致(3^(n + 1) - 1)/2顶点。因为在这种情况下，每个顶点都有两个键，所以键的总数是3^(n + 1) - 1。

因此，如果我们合并4棵这样的最大树，我们肯定会得到一棵树的高度增加了2，16棵合并树的高度增加了3，依此类推。因此，前3次合并是在恒定时间内完成的，而接下来的12次合并则慢了两倍，而接下来的48次合并则慢了3倍，依此类推。您将为每个Ω(i)从1开始执行Ω(3^(i+1) - 3^i)操作，直到log(k)。

​

​

因为Ω(3^log(k)) = Ω(k)这个和肯定是Ω(k log k)，所以不适合于给定的渐近界。

当没有3棵树有相同的高度时，就不会出现这个问题，因为当你将两棵树合并时，产生的高度是max(h_i, h_(i+1)) + 1 = h_(i+1) + 1和h_(i+3) >= h_(i+1) + 1，因此合并部分的高度永远不会高于下一棵树，这就是+k部分的渐近界。