3

任何帮助，将不胜感激。

4

2 回答 2

2

您可以在线性时间内与任意两个排序列表相交。

  • 获取两个 AVL 树的有序（左孩子，然后是父数据，然后是右孩子）迭代器。
  • 查看两个迭代器的头部。
    • 如果一个迭代器用完，则返回结果集。
    • 如果两个元素相等或正在计算并集，则将它们的最小值添加到结果集中。
    • 弹出最低（如果迭代器按升序排列）元素。如果两者相等，则同时弹出

这在 O(n1+n2) 中运行并且对于联合操作是最佳的（您受输出大小的限制）。

或者，您可以查看较小树的所有元素，以查看它们是否存在于较大的树中。这在 O(n1 log n2) 中运行。

这是 Google 在其 BigTable 引擎中使用（或考虑使用）来查找交集的算法：

  • 获取所有源的迭代器
  • 从 pivot = null 开始
  • 依次循环遍历所有 n 个迭代器，直到它们中的任何一个被耗尽。
    • 在此迭代器中找到大于枢轴的最小元素。
    • 如果元素是枢轴
      • 增加枢轴所在的迭代器的计数
      • 如果此枢轴在所有迭代器中，则将枢轴添加到结果集中。
    • 别的
      • 重置枢轴所在的迭代器的计数
      • 使用找到的元素作为新的枢轴。

在二叉树迭代器中查找元素或下一个最大元素：

  • 从当前元素开始
  • 向上走，直到当前元素大于正在搜索的元素，或者您在根中
  • 往下走，直到找到元素，否则你不能向左走
  • 如果当前元素小于正在搜索的元素，则返回 null（此迭代器已耗尽）
  • 否则返回当前元素

对于完全混合的类似大小的集合，这将衰减到 O(n1+n2)，如果第二棵树更大，则衰减到 O(n1 log n2)。如果一棵树中的子树的范围不与另一棵树/所有其他树中的任何节点相交，则最多访问该子树中的一个元素（其最小值）。这可能是可用的最快算法。

于 2012-11-21T10:05:20.880 回答
0

Here is a paper with efficient algorithms for finding intersections and unions of AVL trees (or other kinds of trees for that matter, and other operations).

Implementing Sets Efficiently in a Functional Language

I found this paper when I was researching this subject. The algorithms are in Haskell and they are primarily designed for immutable trees, but they will work as well for any kind of tree (though there might be some overhead in some languages). Their performance guarantees are similar to the algorithm presented above.

于 2013-12-02T20:23:05.007 回答