2-3树（B树）中的求职面试题
Job interview question in 2-3 trees (B trees)
这是求职面试问题的一部分，在第二部分变得更难了。
给定两棵 2-3 树 T1 和 T2，使得每棵树的 h 已知（h 表示高度）和 m，每棵树的 M 也是已知的（ m 表示最小值，M 表示最大值），再加上 T1 中的每个节点 < T2 中的每个节点。
我被要求找到一种算法将它们都连接到 O(|h1-h2|+1)
中的一棵树中
这个很简单，我必须指出这个算法可能会导致 h 比前两个大的树。
现在， 我得到了 k 2-3 棵树（T1、T2、T3...Tk），条件完全相同，而且知道 h_1<=h_2<=...<=h_k 和 没有三棵树具有相同的高度 将它们加入 O(h_k-h_1+k)。
起初我考虑过使用之前的算法将前两个连接在一起，然后将第三个连接到结果等等，但我觉得这里出了问题，因为我没有利用“没有三棵树的高度相同。
我在这里缺少什么？
您的解决方案是正确的，但如果您有超过 2 棵相同高度的树，则不会正确。例如，如果你有 k 棵高度相同的树，那么前两棵确实会在 O(h_1 - h_1) = O(1) 时间内合并，但最终的高度可能会变成 h_1 + 1。虽然它可能会变成，也可能不会，但让我证明一切都可能出错。
在一棵高度为 n 的树中，我们可以拥有的最大键数是 3^(n+1)-1。这是因为每个顶点最多有 3 个子树，因此第 i 层有 3^i 个顶点，添加 n 层将导致 (3^(n + 1) - 1)/2 个顶点。因为在这种情况下每个顶点都有 2 个键，所以键的总数是 3^(n + 1) - 1.
因此，如果我们合并4棵这样的最大树，我们肯定会得到一棵高度增加2的树，合并16棵树会得到高度增加3的树，依此类推。因此，虽然前 3 次合并是在恒定时间内完成的，但接下来的 12 次合并慢了两倍，接下来的 48 次合并慢了 3 倍，依此类推。从 1 开始到 log(k).
，每个 i 需要执行 Ω(i) 次操作 Ω(3^(i+1) - 3^i) 次
因为Ω(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 部分在渐近边界中的来源。
这是求职面试问题的一部分，在第二部分变得更难了。
给定两棵 2-3 树 T1 和 T2，使得每棵树的 h 已知（h 表示高度）和 m，每棵树的 M 也是已知的（ m 表示最小值，M 表示最大值），再加上 T1 中的每个节点 < T2 中的每个节点。
我被要求找到一种算法将它们都连接到 O(|h1-h2|+1)
这个很简单，我必须指出这个算法可能会导致 h 比前两个大的树。
现在， 我得到了 k 2-3 棵树（T1、T2、T3...Tk），条件完全相同，而且知道 h_1<=h_2<=...<=h_k 和 没有三棵树具有相同的高度 将它们加入 O(h_k-h_1+k)。
起初我考虑过使用之前的算法将前两个连接在一起，然后将第三个连接到结果等等，但我觉得这里出了问题，因为我没有利用“没有三棵树的高度相同。
我在这里缺少什么？
您的解决方案是正确的，但如果您有超过 2 棵相同高度的树，则不会正确。例如，如果你有 k 棵高度相同的树，那么前两棵确实会在 O(h_1 - h_1) = O(1) 时间内合并，但最终的高度可能会变成 h_1 + 1。虽然它可能会变成，也可能不会，但让我证明一切都可能出错。
在一棵高度为 n 的树中，我们可以拥有的最大键数是 3^(n+1)-1。这是因为每个顶点最多有 3 个子树，因此第 i 层有 3^i 个顶点，添加 n 层将导致 (3^(n + 1) - 1)/2 个顶点。因为在这种情况下每个顶点都有 2 个键，所以键的总数是 3^(n + 1) - 1.
因此，如果我们合并4棵这样的最大树，我们肯定会得到一棵高度增加2的树，合并16棵树会得到高度增加3的树，依此类推。因此，虽然前 3 次合并是在恒定时间内完成的，但接下来的 12 次合并慢了两倍，接下来的 48 次合并慢了 3 倍，依此类推。从 1 开始到 log(k).
i 需要执行 Ω(i) 次操作 Ω(3^(i+1) - 3^i) 次
因为Ω(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 部分在渐近边界中的来源。