Почему ранг не равен высоте множества в непересекающемся множестве?

Question

Я недавно читал о структуре данных disjoint-set-union.Я запутался насчет ранга эвристического.Я прочитал, что «ранг не высота дерева».

Я не могу найти это требование правильным.Дело в том, что когда для объединения используется эвристика ранга, мы можем легко увидеть, что ранг - это высота набора деревьев, но когда мы используем сжатие пути с ним, ранг больше не является высотой.Но, тем не менее, мы выполняем объединение с учетом ранга дерева.

Предположим, я звоню find (a1) и find (a2), это должно изменить ранг родителя a1 и a2, если высота родительского элементаa1 лежит в пути от корня до a1 (то же самое для a2).

Как работает это сжатие пути, когда ранга больше нет высоты дерева?Что представляет собой ранг дерева при использовании сжатия путей.

Ниже приведен код для функции поиска и объединения.Это не «полная программа».Но их можно легко превратить в одно целое.

int find(vector<int>& parent, int i) {  
    if (parent[i] != i) 
        parent[i] = find(parent, parent[i]); 

    return i; 
} 

void union(vector<int>& parent, vector<int>& rannk, int x, int y) { 
    int xroot = find(parent, x); 
    int yroot = find(parent, y);

    if (rank[xroot] < rank[yroot]) 
       parent[xroot] = yroot; 
    else if (rank[xroot] > rank[yroot]) 
        parent[yroot] = xroot; 
    else{ 
        parent[yroot] = xroot; 
        rank[xroot]++; 
    } 
}

int main() {
    vector<int> parent(10), rank(10, 1);

    for(int i = 0; i < 10; ++i)
       parent[i] = i;

    union(2, 5);
    union(1, 3);
    union(2, 7);
    union(2, 1);
    union(9, 8);
    union(0, 8);
    union(0, 1);
}

Для понимания приведено лишь несколько основных функций.

parent [i] представляет родителя элемента i, 0 <=i <= 10 rank [i] представляет ранг i (корня) набора, 0 <= i <= 10 </p>

Как вы можете легко видеть, после каждого вызова find () путь сжимается изузел к его родителю (теперь он напрямую связан с родителем).Теперь ранг не высота дерева.

Этот код использует ранг [] для определения слияния.Что представляет собой ранг [i] и как он помогает принять решение о слиянии двух множеств в union ()?

Answer 1

Ранг набора не представляет ничего, кроме ранга.Почти постоянная амортизированная временная производительность структуры несвязанных множеств с использованием сжатия пути и объединения по рангу была доказана с использованием ранга, и поэтому мы продолжаем использовать объединение по рангу, чтобы мы могли получить эту проверенную производительность.

Я почти уверен, что такая же оценка была доказана для использования сжатия пути с объединением по размеру, что также легко сделать, если вы хотите это сделать.

Объединение по высоте просто нежизнеспособный вариант со сжатием пути, так как сжатие пути делает дорогостоящим отслеживание высоты.Когда вы не используете сжатие пути, тогда ранг и рост, как вы знаете, совпадают.