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

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

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

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

Answer 1

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

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

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