Объединение непересекающихся множеств

Question

Я рассматриваю непересекающиеся множества, которые поддерживают функцию Союза.

Методика уменьшения высоты дерева:

Мы всегда сливаться меньшее дерево, тем больше один, то есть мы делаем корень меньшего дерева, чтобы указать на корень дерева больше.

Дерево больше другого, если оно имеет больше узлов.

Каждый узел представляет собой структуру с полями: некоторая информация для элемента, указатель «родительский» родительскому узлу и счетчик «счет», который используется только в том случае, если узел является корнем и содержит количество узлы в верхнем дереве.

Следующий алгоритм объединяет два вверх деревья:

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; 
    } 
} 

Рассмотрим реализацию непересекающихся множеств с соединением, где может быть в большинстве к непересекающихся множеств. Реализация использует хэш-таблицу A [0 .. max-1], в которой хранятся ключи, основанные на методе упорядоченного двойного хэширования. Пусть h1 и h2 - первичная и вторичная хеш-функции соответственно. A содержит ключи узлов всех вышеперечисленных деревьев, а также указатель на соответствующий узел для каждого из них. Я хочу написать алгоритм, который принимает в качестве параметров ключи двух узлов и объединяет вверх-деревья, к которым относятся узлы (узлы могут принадлежать любым up-tree, даже в том и в том случае, когда оно появляется соответствующим сообщением). При слиянии мы должны применять методы сжатия пути и уменьшения высоты.

Не могли бы вы дать мне подсказку, как мы можем это сделать?

Предположим, что у нас есть этот массив:

В начале узлы будут так:

Тогда, если k1 = 100, k2 = 5, после применяя алгоритм, получим ли мы это?

Тогда, если мы имеем k1 = 59, k2 = 5, то мы получим следующее:

Правильно? Тогда, применяя сжатие путь мы начинаем делать это:

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

Таким образом, мы будем иметь родителя = F, tmp-> Родитель = B, TMP = F.

Как мы продолжим?

После то k1 = 14, k2 = 59 мы получаем это:

Answer 1

Во-первых, когда вы получаете ключи, вы должны найти их в хэш-таблице.
Хеш-таблица содержит записи: (key, pointer-to-node).
Предположим, вы хотите найти ключ k. Вы проверяете:
A[h1(k) + 0*h2(k) mod size(A)] - если в нем содержится ключ 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)] ... пока вы не найдете ключ k.

Теперь, когда у вас есть указатели на 2 узла, вам нужно найти корни деревьев, к которым принадлежат эти узлы. Чтобы найти корень, вы поднимаетесь по дереву, пока не достигнете корневого узла. Вы используете для этого указатель parent, и вы можете предположить, что указатель корня parent указывает на себя, например.

Теперь, когда у вас есть 2 корня, вы можете объединить их, используя upTreeUnion.

сжатия Path работает следующим образом:

После вы нашли корень дерева для узла s, вы будете следовать по пути от s искоренять еще раз и установить parent указатель каждого узла на путь к корню.

Update:

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); 
}