algorithm - 使用“Treap”比较两组

我想使用treap结构，但我不太熟悉这种类型的树。
我有两个集合，我想写一个方法，将它们与Treap进行比较此方法应返回一个值，该值显示两个集合的相似性。（我的工作是检索一个与输入集基本相似的集）
我该怎么做？
谢谢

最佳答案

树堆
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是树中元素的数目。
此外，在插入过程中，我们可以跟踪树的大小，因此size（）可以在恒定的时间内实现。
当然，我们可以遍历树的所有元素。
伪码
第一步。

sum(A, B):

    C = A

    foreach x in B:
        C.insert(x)

    return C

第二步。

intersection(A, B):

    C = new BalancedBinarySearchTree()

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

    return C

第三步。
计算A和B的提花指数：

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

关于algorithm - 使用“Treap”比较两组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17131537/