algorithm - 使用 "Treap"比较两组

Question

我想用Treap结构，但是对这种树不是很熟悉。

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

我怎样才能完成这项工作？

谢谢

Answer 1

陷阱

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

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

测量

衡量两组之间相似性的一个指标是 Jaccard Index .我们将我们的集合称为 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() 可以在恒定时间内实现。

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

伪代码

第一步。

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)。