首页 文章

算法 - 如何有效地连接两个二叉搜索树？

提问于
浏览 次
3

我是 not 询问如何合并两个二叉搜索树，因为这个问题确实How to merge two BST's efficiently?

我真的在问如何连接两棵树 . 因此，如果树A的所有节点都小于树B的任何节点，我们可以连接两棵树 . 但我该如何有效地做到这一点？

我的想法是找到树B的最小值，然后让树A成为最小的左子（树B） .

这很简单，时间是 O(height of B) .

但我想这个解决方案有一些问题：

  • 它可能导致最终的大树不再 balancer

  • 如果最坏情况下的运行时间为 O(h) ， h 是两棵树的最大高度怎么办？

实际上，书“Algorithm Design Manual”有这个消费税 . 我的简单解决方案足以进行此练习吗？

连接操作需要两组S1和S2，其中S1中的每个键都小于S2中的任何键，并将它们合并在一起 . 给出一种算法将两个二叉搜索树连接成一个二叉搜索树 . 最坏情况下的运行时间应为O（h），其中h是两棵树的最大高度 .

谢谢

algorithm data-structures

2 回答

  • 2

    设A是较小的集合 . 假设x = maximum_element（A）和y = minimum_element（B） .

    我们知道x <y . 获取一个键值等于 z = (x+y)/2 的节点，并将A作为其左子树，将B作为右子树 . 从此BST中删除添加的节点（使用键 z ） .

    回复于
  • 7

    我要定义：

    • h_A =最大高度 A

    • h_B =最大高度 B

    • h = min(h_A, h_B)

    您的解决方案最差情况下的运行时间为 O(h_B) ，这在 min(B) 的深度为 h_B 时发生 .

    这个问题要求 O(h) 最坏的情况 . 最好使用 O(h) 解决方案，因为如果 h_B 远大于 h_A ，我们最好将 B 附加到 max(A) 的右子节点，而不是当前的解决方案，它将 A 附加到 min(B) 的左子节点 .

    以下是如何做到这一点：

    • 递归遍历 A 的右侧和 B 的左侧 .

    • 到达 max(A) 或 min(B) 时停止遍历 .

    • 三件事之一是可能的：

    • 你得 max(A) . 在这种情况下，设置 max(A).right = B

    • 你得 min(B) . 在这种情况下，设置 min(B).left = A

    • 你得 max(A) 和 min(B) . 在这种情况下，请执行上述任一选项 .

    我们最多遍历 h_A 或 h_B 步，以较小者为准 . 也就是说， h 步骤 . 将一棵树附加到元素是不变的 . 因此运行时间为O（h） .

    回复于

相关问题