0

我正在寻找支持联盟功能的不相交集。

树木减高技术：

我们总是将较小的树合并到较大的树上，即我们使较小树的根指向较大树的根。

如果一棵树有更多的节点，它就比另一棵树大。

每个节点都是一个带有字段的结构体：元素的一些信息、指向父节点的指针“parent”和一个计数器“count”，仅当节点是根节点并且包含在上树。

以下算法合并两个向上树：

pointer UpTreeUnion(pointer S,T) {
   if (S == NULL OR P == NULL) return;
   if (S->count >= T->count) {
       S->count = S->count + T->count;
       T->parent = S;
       return S;
   }
   else {
       T->count = T->count + S->count;
       S->parent = T;
       return T;
   }
}

考虑使用联合的不相交集的实现，其中最多可以有 k 个不相交集。该实现使用哈希表 A[0.. max-1]，其中存储了基于排序双哈希方法的键。设 h1 和 h2 分别为主要和次要散列函数。A 包含上述所有树的节点的键，以及指向每个树的相应节点的指针。我想编写一个算法，将两个节点的键作为参数并合并节点所属的向上树（节点可以属于任何向上树，即使在这种情况下，它也会出现适当的消息） . 在合并时，我们应该应用路径压缩和高度降低的技术。

你能给我一个提示，我们怎么能做到这一点？

假设我们有这个数组：

在此处输入图像描述

一开始的节点会是这样的：

在此处输入图像描述

那么如果k1=100，k2=5，应用算法后，我们会得到这个吗？

在此处输入图像描述

那么如果我们有 k1=59, k2=5，我们将得到以下结果：

在此处输入图像描述

正确的？然后应用路径压缩，我们开始这样做：

tmp=B
while (B->parent!=B)
      parent=B->parent;
      tmp->parent=B;
      tmp=parent;
}

所以我们将有 parent=F, tmp->parent=B, tmp=F。

我们如何继续？

然后 k1=14, k2=59 我们得到：

在此处输入图像描述

4

1 回答 1

2

首先，当您获得密钥时，您需要在哈希表中找到它们。
哈希表包含条目：(key, pointer-to-node)。
假设您要查找 key k。您检查：
A[h1(k) + 0*h2(k) mod size(A)]- 如果它包含 key k，则读取相应的指向节点的指针。
如果除了 之外还有其他内容k，请检查：
A[h1(k) + 1*h2(k) mod size(A)],
A[h1(k) + 2*h2(k) mod size(A)],
A[h1(k) + i*h2(k) mod size(A)]... 直到找到 key k。

现在您有了指向 2 个节点的指针，您需要找到这些节点所属的树的根。要找到根，您需要沿着树向上直到到达根节点。您parent为它使用每个节点的指针，例如，您可以假设根的parent指针指向自身。

现在您有 2 个根，您可以使用upTreeUnion.

路径压缩的工作方式如下：

在此处输入图像描述

在找到 node 的树的根之后s，再沿着从s到根的路径再一次，并将parent路径上每个节点的指针设置为根。

更新：

Algorithm(k1,k2){
   int i=0,j=0;
   int i1,i2;
   while (i<max and A[i1 = h1(k1)+i*h2(k1) mod size(A)]->key!=k1){
          i++;
   }
   while (j<max and A[i2 = h1(k2)+j*h2(k2) mod size(A)]->key!=k2){
          j++;
   }
   if (A[i1]->key!=k1) return;
   if (A[i2]->key!=k2) return;

   pointer node1,node2,root1,root2;
   node1=A[i1]->node;
   node2=A[i2]->node;
   root1=UpTreeFind(node1);
   root2=UpTreeFind(node2);
   if (root1==root2){
      printf("The nodes belong to the same up tree");
      return;
   }

   // path compression
   pointer tmp,tmpParent;

   tmp = node1;
   while (tmp->parent!=root1) {
       tmpParent=tmp->parent;
       tmp->parent=root1;
       tmp=tmpParent;
   }

   tmp = node2;
   while (tmp->parent!=root2) {
       tmpParent=tmp->parent;
       tmp->parent=root2;
       tmp=tmpParent;
   }

   UpTreeUnion(root1,root2);
}
于 2014-12-30T23:46:46.407 回答