algorithm - 使用“Treap”比较两组

Question

我想使用 Treap 结构，但我对这种类型的树不太熟悉。

我有两套，我想写一个方法来将它们与 Treap 进行比较。此方法应返回一个值，该值显示两个集合的相似性。（我的工作是检索一个与输入集最相似的集合）

我该怎么做这项工作？

谢谢

Answer 1

特雷普

Treap 是平衡二叉搜索树的一个示例（您可以将它们中的任何一个用于此问题）。包含 n 个元素的 Treap 的预期高度是 O(logn) - 预期的，因为 Treap 是一个随机数据结构。

以下解决方案适用于任何二叉搜索树，但如果使用平衡二叉搜索树（例如 Treap），它的性能要好得多。

措施

衡量两组相似性的一种方法是Jaccard 指数。让我们称我们的集合 A 和 B。Jaccard 索引定义为：

所以要计算 A 和 B 的 Jaccard 指数，我们必须计算 A 和 B 的和和交集。

运营

假设 A 和 B 实现为平衡二叉搜索树。

二叉搜索树可以支持许多操作，但其中三个足以解决此问题：

• find(x) - 仅当 x 在树中时才返回 true
• insert(x) - 如果在此操作之前 x 不在树中，则将 x 插入树中
• size() - 返回树中元素的数量

在平衡二叉搜索树中，find(x) 和 insert(x) 的运行时间为 O(logn)，其中 n 是树中元素的数量。

另外，在插入过程中，我们可以跟踪Tree的大小，所以size()可以在一个固定的时间内实现。

当然，我们可以遍历 Tree 的所有元素。

伪代码

第1步。

sum(A, B):

    C = A 

    foreach x in B:
        C.insert(x)

    return C

第2步。

intersection(A, B):

    C = new BalancedBinarySearchTree()

    foreach x in B:
        if(A.find(x) == true):
            C.insert(x)

    return C

步骤 3。

计算 A 和 B 的 Jaccard 指数：

JaccardIndex(A, B)
    S = sum(A, B)
    I = intersect(A, B)

    return I.size() / S.size()

复杂

让我们假设：

n = A.size()
m = B.size()

那么求和的复杂度是O(n + m * log(n + m))，计算交集的复杂度是O(m * log n)。