Оптимизация ранга в Union-Find

В предыдущем подразделе была представлена оптимизация по размеру для структуры данных union-find, но в некоторых сценариях всё ещё существуют проблемы, как показано на рисунке ниже, при выполнении операции union(4,2).

Согласно предыдущему подразделу, при оптимизации по размеру корень множества с меньшим числом элементов указывает на корень множества с большим числом элементов. После операции количество уровней становится равным 4, что на один уровень больше, чем раньше, как показано на рисунке ниже:

Видно, что опираться на размер множества для определения направления указателя не совсем правильно. Точнее, направление указателя корня следует определять на основе количества уровней двух множеств: корень множества с меньшим количеством уровней указывает на корень множества с большим количеством уровней, как показано на рисунке ниже. Это оптимизация по рангу.

Мы добавляем массив rank в свойства структуры данных union-find, где rank[i] представляет количество уровней дерева, представленного множеством с корнем в i.

...
private int[] rank;   // rank[i] представляет количество уровней дерева, представленного множеством с корнем в i
private int[] parent; // parent[i] представляет родительский узел, на который указывает i-й элемент
private int count;    // количество элементов данных
...

Соответствующим образом следует изменить конструктор:

...
// конструктор
public UnionFind4(int count){
    rank = new int[count];
    parent = new int[count];
    this.count = count;
    // инициализация: каждый parent[i] указывает на самого себя, что означает, что каждый элемент образует отдельное множество
    for( int i = 0 ; i < count ; i ++ ){
        parent[i] = i;
        rank[i] = 1;
    }
}
...

При объединении двух элементов необходимо сравнить количество уровней множеств корневых узлов. Весь процесс имеет сложность O(h), где h — высота дерева.

...
public void unionElements(int p, int q){
    int pRoot = find(p);
    int qRoot = find(q);
    if( pRoot == qRoot )
        return;

    if( rank[pRoot] < rank[qRoot] ){
        parent[pRoot] = qRoot;
    }
    else if( rank[qRoot] < rank[pRoot]){
        parent[qRoot] = pRoot;
    }
    else{ // rank[pRoot] == rank[qRoot]
        parent[pRoot] = qRoot;
        rank[qRoot] += 1;   // на этом этапе я поддерживаю значение rank
    }
}
...

Пример кода на Java

Исходный пакет:Скачать

Код файла UnionFind3.java:

package example.union;
/**
* Оптимизация на основе ранга
 */
public class UnionFind4 {
    private int[] rank;   // rank[i] представляет количество уровней дерева, представленного множеством с корнем в i
    private int[] parent; // parent[i] представляет родительский узел, на который указывает i-й элемент
    private int count;    // количество элементов данных
    // конструктор
    public UnionFind4(int count){
        rank = new int[count];
        parent = new int[count];
        this.count = count;
        // инициализация: каждый parent[i] указывает на самого себя, что означает, что каждый элемент образует отдельное множество
        for( int i = 0 ; i < count ; i ++ ){
            parent[i] = i;
            rank[i] = 1;
        }
    }
    // процесс find, найти номер множества, соответствующего элементу p
    // сложность O(h), h — высота дерева
    private int find(int p){
        assert( p >= 0 && p < count );
        // продолжаем обращаться к родительскому узлу, пока не достигнем корневого узла
        // признак корневого узла: parent[p] == p
        while( p != parent[p] )
            p = parent[p];
        return p;
    }
    // проверить, принадлежат ли элемент p и элемент q одному и тому же множеству
    // сложность O(h), h — высота дерева
    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }
    // объединить множества, содержащие элемент p и элемент q
    // сложность O(h), h — высота дерева
    public void unionElements(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if( pRoot == qRoot )
            return;
        if( rank[pRoot] < rank[qRoot] ){
            parent[pRoot] = qRoot;
        }
        else if( rank[qRoot] < rank[pRoot]){
            parent[qRoot] = pRoot;
        }
        else{ // rank[pRoot] == rank[qRoot]
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;   // поддерживать значение rank
        }
    }
}
Другие расширения